diff -r 000000000000 -r 6474c204b198 intl/icu/source/common/unisetspan.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/intl/icu/source/common/unisetspan.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,1510 @@ +/* +****************************************************************************** +* +* Copyright (C) 2007-2012, International Business Machines +* Corporation and others. All Rights Reserved. +* +****************************************************************************** +* file name: unisetspan.cpp +* encoding: US-ASCII +* tab size: 8 (not used) +* indentation:4 +* +* created on: 2007mar01 +* created by: Markus W. Scherer +*/ + +#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(++imaxLength16) { + 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; ifreeze(); + } +} + +// 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=(UnicodeSet *)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=(UnicodeSet *)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=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((int8_t)c>=0) { + 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((int8_t)c>=0) { + 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=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=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 || overlapmaxOverlap || /* 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=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=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 || overlapmaxOverlap || /* 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=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=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 || overlapmaxOverlap || /* 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=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=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 || overlapmaxOverlap || /* 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; ispanBack(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; ispanUTF8((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; ispanBackUTF8((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