| // © 2016 and later: Unicode, Inc. and others. | |
| // License & terms of use: http://www.unicode.org/copyright.html | |
| /* | |
| ****************************************************************************** | |
| * | |
| * Copyright (C) 2007-2012, International Business Machines | |
| * Corporation and others. All Rights Reserved. | |
| * | |
| ****************************************************************************** | |
| * file name: unisetspan.cpp | |
| * encoding: UTF-8 | |
| * tab size: 8 (not used) | |
| * indentation:4 | |
| * | |
| * created on: 2007mar01 | |
| * created by: Markus W. Scherer | |
| */ | |
| #if defined(STARBOARD) | |
| #include "starboard/client_porting/poem/string_poem.h" | |
| #endif // defined(STARBOARD) | |
| #include "unicode/utypes.h" | |
| #include "unicode/uniset.h" | |
| #include "unicode/ustring.h" | |
| #include "unicode/utf8.h" | |
| #include "unicode/utf16.h" | |
| #include "cmemory.h" | |
| #include "uvector.h" | |
| #include "unisetspan.h" | |
| U_NAMESPACE_BEGIN | |
| /* | |
| * List of offsets from the current position from where to try matching | |
| * a code point or a string. | |
| * Store offsets rather than indexes to simplify the code and use the same list | |
| * for both increments (in span()) and decrements (in spanBack()). | |
| * | |
| * Assumption: The maximum offset is limited, and the offsets that are stored | |
| * at any one time are relatively dense, that is, there are normally no gaps of | |
| * hundreds or thousands of offset values. | |
| * | |
| * The implementation uses a circular buffer of byte flags, | |
| * each indicating whether the corresponding offset is in the list. | |
| * This avoids inserting into a sorted list of offsets (or absolute indexes) and | |
| * physically moving part of the list. | |
| * | |
| * Note: In principle, the caller should setMaxLength() to the maximum of the | |
| * max string length and U16_LENGTH/U8_LENGTH to account for | |
| * "long" single code points. | |
| * However, this implementation uses at least a staticList with more than | |
| * U8_LENGTH entries anyway. | |
| * | |
| * Note: If maxLength were guaranteed to be no more than 32 or 64, | |
| * the list could be stored as bit flags in a single integer. | |
| * Rather than handling a circular buffer with a start list index, | |
| * the integer would simply be shifted when lower offsets are removed. | |
| * UnicodeSet does not have a limit on the lengths of strings. | |
| */ | |
| class OffsetList { // Only ever stack-allocated, does not need to inherit UMemory. | |
| public: | |
| OffsetList() : list(staticList), capacity(0), length(0), start(0) {} | |
| ~OffsetList() { | |
| if(list!=staticList) { | |
| uprv_free(list); | |
| } | |
| } | |
| // Call exactly once if the list is to be used. | |
| void setMaxLength(int32_t maxLength) { | |
| if(maxLength<=(int32_t)sizeof(staticList)) { | |
| capacity=(int32_t)sizeof(staticList); | |
| } else { | |
| UBool *l=(UBool *)uprv_malloc(maxLength); | |
| if(l!=NULL) { | |
| list=l; | |
| capacity=maxLength; | |
| } | |
| } | |
| uprv_memset(list, 0, capacity); | |
| } | |
| void clear() { | |
| uprv_memset(list, 0, capacity); | |
| start=length=0; | |
| } | |
| UBool isEmpty() const { | |
| return (UBool)(length==0); | |
| } | |
| // Reduce all stored offsets by delta, used when the current position | |
| // moves by delta. | |
| // There must not be any offsets lower than delta. | |
| // If there is an offset equal to delta, it is removed. | |
| // delta=[1..maxLength] | |
| void shift(int32_t delta) { | |
| int32_t i=start+delta; | |
| if(i>=capacity) { | |
| i-=capacity; | |
| } | |
| if(list[i]) { | |
| list[i]=FALSE; | |
| --length; | |
| } | |
| start=i; | |
| } | |
| // Add an offset. The list must not contain it yet. | |
| // offset=[1..maxLength] | |
| void addOffset(int32_t offset) { | |
| int32_t i=start+offset; | |
| if(i>=capacity) { | |
| i-=capacity; | |
| } | |
| list[i]=TRUE; | |
| ++length; | |
| } | |
| // offset=[1..maxLength] | |
| UBool containsOffset(int32_t offset) const { | |
| int32_t i=start+offset; | |
| if(i>=capacity) { | |
| i-=capacity; | |
| } | |
| return list[i]; | |
| } | |
| // Find the lowest stored offset from a non-empty list, remove it, | |
| // and reduce all other offsets by this minimum. | |
| // Returns [1..maxLength]. | |
| int32_t popMinimum() { | |
| // Look for the next offset in list[start+1..capacity-1]. | |
| int32_t i=start, result; | |
| while(++i<capacity) { | |
| if(list[i]) { | |
| list[i]=FALSE; | |
| --length; | |
| result=i-start; | |
| start=i; | |
| return result; | |
| } | |
| } | |
| // i==capacity | |
| // Wrap around and look for the next offset in list[0..start]. | |
| // Since the list is not empty, there will be one. | |
| result=capacity-start; | |
| i=0; | |
| while(!list[i]) { | |
| ++i; | |
| } | |
| list[i]=FALSE; | |
| --length; | |
| start=i; | |
| return result+=i; | |
| } | |
| private: | |
| UBool *list; | |
| int32_t capacity; | |
| int32_t length; | |
| int32_t start; | |
| UBool staticList[16]; | |
| }; | |
| // Get the number of UTF-8 bytes for a UTF-16 (sub)string. | |
| static int32_t | |
| getUTF8Length(const UChar *s, int32_t length) { | |
| UErrorCode errorCode=U_ZERO_ERROR; | |
| int32_t length8=0; | |
| u_strToUTF8(NULL, 0, &length8, s, length, &errorCode); | |
| if(U_SUCCESS(errorCode) || errorCode==U_BUFFER_OVERFLOW_ERROR) { | |
| return length8; | |
| } else { | |
| // The string contains an unpaired surrogate. | |
| // Ignore this string. | |
| return 0; | |
| } | |
| } | |
| // Append the UTF-8 version of the string to t and return the appended UTF-8 length. | |
| static int32_t | |
| appendUTF8(const UChar *s, int32_t length, uint8_t *t, int32_t capacity) { | |
| UErrorCode errorCode=U_ZERO_ERROR; | |
| int32_t length8=0; | |
| u_strToUTF8((char *)t, capacity, &length8, s, length, &errorCode); | |
| if(U_SUCCESS(errorCode)) { | |
| return length8; | |
| } else { | |
| // The string contains an unpaired surrogate. | |
| // Ignore this string. | |
| return 0; | |
| } | |
| } | |
| static inline uint8_t | |
| makeSpanLengthByte(int32_t spanLength) { | |
| // 0xfe==UnicodeSetStringSpan::LONG_SPAN | |
| return spanLength<0xfe ? (uint8_t)spanLength : (uint8_t)0xfe; | |
| } | |
| // Construct for all variants of span(), or only for any one variant. | |
| // Initialize as little as possible, for single use. | |
| UnicodeSetStringSpan::UnicodeSetStringSpan(const UnicodeSet &set, | |
| const UVector &setStrings, | |
| uint32_t which) | |
| : spanSet(0, 0x10ffff), pSpanNotSet(NULL), strings(setStrings), | |
| utf8Lengths(NULL), spanLengths(NULL), utf8(NULL), | |
| utf8Length(0), | |
| maxLength16(0), maxLength8(0), | |
| all((UBool)(which==ALL)) { | |
| spanSet.retainAll(set); | |
| if(which&NOT_CONTAINED) { | |
| // Default to the same sets. | |
| // addToSpanNotSet() will create a separate set if necessary. | |
| pSpanNotSet=&spanSet; | |
| } | |
| // Determine if the strings even need to be taken into account at all for span() etc. | |
| // If any string is relevant, then all strings need to be used for | |
| // span(longest match) but only the relevant ones for span(while contained). | |
| // TODO: Possible optimization: Distinguish CONTAINED vs. LONGEST_MATCH | |
| // and do not store UTF-8 strings if !thisRelevant and CONTAINED. | |
| // (Only store irrelevant UTF-8 strings for LONGEST_MATCH where they are relevant after all.) | |
| // Also count the lengths of the UTF-8 versions of the strings for memory allocation. | |
| int32_t stringsLength=strings.size(); | |
| int32_t i, spanLength; | |
| UBool someRelevant=FALSE; | |
| for(i=0; i<stringsLength; ++i) { | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| UBool thisRelevant; | |
| spanLength=spanSet.span(s16, length16, USET_SPAN_CONTAINED); | |
| if(spanLength<length16) { // Relevant string. | |
| someRelevant=thisRelevant=TRUE; | |
| } else { | |
| thisRelevant=FALSE; | |
| } | |
| if((which&UTF16) && length16>maxLength16) { | |
| maxLength16=length16; | |
| } | |
| if((which&UTF8) && (thisRelevant || (which&CONTAINED))) { | |
| int32_t length8=getUTF8Length(s16, length16); | |
| utf8Length+=length8; | |
| if(length8>maxLength8) { | |
| maxLength8=length8; | |
| } | |
| } | |
| } | |
| if(!someRelevant) { | |
| maxLength16=maxLength8=0; | |
| return; | |
| } | |
| // Freeze after checking for the need to use strings at all because freezing | |
| // a set takes some time and memory which are wasted if there are no relevant strings. | |
| if(all) { | |
| spanSet.freeze(); | |
| } | |
| uint8_t *spanBackLengths; | |
| uint8_t *spanUTF8Lengths; | |
| uint8_t *spanBackUTF8Lengths; | |
| // Allocate a block of meta data. | |
| int32_t allocSize; | |
| if(all) { | |
| // UTF-8 lengths, 4 sets of span lengths, UTF-8 strings. | |
| allocSize=stringsLength*(4+1+1+1+1)+utf8Length; | |
| } else { | |
| allocSize=stringsLength; // One set of span lengths. | |
| if(which&UTF8) { | |
| // UTF-8 lengths and UTF-8 strings. | |
| allocSize+=stringsLength*4+utf8Length; | |
| } | |
| } | |
| if(allocSize<=(int32_t)sizeof(staticLengths)) { | |
| utf8Lengths=staticLengths; | |
| } else { | |
| utf8Lengths=(int32_t *)uprv_malloc(allocSize); | |
| if(utf8Lengths==NULL) { | |
| maxLength16=maxLength8=0; // Prevent usage by making needsStringSpanUTF16/8() return FALSE. | |
| return; // Out of memory. | |
| } | |
| } | |
| if(all) { | |
| // Store span lengths for all span() variants. | |
| spanLengths=(uint8_t *)(utf8Lengths+stringsLength); | |
| spanBackLengths=spanLengths+stringsLength; | |
| spanUTF8Lengths=spanBackLengths+stringsLength; | |
| spanBackUTF8Lengths=spanUTF8Lengths+stringsLength; | |
| utf8=spanBackUTF8Lengths+stringsLength; | |
| } else { | |
| // Store span lengths for only one span() variant. | |
| if(which&UTF8) { | |
| spanLengths=(uint8_t *)(utf8Lengths+stringsLength); | |
| utf8=spanLengths+stringsLength; | |
| } else { | |
| spanLengths=(uint8_t *)utf8Lengths; | |
| } | |
| spanBackLengths=spanUTF8Lengths=spanBackUTF8Lengths=spanLengths; | |
| } | |
| // Set the meta data and pSpanNotSet and write the UTF-8 strings. | |
| int32_t utf8Count=0; // Count UTF-8 bytes written so far. | |
| for(i=0; i<stringsLength; ++i) { | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| spanLength=spanSet.span(s16, length16, USET_SPAN_CONTAINED); | |
| if(spanLength<length16) { // Relevant string. | |
| if(which&UTF16) { | |
| if(which&CONTAINED) { | |
| if(which&FWD) { | |
| spanLengths[i]=makeSpanLengthByte(spanLength); | |
| } | |
| if(which&BACK) { | |
| spanLength=length16-spanSet.spanBack(s16, length16, USET_SPAN_CONTAINED); | |
| spanBackLengths[i]=makeSpanLengthByte(spanLength); | |
| } | |
| } else /* not CONTAINED, not all, but NOT_CONTAINED */ { | |
| spanLengths[i]=spanBackLengths[i]=0; // Only store a relevant/irrelevant flag. | |
| } | |
| } | |
| if(which&UTF8) { | |
| uint8_t *s8=utf8+utf8Count; | |
| int32_t length8=appendUTF8(s16, length16, s8, utf8Length-utf8Count); | |
| utf8Count+=utf8Lengths[i]=length8; | |
| if(length8==0) { // Irrelevant for UTF-8 because not representable in UTF-8. | |
| spanUTF8Lengths[i]=spanBackUTF8Lengths[i]=(uint8_t)ALL_CP_CONTAINED; | |
| } else { // Relevant for UTF-8. | |
| if(which&CONTAINED) { | |
| if(which&FWD) { | |
| spanLength=spanSet.spanUTF8((const char *)s8, length8, USET_SPAN_CONTAINED); | |
| spanUTF8Lengths[i]=makeSpanLengthByte(spanLength); | |
| } | |
| if(which&BACK) { | |
| spanLength=length8-spanSet.spanBackUTF8((const char *)s8, length8, USET_SPAN_CONTAINED); | |
| spanBackUTF8Lengths[i]=makeSpanLengthByte(spanLength); | |
| } | |
| } else /* not CONTAINED, not all, but NOT_CONTAINED */ { | |
| spanUTF8Lengths[i]=spanBackUTF8Lengths[i]=0; // Only store a relevant/irrelevant flag. | |
| } | |
| } | |
| } | |
| if(which&NOT_CONTAINED) { | |
| // Add string start and end code points to the spanNotSet so that | |
| // a span(while not contained) stops before any string. | |
| UChar32 c; | |
| if(which&FWD) { | |
| int32_t len=0; | |
| U16_NEXT(s16, len, length16, c); | |
| addToSpanNotSet(c); | |
| } | |
| if(which&BACK) { | |
| int32_t len=length16; | |
| U16_PREV(s16, 0, len, c); | |
| addToSpanNotSet(c); | |
| } | |
| } | |
| } else { // Irrelevant string. | |
| if(which&UTF8) { | |
| if(which&CONTAINED) { // Only necessary for LONGEST_MATCH. | |
| uint8_t *s8=utf8+utf8Count; | |
| int32_t length8=appendUTF8(s16, length16, s8, utf8Length-utf8Count); | |
| utf8Count+=utf8Lengths[i]=length8; | |
| } else { | |
| utf8Lengths[i]=0; | |
| } | |
| } | |
| if(all) { | |
| spanLengths[i]=spanBackLengths[i]= | |
| spanUTF8Lengths[i]=spanBackUTF8Lengths[i]= | |
| (uint8_t)ALL_CP_CONTAINED; | |
| } else { | |
| // All spanXYZLengths pointers contain the same address. | |
| spanLengths[i]=(uint8_t)ALL_CP_CONTAINED; | |
| } | |
| } | |
| } | |
| // Finish. | |
| if(all) { | |
| pSpanNotSet->freeze(); | |
| } | |
| } | |
| // Copy constructor. Assumes which==ALL for a frozen set. | |
| UnicodeSetStringSpan::UnicodeSetStringSpan(const UnicodeSetStringSpan &otherStringSpan, | |
| const UVector &newParentSetStrings) | |
| : spanSet(otherStringSpan.spanSet), pSpanNotSet(NULL), strings(newParentSetStrings), | |
| utf8Lengths(NULL), spanLengths(NULL), utf8(NULL), | |
| utf8Length(otherStringSpan.utf8Length), | |
| maxLength16(otherStringSpan.maxLength16), maxLength8(otherStringSpan.maxLength8), | |
| all(TRUE) { | |
| if(otherStringSpan.pSpanNotSet==&otherStringSpan.spanSet) { | |
| pSpanNotSet=&spanSet; | |
| } else { | |
| pSpanNotSet=otherStringSpan.pSpanNotSet->clone(); | |
| } | |
| // Allocate a block of meta data. | |
| // UTF-8 lengths, 4 sets of span lengths, UTF-8 strings. | |
| int32_t stringsLength=strings.size(); | |
| int32_t allocSize=stringsLength*(4+1+1+1+1)+utf8Length; | |
| if(allocSize<=(int32_t)sizeof(staticLengths)) { | |
| utf8Lengths=staticLengths; | |
| } else { | |
| utf8Lengths=(int32_t *)uprv_malloc(allocSize); | |
| if(utf8Lengths==NULL) { | |
| maxLength16=maxLength8=0; // Prevent usage by making needsStringSpanUTF16/8() return FALSE. | |
| return; // Out of memory. | |
| } | |
| } | |
| spanLengths=(uint8_t *)(utf8Lengths+stringsLength); | |
| utf8=spanLengths+stringsLength*4; | |
| uprv_memcpy(utf8Lengths, otherStringSpan.utf8Lengths, allocSize); | |
| } | |
| UnicodeSetStringSpan::~UnicodeSetStringSpan() { | |
| if(pSpanNotSet!=NULL && pSpanNotSet!=&spanSet) { | |
| delete pSpanNotSet; | |
| } | |
| if(utf8Lengths!=NULL && utf8Lengths!=staticLengths) { | |
| uprv_free(utf8Lengths); | |
| } | |
| } | |
| void UnicodeSetStringSpan::addToSpanNotSet(UChar32 c) { | |
| if(pSpanNotSet==NULL || pSpanNotSet==&spanSet) { | |
| if(spanSet.contains(c)) { | |
| return; // Nothing to do. | |
| } | |
| UnicodeSet *newSet=spanSet.cloneAsThawed(); | |
| if(newSet==NULL) { | |
| return; // Out of memory. | |
| } else { | |
| pSpanNotSet=newSet; | |
| } | |
| } | |
| pSpanNotSet->add(c); | |
| } | |
| // Compare strings without any argument checks. Requires length>0. | |
| static inline UBool | |
| matches16(const UChar *s, const UChar *t, int32_t length) { | |
| do { | |
| if(*s++!=*t++) { | |
| return FALSE; | |
| } | |
| } while(--length>0); | |
| return TRUE; | |
| } | |
| static inline UBool | |
| matches8(const uint8_t *s, const uint8_t *t, int32_t length) { | |
| do { | |
| if(*s++!=*t++) { | |
| return FALSE; | |
| } | |
| } while(--length>0); | |
| return TRUE; | |
| } | |
| // Compare 16-bit Unicode strings (which may be malformed UTF-16) | |
| // at code point boundaries. | |
| // That is, each edge of a match must not be in the middle of a surrogate pair. | |
| static inline UBool | |
| matches16CPB(const UChar *s, int32_t start, int32_t limit, const UChar *t, int32_t length) { | |
| s+=start; | |
| limit-=start; | |
| return matches16(s, t, length) && | |
| !(0<start && U16_IS_LEAD(s[-1]) && U16_IS_TRAIL(s[0])) && | |
| !(length<limit && U16_IS_LEAD(s[length-1]) && U16_IS_TRAIL(s[length])); | |
| } | |
| // Does the set contain the next code point? | |
| // If so, return its length; otherwise return its negative length. | |
| static inline int32_t | |
| spanOne(const UnicodeSet &set, const UChar *s, int32_t length) { | |
| UChar c=*s, c2; | |
| if(c>=0xd800 && c<=0xdbff && length>=2 && U16_IS_TRAIL(c2=s[1])) { | |
| return set.contains(U16_GET_SUPPLEMENTARY(c, c2)) ? 2 : -2; | |
| } | |
| return set.contains(c) ? 1 : -1; | |
| } | |
| static inline int32_t | |
| spanOneBack(const UnicodeSet &set, const UChar *s, int32_t length) { | |
| UChar c=s[length-1], c2; | |
| if(c>=0xdc00 && c<=0xdfff && length>=2 && U16_IS_LEAD(c2=s[length-2])) { | |
| return set.contains(U16_GET_SUPPLEMENTARY(c2, c)) ? 2 : -2; | |
| } | |
| return set.contains(c) ? 1 : -1; | |
| } | |
| static inline int32_t | |
| spanOneUTF8(const UnicodeSet &set, const uint8_t *s, int32_t length) { | |
| UChar32 c=*s; | |
| if(U8_IS_SINGLE(c)) { | |
| return set.contains(c) ? 1 : -1; | |
| } | |
| // Take advantage of non-ASCII fastpaths in U8_NEXT_OR_FFFD(). | |
| int32_t i=0; | |
| U8_NEXT_OR_FFFD(s, i, length, c); | |
| return set.contains(c) ? i : -i; | |
| } | |
| static inline int32_t | |
| spanOneBackUTF8(const UnicodeSet &set, const uint8_t *s, int32_t length) { | |
| UChar32 c=s[length-1]; | |
| if(U8_IS_SINGLE(c)) { | |
| return set.contains(c) ? 1 : -1; | |
| } | |
| int32_t i=length-1; | |
| c=utf8_prevCharSafeBody(s, 0, &i, c, -3); | |
| length-=i; | |
| return set.contains(c) ? length : -length; | |
| } | |
| /* | |
| * Note: In span() when spanLength==0 (after a string match, or at the beginning | |
| * after an empty code point span) and in spanNot() and spanNotUTF8(), | |
| * string matching could use a binary search | |
| * because all string matches are done from the same start index. | |
| * | |
| * For UTF-8, this would require a comparison function that returns UTF-16 order. | |
| * | |
| * This optimization should not be necessary for normal UnicodeSets because | |
| * most sets have no strings, and most sets with strings have | |
| * very few very short strings. | |
| * For cases with many strings, it might be better to use a different API | |
| * and implementation with a DFA (state machine). | |
| */ | |
| /* | |
| * Algorithm for span(USET_SPAN_CONTAINED) | |
| * | |
| * Theoretical algorithm: | |
| * - Iterate through the string, and at each code point boundary: | |
| * + If the code point there is in the set, then remember to continue after it. | |
| * + If a set string matches at the current position, then remember to continue after it. | |
| * + Either recursively span for each code point or string match, | |
| * or recursively span for all but the shortest one and | |
| * iteratively continue the span with the shortest local match. | |
| * + Remember the longest recursive span (the farthest end point). | |
| * + If there is no match at the current position, neither for the code point there | |
| * nor for any set string, then stop and return the longest recursive span length. | |
| * | |
| * Optimized implementation: | |
| * | |
| * (We assume that most sets will have very few very short strings. | |
| * A span using a string-less set is extremely fast.) | |
| * | |
| * Create and cache a spanSet which contains all of the single code points | |
| * of the original set but none of its strings. | |
| * | |
| * - Start with spanLength=spanSet.span(USET_SPAN_CONTAINED). | |
| * - Loop: | |
| * + Try to match each set string at the end of the spanLength. | |
| * ~ Set strings that start with set-contained code points must be matched | |
| * with a partial overlap because the recursive algorithm would have tried | |
| * to match them at every position. | |
| * ~ Set strings that entirely consist of set-contained code points | |
| * are irrelevant for span(USET_SPAN_CONTAINED) because the | |
| * recursive algorithm would continue after them anyway | |
| * and find the longest recursive match from their end. | |
| * ~ Rather than recursing, note each end point of a set string match. | |
| * + If no set string matched after spanSet.span(), then return | |
| * with where the spanSet.span() ended. | |
| * + If at least one set string matched after spanSet.span(), then | |
| * pop the shortest string match end point and continue | |
| * the loop, trying to match all set strings from there. | |
| * + If at least one more set string matched after a previous string match, | |
| * then test if the code point after the previous string match is also | |
| * contained in the set. | |
| * Continue the loop with the shortest end point of either this code point | |
| * or a matching set string. | |
| * + If no more set string matched after a previous string match, | |
| * then try another spanLength=spanSet.span(USET_SPAN_CONTAINED). | |
| * Stop if spanLength==0, otherwise continue the loop. | |
| * | |
| * By noting each end point of a set string match, | |
| * the function visits each string position at most once and finishes | |
| * in linear time. | |
| * | |
| * The recursive algorithm may visit the same string position many times | |
| * if multiple paths lead to it and finishes in exponential time. | |
| */ | |
| /* | |
| * Algorithm for span(USET_SPAN_SIMPLE) | |
| * | |
| * Theoretical algorithm: | |
| * - Iterate through the string, and at each code point boundary: | |
| * + If the code point there is in the set, then remember to continue after it. | |
| * + If a set string matches at the current position, then remember to continue after it. | |
| * + Continue from the farthest match position and ignore all others. | |
| * + If there is no match at the current position, | |
| * then stop and return the current position. | |
| * | |
| * Optimized implementation: | |
| * | |
| * (Same assumption and spanSet as above.) | |
| * | |
| * - Start with spanLength=spanSet.span(USET_SPAN_CONTAINED). | |
| * - Loop: | |
| * + Try to match each set string at the end of the spanLength. | |
| * ~ Set strings that start with set-contained code points must be matched | |
| * with a partial overlap because the standard algorithm would have tried | |
| * to match them earlier. | |
| * ~ Set strings that entirely consist of set-contained code points | |
| * must be matched with a full overlap because the longest-match algorithm | |
| * would hide set string matches that end earlier. | |
| * Such set strings need not be matched earlier inside the code point span | |
| * because the standard algorithm would then have continued after | |
| * the set string match anyway. | |
| * ~ Remember the longest set string match (farthest end point) from the earliest | |
| * starting point. | |
| * + If no set string matched after spanSet.span(), then return | |
| * with where the spanSet.span() ended. | |
| * + If at least one set string matched, then continue the loop after the | |
| * longest match from the earliest position. | |
| * + If no more set string matched after a previous string match, | |
| * then try another spanLength=spanSet.span(USET_SPAN_CONTAINED). | |
| * Stop if spanLength==0, otherwise continue the loop. | |
| */ | |
| int32_t UnicodeSetStringSpan::span(const UChar *s, int32_t length, USetSpanCondition spanCondition) const { | |
| if(spanCondition==USET_SPAN_NOT_CONTAINED) { | |
| return spanNot(s, length); | |
| } | |
| int32_t spanLength=spanSet.span(s, length, USET_SPAN_CONTAINED); | |
| if(spanLength==length) { | |
| return length; | |
| } | |
| // Consider strings; they may overlap with the span. | |
| OffsetList offsets; | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| // Use offset list to try all possibilities. | |
| offsets.setMaxLength(maxLength16); | |
| } | |
| int32_t pos=spanLength, rest=length-pos; | |
| int32_t i, stringsLength=strings.size(); | |
| for(;;) { | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| for(i=0; i<stringsLength; ++i) { | |
| int32_t overlap=spanLengths[i]; | |
| if(overlap==ALL_CP_CONTAINED) { | |
| continue; // Irrelevant string. | |
| } | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| // Try to match this string at pos-overlap..pos. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length16; | |
| // While contained: No point matching fully inside the code point span. | |
| U16_BACK_1(s16, 0, overlap); // Length of the string minus the last code point. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t inc=length16-overlap; // Keep overlap+inc==length16. | |
| for(;;) { | |
| if(inc>rest) { | |
| break; | |
| } | |
| // Try to match if the increment is not listed already. | |
| if(!offsets.containsOffset(inc) && matches16CPB(s, pos-overlap, length, s16, length16)) { | |
| if(inc==rest) { | |
| return length; // Reached the end of the string. | |
| } | |
| offsets.addOffset(inc); | |
| } | |
| if(overlap==0) { | |
| break; | |
| } | |
| --overlap; | |
| ++inc; | |
| } | |
| } | |
| } else /* USET_SPAN_SIMPLE */ { | |
| int32_t maxInc=0, maxOverlap=0; | |
| for(i=0; i<stringsLength; ++i) { | |
| int32_t overlap=spanLengths[i]; | |
| // For longest match, we do need to try to match even an all-contained string | |
| // to find the match from the earliest start. | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| // Try to match this string at pos-overlap..pos. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length16; | |
| // Longest match: Need to match fully inside the code point span | |
| // to find the match from the earliest start. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t inc=length16-overlap; // Keep overlap+inc==length16. | |
| for(;;) { | |
| if(inc>rest || overlap<maxOverlap) { | |
| break; | |
| } | |
| // Try to match if the string is longer or starts earlier. | |
| if( (overlap>maxOverlap || /* redundant overlap==maxOverlap && */ inc>maxInc) && | |
| matches16CPB(s, pos-overlap, length, s16, length16) | |
| ) { | |
| maxInc=inc; // Longest match from earliest start. | |
| maxOverlap=overlap; | |
| break; | |
| } | |
| --overlap; | |
| ++inc; | |
| } | |
| } | |
| if(maxInc!=0 || maxOverlap!=0) { | |
| // Longest-match algorithm, and there was a string match. | |
| // Simply continue after it. | |
| pos+=maxInc; | |
| rest-=maxInc; | |
| if(rest==0) { | |
| return length; // Reached the end of the string. | |
| } | |
| spanLength=0; // Match strings from after a string match. | |
| continue; | |
| } | |
| } | |
| // Finished trying to match all strings at pos. | |
| if(spanLength!=0 || pos==0) { | |
| // The position is after an unlimited code point span (spanLength!=0), | |
| // not after a string match. | |
| // The only position where spanLength==0 after a span is pos==0. | |
| // Otherwise, an unlimited code point span is only tried again when no | |
| // strings match, and if such a non-initial span fails we stop. | |
| if(offsets.isEmpty()) { | |
| return pos; // No strings matched after a span. | |
| } | |
| // Match strings from after the next string match. | |
| } else { | |
| // The position is after a string match (or a single code point). | |
| if(offsets.isEmpty()) { | |
| // No more strings matched after a previous string match. | |
| // Try another code point span from after the last string match. | |
| spanLength=spanSet.span(s+pos, rest, USET_SPAN_CONTAINED); | |
| if( spanLength==rest || // Reached the end of the string, or | |
| spanLength==0 // neither strings nor span progressed. | |
| ) { | |
| return pos+spanLength; | |
| } | |
| pos+=spanLength; | |
| rest-=spanLength; | |
| continue; // spanLength>0: Match strings from after a span. | |
| } else { | |
| // Try to match only one code point from after a string match if some | |
| // string matched beyond it, so that we try all possible positions | |
| // and don't overshoot. | |
| spanLength=spanOne(spanSet, s+pos, rest); | |
| if(spanLength>0) { | |
| if(spanLength==rest) { | |
| return length; // Reached the end of the string. | |
| } | |
| // Match strings after this code point. | |
| // There cannot be any increments below it because UnicodeSet strings | |
| // contain multiple code points. | |
| pos+=spanLength; | |
| rest-=spanLength; | |
| offsets.shift(spanLength); | |
| spanLength=0; | |
| continue; // Match strings from after a single code point. | |
| } | |
| // Match strings from after the next string match. | |
| } | |
| } | |
| int32_t minOffset=offsets.popMinimum(); | |
| pos+=minOffset; | |
| rest-=minOffset; | |
| spanLength=0; // Match strings from after a string match. | |
| } | |
| } | |
| int32_t UnicodeSetStringSpan::spanBack(const UChar *s, int32_t length, USetSpanCondition spanCondition) const { | |
| if(spanCondition==USET_SPAN_NOT_CONTAINED) { | |
| return spanNotBack(s, length); | |
| } | |
| int32_t pos=spanSet.spanBack(s, length, USET_SPAN_CONTAINED); | |
| if(pos==0) { | |
| return 0; | |
| } | |
| int32_t spanLength=length-pos; | |
| // Consider strings; they may overlap with the span. | |
| OffsetList offsets; | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| // Use offset list to try all possibilities. | |
| offsets.setMaxLength(maxLength16); | |
| } | |
| int32_t i, stringsLength=strings.size(); | |
| uint8_t *spanBackLengths=spanLengths; | |
| if(all) { | |
| spanBackLengths+=stringsLength; | |
| } | |
| for(;;) { | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| for(i=0; i<stringsLength; ++i) { | |
| int32_t overlap=spanBackLengths[i]; | |
| if(overlap==ALL_CP_CONTAINED) { | |
| continue; // Irrelevant string. | |
| } | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| // Try to match this string at pos-(length16-overlap)..pos-length16. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length16; | |
| // While contained: No point matching fully inside the code point span. | |
| int32_t len1=0; | |
| U16_FWD_1(s16, len1, overlap); | |
| overlap-=len1; // Length of the string minus the first code point. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t dec=length16-overlap; // Keep dec+overlap==length16. | |
| for(;;) { | |
| if(dec>pos) { | |
| break; | |
| } | |
| // Try to match if the decrement is not listed already. | |
| if(!offsets.containsOffset(dec) && matches16CPB(s, pos-dec, length, s16, length16)) { | |
| if(dec==pos) { | |
| return 0; // Reached the start of the string. | |
| } | |
| offsets.addOffset(dec); | |
| } | |
| if(overlap==0) { | |
| break; | |
| } | |
| --overlap; | |
| ++dec; | |
| } | |
| } | |
| } else /* USET_SPAN_SIMPLE */ { | |
| int32_t maxDec=0, maxOverlap=0; | |
| for(i=0; i<stringsLength; ++i) { | |
| int32_t overlap=spanBackLengths[i]; | |
| // For longest match, we do need to try to match even an all-contained string | |
| // to find the match from the latest end. | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| // Try to match this string at pos-(length16-overlap)..pos-length16. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length16; | |
| // Longest match: Need to match fully inside the code point span | |
| // to find the match from the latest end. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t dec=length16-overlap; // Keep dec+overlap==length16. | |
| for(;;) { | |
| if(dec>pos || overlap<maxOverlap) { | |
| break; | |
| } | |
| // Try to match if the string is longer or ends later. | |
| if( (overlap>maxOverlap || /* redundant overlap==maxOverlap && */ dec>maxDec) && | |
| matches16CPB(s, pos-dec, length, s16, length16) | |
| ) { | |
| maxDec=dec; // Longest match from latest end. | |
| maxOverlap=overlap; | |
| break; | |
| } | |
| --overlap; | |
| ++dec; | |
| } | |
| } | |
| if(maxDec!=0 || maxOverlap!=0) { | |
| // Longest-match algorithm, and there was a string match. | |
| // Simply continue before it. | |
| pos-=maxDec; | |
| if(pos==0) { | |
| return 0; // Reached the start of the string. | |
| } | |
| spanLength=0; // Match strings from before a string match. | |
| continue; | |
| } | |
| } | |
| // Finished trying to match all strings at pos. | |
| if(spanLength!=0 || pos==length) { | |
| // The position is before an unlimited code point span (spanLength!=0), | |
| // not before a string match. | |
| // The only position where spanLength==0 before a span is pos==length. | |
| // Otherwise, an unlimited code point span is only tried again when no | |
| // strings match, and if such a non-initial span fails we stop. | |
| if(offsets.isEmpty()) { | |
| return pos; // No strings matched before a span. | |
| } | |
| // Match strings from before the next string match. | |
| } else { | |
| // The position is before a string match (or a single code point). | |
| if(offsets.isEmpty()) { | |
| // No more strings matched before a previous string match. | |
| // Try another code point span from before the last string match. | |
| int32_t oldPos=pos; | |
| pos=spanSet.spanBack(s, oldPos, USET_SPAN_CONTAINED); | |
| spanLength=oldPos-pos; | |
| if( pos==0 || // Reached the start of the string, or | |
| spanLength==0 // neither strings nor span progressed. | |
| ) { | |
| return pos; | |
| } | |
| continue; // spanLength>0: Match strings from before a span. | |
| } else { | |
| // Try to match only one code point from before a string match if some | |
| // string matched beyond it, so that we try all possible positions | |
| // and don't overshoot. | |
| spanLength=spanOneBack(spanSet, s, pos); | |
| if(spanLength>0) { | |
| if(spanLength==pos) { | |
| return 0; // Reached the start of the string. | |
| } | |
| // Match strings before this code point. | |
| // There cannot be any decrements below it because UnicodeSet strings | |
| // contain multiple code points. | |
| pos-=spanLength; | |
| offsets.shift(spanLength); | |
| spanLength=0; | |
| continue; // Match strings from before a single code point. | |
| } | |
| // Match strings from before the next string match. | |
| } | |
| } | |
| pos-=offsets.popMinimum(); | |
| spanLength=0; // Match strings from before a string match. | |
| } | |
| } | |
| int32_t UnicodeSetStringSpan::spanUTF8(const uint8_t *s, int32_t length, USetSpanCondition spanCondition) const { | |
| if(spanCondition==USET_SPAN_NOT_CONTAINED) { | |
| return spanNotUTF8(s, length); | |
| } | |
| int32_t spanLength=spanSet.spanUTF8((const char *)s, length, USET_SPAN_CONTAINED); | |
| if(spanLength==length) { | |
| return length; | |
| } | |
| // Consider strings; they may overlap with the span. | |
| OffsetList offsets; | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| // Use offset list to try all possibilities. | |
| offsets.setMaxLength(maxLength8); | |
| } | |
| int32_t pos=spanLength, rest=length-pos; | |
| int32_t i, stringsLength=strings.size(); | |
| uint8_t *spanUTF8Lengths=spanLengths; | |
| if(all) { | |
| spanUTF8Lengths+=2*stringsLength; | |
| } | |
| for(;;) { | |
| const uint8_t *s8=utf8; | |
| int32_t length8; | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| for(i=0; i<stringsLength; ++i) { | |
| length8=utf8Lengths[i]; | |
| if(length8==0) { | |
| continue; // String not representable in UTF-8. | |
| } | |
| int32_t overlap=spanUTF8Lengths[i]; | |
| if(overlap==ALL_CP_CONTAINED) { | |
| s8+=length8; | |
| continue; // Irrelevant string. | |
| } | |
| // Try to match this string at pos-overlap..pos. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length8; | |
| // While contained: No point matching fully inside the code point span. | |
| U8_BACK_1(s8, 0, overlap); // Length of the string minus the last code point. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t inc=length8-overlap; // Keep overlap+inc==length8. | |
| for(;;) { | |
| if(inc>rest) { | |
| break; | |
| } | |
| // Try to match if the increment is not listed already. | |
| // Match at code point boundaries. (The UTF-8 strings were converted | |
| // from UTF-16 and are guaranteed to be well-formed.) | |
| if(!U8_IS_TRAIL(s[pos-overlap]) && | |
| !offsets.containsOffset(inc) && | |
| matches8(s+pos-overlap, s8, length8)) { | |
| if(inc==rest) { | |
| return length; // Reached the end of the string. | |
| } | |
| offsets.addOffset(inc); | |
| } | |
| if(overlap==0) { | |
| break; | |
| } | |
| --overlap; | |
| ++inc; | |
| } | |
| s8+=length8; | |
| } | |
| } else /* USET_SPAN_SIMPLE */ { | |
| int32_t maxInc=0, maxOverlap=0; | |
| for(i=0; i<stringsLength; ++i) { | |
| length8=utf8Lengths[i]; | |
| if(length8==0) { | |
| continue; // String not representable in UTF-8. | |
| } | |
| int32_t overlap=spanUTF8Lengths[i]; | |
| // For longest match, we do need to try to match even an all-contained string | |
| // to find the match from the earliest start. | |
| // Try to match this string at pos-overlap..pos. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length8; | |
| // Longest match: Need to match fully inside the code point span | |
| // to find the match from the earliest start. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t inc=length8-overlap; // Keep overlap+inc==length8. | |
| for(;;) { | |
| if(inc>rest || overlap<maxOverlap) { | |
| break; | |
| } | |
| // Try to match if the string is longer or starts earlier. | |
| // Match at code point boundaries. (The UTF-8 strings were converted | |
| // from UTF-16 and are guaranteed to be well-formed.) | |
| if(!U8_IS_TRAIL(s[pos-overlap]) && | |
| (overlap>maxOverlap || | |
| /* redundant overlap==maxOverlap && */ inc>maxInc) && | |
| matches8(s+pos-overlap, s8, length8)) { | |
| maxInc=inc; // Longest match from earliest start. | |
| maxOverlap=overlap; | |
| break; | |
| } | |
| --overlap; | |
| ++inc; | |
| } | |
| s8+=length8; | |
| } | |
| if(maxInc!=0 || maxOverlap!=0) { | |
| // Longest-match algorithm, and there was a string match. | |
| // Simply continue after it. | |
| pos+=maxInc; | |
| rest-=maxInc; | |
| if(rest==0) { | |
| return length; // Reached the end of the string. | |
| } | |
| spanLength=0; // Match strings from after a string match. | |
| continue; | |
| } | |
| } | |
| // Finished trying to match all strings at pos. | |
| if(spanLength!=0 || pos==0) { | |
| // The position is after an unlimited code point span (spanLength!=0), | |
| // not after a string match. | |
| // The only position where spanLength==0 after a span is pos==0. | |
| // Otherwise, an unlimited code point span is only tried again when no | |
| // strings match, and if such a non-initial span fails we stop. | |
| if(offsets.isEmpty()) { | |
| return pos; // No strings matched after a span. | |
| } | |
| // Match strings from after the next string match. | |
| } else { | |
| // The position is after a string match (or a single code point). | |
| if(offsets.isEmpty()) { | |
| // No more strings matched after a previous string match. | |
| // Try another code point span from after the last string match. | |
| spanLength=spanSet.spanUTF8((const char *)s+pos, rest, USET_SPAN_CONTAINED); | |
| if( spanLength==rest || // Reached the end of the string, or | |
| spanLength==0 // neither strings nor span progressed. | |
| ) { | |
| return pos+spanLength; | |
| } | |
| pos+=spanLength; | |
| rest-=spanLength; | |
| continue; // spanLength>0: Match strings from after a span. | |
| } else { | |
| // Try to match only one code point from after a string match if some | |
| // string matched beyond it, so that we try all possible positions | |
| // and don't overshoot. | |
| spanLength=spanOneUTF8(spanSet, s+pos, rest); | |
| if(spanLength>0) { | |
| if(spanLength==rest) { | |
| return length; // Reached the end of the string. | |
| } | |
| // Match strings after this code point. | |
| // There cannot be any increments below it because UnicodeSet strings | |
| // contain multiple code points. | |
| pos+=spanLength; | |
| rest-=spanLength; | |
| offsets.shift(spanLength); | |
| spanLength=0; | |
| continue; // Match strings from after a single code point. | |
| } | |
| // Match strings from after the next string match. | |
| } | |
| } | |
| int32_t minOffset=offsets.popMinimum(); | |
| pos+=minOffset; | |
| rest-=minOffset; | |
| spanLength=0; // Match strings from after a string match. | |
| } | |
| } | |
| int32_t UnicodeSetStringSpan::spanBackUTF8(const uint8_t *s, int32_t length, USetSpanCondition spanCondition) const { | |
| if(spanCondition==USET_SPAN_NOT_CONTAINED) { | |
| return spanNotBackUTF8(s, length); | |
| } | |
| int32_t pos=spanSet.spanBackUTF8((const char *)s, length, USET_SPAN_CONTAINED); | |
| if(pos==0) { | |
| return 0; | |
| } | |
| int32_t spanLength=length-pos; | |
| // Consider strings; they may overlap with the span. | |
| OffsetList offsets; | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| // Use offset list to try all possibilities. | |
| offsets.setMaxLength(maxLength8); | |
| } | |
| int32_t i, stringsLength=strings.size(); | |
| uint8_t *spanBackUTF8Lengths=spanLengths; | |
| if(all) { | |
| spanBackUTF8Lengths+=3*stringsLength; | |
| } | |
| for(;;) { | |
| const uint8_t *s8=utf8; | |
| int32_t length8; | |
| if(spanCondition==USET_SPAN_CONTAINED) { | |
| for(i=0; i<stringsLength; ++i) { | |
| length8=utf8Lengths[i]; | |
| if(length8==0) { | |
| continue; // String not representable in UTF-8. | |
| } | |
| int32_t overlap=spanBackUTF8Lengths[i]; | |
| if(overlap==ALL_CP_CONTAINED) { | |
| s8+=length8; | |
| continue; // Irrelevant string. | |
| } | |
| // Try to match this string at pos-(length8-overlap)..pos-length8. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length8; | |
| // While contained: No point matching fully inside the code point span. | |
| int32_t len1=0; | |
| U8_FWD_1(s8, len1, overlap); | |
| overlap-=len1; // Length of the string minus the first code point. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t dec=length8-overlap; // Keep dec+overlap==length8. | |
| for(;;) { | |
| if(dec>pos) { | |
| break; | |
| } | |
| // Try to match if the decrement is not listed already. | |
| // Match at code point boundaries. (The UTF-8 strings were converted | |
| // from UTF-16 and are guaranteed to be well-formed.) | |
| if( !U8_IS_TRAIL(s[pos-dec]) && | |
| !offsets.containsOffset(dec) && | |
| matches8(s+pos-dec, s8, length8) | |
| ) { | |
| if(dec==pos) { | |
| return 0; // Reached the start of the string. | |
| } | |
| offsets.addOffset(dec); | |
| } | |
| if(overlap==0) { | |
| break; | |
| } | |
| --overlap; | |
| ++dec; | |
| } | |
| s8+=length8; | |
| } | |
| } else /* USET_SPAN_SIMPLE */ { | |
| int32_t maxDec=0, maxOverlap=0; | |
| for(i=0; i<stringsLength; ++i) { | |
| length8=utf8Lengths[i]; | |
| if(length8==0) { | |
| continue; // String not representable in UTF-8. | |
| } | |
| int32_t overlap=spanBackUTF8Lengths[i]; | |
| // For longest match, we do need to try to match even an all-contained string | |
| // to find the match from the latest end. | |
| // Try to match this string at pos-(length8-overlap)..pos-length8. | |
| if(overlap>=LONG_SPAN) { | |
| overlap=length8; | |
| // Longest match: Need to match fully inside the code point span | |
| // to find the match from the latest end. | |
| } | |
| if(overlap>spanLength) { | |
| overlap=spanLength; | |
| } | |
| int32_t dec=length8-overlap; // Keep dec+overlap==length8. | |
| for(;;) { | |
| if(dec>pos || overlap<maxOverlap) { | |
| break; | |
| } | |
| // Try to match if the string is longer or ends later. | |
| // Match at code point boundaries. (The UTF-8 strings were converted | |
| // from UTF-16 and are guaranteed to be well-formed.) | |
| if( !U8_IS_TRAIL(s[pos-dec]) && | |
| (overlap>maxOverlap || /* redundant overlap==maxOverlap && */ dec>maxDec) && | |
| matches8(s+pos-dec, s8, length8) | |
| ) { | |
| maxDec=dec; // Longest match from latest end. | |
| maxOverlap=overlap; | |
| break; | |
| } | |
| --overlap; | |
| ++dec; | |
| } | |
| s8+=length8; | |
| } | |
| if(maxDec!=0 || maxOverlap!=0) { | |
| // Longest-match algorithm, and there was a string match. | |
| // Simply continue before it. | |
| pos-=maxDec; | |
| if(pos==0) { | |
| return 0; // Reached the start of the string. | |
| } | |
| spanLength=0; // Match strings from before a string match. | |
| continue; | |
| } | |
| } | |
| // Finished trying to match all strings at pos. | |
| if(spanLength!=0 || pos==length) { | |
| // The position is before an unlimited code point span (spanLength!=0), | |
| // not before a string match. | |
| // The only position where spanLength==0 before a span is pos==length. | |
| // Otherwise, an unlimited code point span is only tried again when no | |
| // strings match, and if such a non-initial span fails we stop. | |
| if(offsets.isEmpty()) { | |
| return pos; // No strings matched before a span. | |
| } | |
| // Match strings from before the next string match. | |
| } else { | |
| // The position is before a string match (or a single code point). | |
| if(offsets.isEmpty()) { | |
| // No more strings matched before a previous string match. | |
| // Try another code point span from before the last string match. | |
| int32_t oldPos=pos; | |
| pos=spanSet.spanBackUTF8((const char *)s, oldPos, USET_SPAN_CONTAINED); | |
| spanLength=oldPos-pos; | |
| if( pos==0 || // Reached the start of the string, or | |
| spanLength==0 // neither strings nor span progressed. | |
| ) { | |
| return pos; | |
| } | |
| continue; // spanLength>0: Match strings from before a span. | |
| } else { | |
| // Try to match only one code point from before a string match if some | |
| // string matched beyond it, so that we try all possible positions | |
| // and don't overshoot. | |
| spanLength=spanOneBackUTF8(spanSet, s, pos); | |
| if(spanLength>0) { | |
| if(spanLength==pos) { | |
| return 0; // Reached the start of the string. | |
| } | |
| // Match strings before this code point. | |
| // There cannot be any decrements below it because UnicodeSet strings | |
| // contain multiple code points. | |
| pos-=spanLength; | |
| offsets.shift(spanLength); | |
| spanLength=0; | |
| continue; // Match strings from before a single code point. | |
| } | |
| // Match strings from before the next string match. | |
| } | |
| } | |
| pos-=offsets.popMinimum(); | |
| spanLength=0; // Match strings from before a string match. | |
| } | |
| } | |
| /* | |
| * Algorithm for spanNot()==span(USET_SPAN_NOT_CONTAINED) | |
| * | |
| * Theoretical algorithm: | |
| * - Iterate through the string, and at each code point boundary: | |
| * + If the code point there is in the set, then return with the current position. | |
| * + If a set string matches at the current position, then return with the current position. | |
| * | |
| * Optimized implementation: | |
| * | |
| * (Same assumption as for span() above.) | |
| * | |
| * Create and cache a spanNotSet which contains all of the single code points | |
| * of the original set but none of its strings. | |
| * For each set string add its initial code point to the spanNotSet. | |
| * (Also add its final code point for spanNotBack().) | |
| * | |
| * - Loop: | |
| * + Do spanLength=spanNotSet.span(USET_SPAN_NOT_CONTAINED). | |
| * + If the current code point is in the original set, then | |
| * return the current position. | |
| * + If any set string matches at the current position, then | |
| * return the current position. | |
| * + If there is no match at the current position, neither for the code point there | |
| * nor for any set string, then skip this code point and continue the loop. | |
| * This happens for set-string-initial code points that were added to spanNotSet | |
| * when there is not actually a match for such a set string. | |
| */ | |
| int32_t UnicodeSetStringSpan::spanNot(const UChar *s, int32_t length) const { | |
| int32_t pos=0, rest=length; | |
| int32_t i, stringsLength=strings.size(); | |
| do { | |
| // Span until we find a code point from the set, | |
| // or a code point that starts or ends some string. | |
| i=pSpanNotSet->span(s+pos, rest, USET_SPAN_NOT_CONTAINED); | |
| if(i==rest) { | |
| return length; // Reached the end of the string. | |
| } | |
| pos+=i; | |
| rest-=i; | |
| // Check whether the current code point is in the original set, | |
| // without the string starts and ends. | |
| int32_t cpLength=spanOne(spanSet, s+pos, rest); | |
| if(cpLength>0) { | |
| return pos; // There is a set element at pos. | |
| } | |
| // Try to match the strings at pos. | |
| for(i=0; i<stringsLength; ++i) { | |
| if(spanLengths[i]==ALL_CP_CONTAINED) { | |
| continue; // Irrelevant string. | |
| } | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| if(length16<=rest && matches16CPB(s, pos, length, s16, length16)) { | |
| return pos; // There is a set element at pos. | |
| } | |
| } | |
| // The span(while not contained) ended on a string start/end which is | |
| // not in the original set. Skip this code point and continue. | |
| // cpLength<0 | |
| pos-=cpLength; | |
| rest+=cpLength; | |
| } while(rest!=0); | |
| return length; // Reached the end of the string. | |
| } | |
| int32_t UnicodeSetStringSpan::spanNotBack(const UChar *s, int32_t length) const { | |
| int32_t pos=length; | |
| int32_t i, stringsLength=strings.size(); | |
| do { | |
| // Span until we find a code point from the set, | |
| // or a code point that starts or ends some string. | |
| pos=pSpanNotSet->spanBack(s, pos, USET_SPAN_NOT_CONTAINED); | |
| if(pos==0) { | |
| return 0; // Reached the start of the string. | |
| } | |
| // Check whether the current code point is in the original set, | |
| // without the string starts and ends. | |
| int32_t cpLength=spanOneBack(spanSet, s, pos); | |
| if(cpLength>0) { | |
| return pos; // There is a set element at pos. | |
| } | |
| // Try to match the strings at pos. | |
| for(i=0; i<stringsLength; ++i) { | |
| // Use spanLengths rather than a spanBackLengths pointer because | |
| // it is easier and we only need to know whether the string is irrelevant | |
| // which is the same in either array. | |
| if(spanLengths[i]==ALL_CP_CONTAINED) { | |
| continue; // Irrelevant string. | |
| } | |
| const UnicodeString &string=*(const UnicodeString *)strings.elementAt(i); | |
| const UChar *s16=string.getBuffer(); | |
| int32_t length16=string.length(); | |
| if(length16<=pos && matches16CPB(s, pos-length16, length, s16, length16)) { | |
| return pos; // There is a set element at pos. | |
| } | |
| } | |
| // The span(while not contained) ended on a string start/end which is | |
| // not in the original set. Skip this code point and continue. | |
| // cpLength<0 | |
| pos+=cpLength; | |
| } while(pos!=0); | |
| return 0; // Reached the start of the string. | |
| } | |
| int32_t UnicodeSetStringSpan::spanNotUTF8(const uint8_t *s, int32_t length) const { | |
| int32_t pos=0, rest=length; | |
| int32_t i, stringsLength=strings.size(); | |
| uint8_t *spanUTF8Lengths=spanLengths; | |
| if(all) { | |
| spanUTF8Lengths+=2*stringsLength; | |
| } | |
| do { | |
| // Span until we find a code point from the set, | |
| // or a code point that starts or ends some string. | |
| i=pSpanNotSet->spanUTF8((const char *)s+pos, rest, USET_SPAN_NOT_CONTAINED); | |
| if(i==rest) { | |
| return length; // Reached the end of the string. | |
| } | |
| pos+=i; | |
| rest-=i; | |
| // Check whether the current code point is in the original set, | |
| // without the string starts and ends. | |
| int32_t cpLength=spanOneUTF8(spanSet, s+pos, rest); | |
| if(cpLength>0) { | |
| return pos; // There is a set element at pos. | |
| } | |
| // Try to match the strings at pos. | |
| const uint8_t *s8=utf8; | |
| int32_t length8; | |
| for(i=0; i<stringsLength; ++i) { | |
| length8=utf8Lengths[i]; | |
| // ALL_CP_CONTAINED: Irrelevant string. | |
| if(length8!=0 && spanUTF8Lengths[i]!=ALL_CP_CONTAINED && length8<=rest && matches8(s+pos, s8, length8)) { | |
| return pos; // There is a set element at pos. | |
| } | |
| s8+=length8; | |
| } | |
| // The span(while not contained) ended on a string start/end which is | |
| // not in the original set. Skip this code point and continue. | |
| // cpLength<0 | |
| pos-=cpLength; | |
| rest+=cpLength; | |
| } while(rest!=0); | |
| return length; // Reached the end of the string. | |
| } | |
| int32_t UnicodeSetStringSpan::spanNotBackUTF8(const uint8_t *s, int32_t length) const { | |
| int32_t pos=length; | |
| int32_t i, stringsLength=strings.size(); | |
| uint8_t *spanBackUTF8Lengths=spanLengths; | |
| if(all) { | |
| spanBackUTF8Lengths+=3*stringsLength; | |
| } | |
| do { | |
| // Span until we find a code point from the set, | |
| // or a code point that starts or ends some string. | |
| pos=pSpanNotSet->spanBackUTF8((const char *)s, pos, USET_SPAN_NOT_CONTAINED); | |
| if(pos==0) { | |
| return 0; // Reached the start of the string. | |
| } | |
| // Check whether the current code point is in the original set, | |
| // without the string starts and ends. | |
| int32_t cpLength=spanOneBackUTF8(spanSet, s, pos); | |
| if(cpLength>0) { | |
| return pos; // There is a set element at pos. | |
| } | |
| // Try to match the strings at pos. | |
| const uint8_t *s8=utf8; | |
| int32_t length8; | |
| for(i=0; i<stringsLength; ++i) { | |
| length8=utf8Lengths[i]; | |
| // ALL_CP_CONTAINED: Irrelevant string. | |
| if(length8!=0 && spanBackUTF8Lengths[i]!=ALL_CP_CONTAINED && length8<=pos && matches8(s+pos-length8, s8, length8)) { | |
| return pos; // There is a set element at pos. | |
| } | |
| s8+=length8; | |
| } | |
| // The span(while not contained) ended on a string start/end which is | |
| // not in the original set. Skip this code point and continue. | |
| // cpLength<0 | |
| pos+=cpLength; | |
| } while(pos!=0); | |
| return 0; // Reached the start of the string. | |
| } | |
| U_NAMESPACE_END |