X-Git-Url: https://git.saurik.com/apple/icu.git/blobdiff_plain/374ca955a76ecab1204ca8bfa63ff9238d998416..b331163bffd790ced0e88b73f44f86d49ccc48a5:/icuSources/i18n/usearch.cpp diff --git a/icuSources/i18n/usearch.cpp b/icuSources/i18n/usearch.cpp index 8c14c0b9..1ced2f15 100644 --- a/icuSources/i18n/usearch.cpp +++ b/icuSources/i18n/usearch.cpp @@ -1,6 +1,6 @@ /* ********************************************************************** -* Copyright (C) 2001-2004 IBM and others. All rights reserved. +* Copyright (C) 2001-2015 IBM and others. All rights reserved. ********************************************************************** * Date Name Description * 07/02/2001 synwee Creation. @@ -9,16 +9,24 @@ #include "unicode/utypes.h" -#if !UCONFIG_NO_COLLATION +#if !UCONFIG_NO_COLLATION && !UCONFIG_NO_BREAK_ITERATION #include "unicode/usearch.h" #include "unicode/ustring.h" #include "unicode/uchar.h" -#include "unormimp.h" -#include "ucol_imp.h" +#include "unicode/utf16.h" +#include "normalizer2impl.h" #include "usrchimp.h" #include "cmemory.h" #include "ucln_in.h" +#include "uassert.h" +#include "ustr_imp.h" + +U_NAMESPACE_USE + +// don't use Boyer-Moore +// (and if we decide to turn this on again there are several new TODOs that will need to be addressed) +#define BOYER_MOORE 0 // internal definition --------------------------------------------------- @@ -26,7 +34,7 @@ #define SECOND_LAST_BYTE_SHIFT_ 8 #define SUPPLEMENTARY_MIN_VALUE_ 0x10000 -static const uint16_t *FCD_ = NULL; +static const Normalizer2Impl *g_nfcImpl = NULL; // internal methods ------------------------------------------------- @@ -36,17 +44,14 @@ static const uint16_t *FCD_ = NULL; * @param coleiter collation element iterator * @param offset to set */ -static +static inline void setColEIterOffset(UCollationElements *elems, int32_t offset) { - collIterate *ci = &(elems->iteratordata_); - ci->pos = ci->string + offset; - ci->CEpos = ci->toReturn = ci->CEs; - if (ci->flags & UCOL_ITER_INNORMBUF) { - ci->flags = ci->origFlags; - } - ci->fcdPosition = NULL; + // Note: Not "fast" any more after the 2013 collation rewrite. + // We do not want to expose more internals than necessary. + UErrorCode status = U_ZERO_ERROR; + ucol_setOffset(elems, offset, &status); } /** @@ -55,16 +60,16 @@ inline void setColEIterOffset(UCollationElements *elems, * @return collation element mask */ static -inline uint32_t getMask(UCollationStrength strength) +inline uint32_t getMask(UCollationStrength strength) { - switch (strength) + switch (strength) { case UCOL_PRIMARY: return UCOL_PRIMARYORDERMASK; case UCOL_SECONDARY: return UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK; default: - return UCOL_TERTIARYORDERMASK | UCOL_SECONDARYORDERMASK | + return UCOL_TERTIARYORDERMASK | UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK; } } @@ -75,7 +80,7 @@ inline uint32_t getMask(UCollationStrength strength) * @return collapsed version of the collation element */ static -inline int hash(uint32_t ce) +inline int hash(uint32_t ce) { // the old value UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_ does not work // well with the new collation where most of the latin 1 characters @@ -87,7 +92,7 @@ inline int hash(uint32_t ce) U_CDECL_BEGIN static UBool U_CALLCONV usearch_cleanup(void) { - FCD_ = NULL; + g_nfcImpl = NULL; return TRUE; } U_CDECL_END @@ -95,14 +100,14 @@ U_CDECL_END /** * Initializing the fcd tables. * Internal method, status assumed to be a success. -* @param status output error if any, caller to check status before calling +* @param status output error if any, caller to check status before calling * method, status assumed to be success when passed in. */ static -inline void initializeFCD(UErrorCode *status) +inline void initializeFCD(UErrorCode *status) { - if (FCD_ == NULL) { - FCD_ = unorm_getFCDTrie(status); + if (g_nfcImpl == NULL) { + g_nfcImpl = Normalizer2Factory::getNFCImpl(*status); ucln_i18n_registerCleanup(UCLN_I18N_USEARCH, usearch_cleanup); } } @@ -111,40 +116,27 @@ inline void initializeFCD(UErrorCode *status) * Gets the fcd value for a character at the argument index. * This method takes into accounts of the supplementary characters. * @param str UTF16 string where character for fcd retrieval resides -* @param offset position of the character whose fcd is to be retrieved, to be -* overwritten with the next character position, taking +* @param offset position of the character whose fcd is to be retrieved, to be +* overwritten with the next character position, taking * surrogate characters into consideration. * @param strlength length of the argument string * @return fcd value */ static -inline uint16_t getFCD(const UChar *str, int32_t *offset, +uint16_t getFCD(const UChar *str, int32_t *offset, int32_t strlength) { - int32_t temp = *offset; - uint16_t result; - UChar ch = str[temp]; - result = unorm_getFCD16(FCD_, ch); - temp ++; - - if (result && temp != strlength && UTF_IS_FIRST_SURROGATE(ch)) { - ch = str[temp]; - if (UTF_IS_SECOND_SURROGATE(ch)) { - result = unorm_getFCD16FromSurrogatePair(FCD_, result, ch); - temp ++; - } else { - result = 0; - } - } - *offset = temp; + const UChar *temp = str + *offset; + uint16_t result = g_nfcImpl->nextFCD16(temp, str + strlength); + *offset = (int32_t)(temp - str); return result; } /** -* Getting the modified collation elements taking into account the collation +* Getting the modified collation elements taking into account the collation * attributes * @param strsrch string search data -* @param sourcece +* @param sourcece * @return the modified collation element */ static @@ -154,7 +146,7 @@ inline int32_t getCE(const UStringSearch *strsrch, uint32_t sourcece) // is a preprocessed mask that takes into account case options. since // we are only concerned with exact matches, we don't need that. sourcece &= strsrch->ceMask; - + if (strsrch->toShift) { // alternate handling here, since only the 16 most significant digits // is only used, we can safely do a compare without masking @@ -162,28 +154,30 @@ inline int32_t getCE(const UStringSearch *strsrch, uint32_t sourcece) // no shifting to quartenary is required since all primary values // less than variabletop will need to be masked off anyway. if (strsrch->variableTop > sourcece) { - if (strsrch->strength == UCOL_QUATERNARY) { + if (strsrch->strength >= UCOL_QUATERNARY) { sourcece &= UCOL_PRIMARYORDERMASK; } - else { + else { sourcece = UCOL_IGNORABLE; } } + } else if (strsrch->strength >= UCOL_QUATERNARY && sourcece == UCOL_IGNORABLE) { + sourcece = 0xFFFF; } return sourcece; } -/** +/** * Allocate a memory and returns NULL if it failed. * Internal method, status assumed to be a success. * @param size to allocate -* @param status output error if any, caller to check status before calling +* @param status output error if any, caller to check status before calling * method, status assumed to be success when passed in. * @return newly allocated array, NULL otherwise */ static -inline void * allocateMemory(uint32_t size, UErrorCode *status) +inline void * allocateMemory(uint32_t size, UErrorCode *status) { uint32_t *result = (uint32_t *)uprv_malloc(size); if (result == NULL) { @@ -194,27 +188,27 @@ inline void * allocateMemory(uint32_t size, UErrorCode *status) /** * Adds a uint32_t value to a destination array. -* Creates a new array if we run out of space. The caller will have to +* Creates a new array if we run out of space. The caller will have to * manually deallocate the newly allocated array. -* Internal method, status assumed to be success, caller has to check status -* before calling this method. destination not to be NULL and has at least +* Internal method, status assumed to be success, caller has to check status +* before calling this method. destination not to be NULL and has at least * size destinationlength. * @param destination target array * @param offset destination offset to add value * @param destinationlength target array size, return value for the new size * @param value to be added * @param increments incremental size expected -* @param status output error if any, caller to check status before calling +* @param status output error if any, caller to check status before calling * method, status assumed to be success when passed in. * @return new destination array, destination if there was no new allocation */ static -inline int32_t * addTouint32_tArray(int32_t *destination, - uint32_t offset, - uint32_t *destinationlength, +inline int32_t * addTouint32_tArray(int32_t *destination, + uint32_t offset, + uint32_t *destinationlength, uint32_t value, - uint32_t increments, - UErrorCode *status) + uint32_t increments, + UErrorCode *status) { uint32_t newlength = *destinationlength; if (offset + 1 == newlength) { @@ -232,46 +226,91 @@ inline int32_t * addTouint32_tArray(int32_t *destination, return destination; } +/** +* Adds a uint64_t value to a destination array. +* Creates a new array if we run out of space. The caller will have to +* manually deallocate the newly allocated array. +* Internal method, status assumed to be success, caller has to check status +* before calling this method. destination not to be NULL and has at least +* size destinationlength. +* @param destination target array +* @param offset destination offset to add value +* @param destinationlength target array size, return value for the new size +* @param value to be added +* @param increments incremental size expected +* @param status output error if any, caller to check status before calling +* method, status assumed to be success when passed in. +* @return new destination array, destination if there was no new allocation +*/ +static +inline int64_t * addTouint64_tArray(int64_t *destination, + uint32_t offset, + uint32_t *destinationlength, + uint64_t value, + uint32_t increments, + UErrorCode *status) +{ + uint32_t newlength = *destinationlength; + if (offset + 1 == newlength) { + newlength += increments; + int64_t *temp = (int64_t *)allocateMemory( + sizeof(int64_t) * newlength, status); + + if (U_FAILURE(*status)) { + return NULL; + } + + uprv_memcpy(temp, destination, sizeof(int64_t) * offset); + *destinationlength = newlength; + destination = temp; + } + + destination[offset] = value; + + return destination; +} + /** * Initializing the ce table for a pattern. * Stores non-ignorable collation keys. -* Table size will be estimated by the size of the pattern text. Table -* expansion will be perform as we go along. Adding 1 to ensure that the table +* Table size will be estimated by the size of the pattern text. Table +* expansion will be perform as we go along. Adding 1 to ensure that the table * size definitely increases. * Internal method, status assumed to be a success. * @param strsrch string search data -* @param status output error if any, caller to check status before calling +* @param status output error if any, caller to check status before calling * method, status assumed to be success when passed in. -* @return total number of expansions +* @return total number of expansions */ static -inline uint16_t initializePatternCETable(UStringSearch *strsrch, +inline uint16_t initializePatternCETable(UStringSearch *strsrch, UErrorCode *status) { UPattern *pattern = &(strsrch->pattern); uint32_t cetablesize = INITIAL_ARRAY_SIZE_; - int32_t *cetable = pattern->CEBuffer; + int32_t *cetable = pattern->cesBuffer; uint32_t patternlength = pattern->textLength; UCollationElements *coleiter = strsrch->utilIter; - + if (coleiter == NULL) { - coleiter = ucol_openElements(strsrch->collator, pattern->text, + coleiter = ucol_openElements(strsrch->collator, pattern->text, patternlength, status); - // status will be checked in ucol_next(..) later and if it is an - // error UCOL_NULLORDER the result of ucol_next(..) and 0 will be + // status will be checked in ucol_next(..) later and if it is an + // error UCOL_NULLORDER the result of ucol_next(..) and 0 will be // returned. strsrch->utilIter = coleiter; } else { - uprv_init_collIterate(strsrch->collator, pattern->text, - pattern->textLength, - &coleiter->iteratordata_); + ucol_setText(coleiter, pattern->text, pattern->textLength, status); } - - if (pattern->CE != cetable && pattern->CE) { - uprv_free(pattern->CE); + if(U_FAILURE(*status)) { + return 0; } - + + if (pattern->ces != cetable && pattern->ces) { + uprv_free(pattern->ces); + } + uint16_t offset = 0; uint16_t result = 0; int32_t ce; @@ -280,15 +319,15 @@ inline uint16_t initializePatternCETable(UStringSearch *strsrch, U_SUCCESS(*status)) { uint32_t newce = getCE(strsrch, ce); if (newce) { - int32_t *temp = addTouint32_tArray(cetable, offset, &cetablesize, + int32_t *temp = addTouint32_tArray(cetable, offset, &cetablesize, newce, - patternlength - ucol_getOffset(coleiter) + 1, + patternlength - ucol_getOffset(coleiter) + 1, status); if (U_FAILURE(*status)) { return 0; } offset ++; - if (cetable != temp && cetable != pattern->CEBuffer) { + if (cetable != temp && cetable != pattern->cesBuffer) { uprv_free(cetable); } cetable = temp; @@ -297,8 +336,85 @@ inline uint16_t initializePatternCETable(UStringSearch *strsrch, } cetable[offset] = 0; - pattern->CE = cetable; - pattern->CELength = offset; + pattern->ces = cetable; + pattern->cesLength = offset; + + return result; +} + +/** +* Initializing the pce table for a pattern. +* Stores non-ignorable collation keys. +* Table size will be estimated by the size of the pattern text. Table +* expansion will be perform as we go along. Adding 1 to ensure that the table +* size definitely increases. +* Internal method, status assumed to be a success. +* @param strsrch string search data +* @param status output error if any, caller to check status before calling +* method, status assumed to be success when passed in. +* @return total number of expansions +*/ +static +inline uint16_t initializePatternPCETable(UStringSearch *strsrch, + UErrorCode *status) +{ + UPattern *pattern = &(strsrch->pattern); + uint32_t pcetablesize = INITIAL_ARRAY_SIZE_; + int64_t *pcetable = pattern->pcesBuffer; + uint32_t patternlength = pattern->textLength; + UCollationElements *coleiter = strsrch->utilIter; + + if (coleiter == NULL) { + coleiter = ucol_openElements(strsrch->collator, pattern->text, + patternlength, status); + // status will be checked in ucol_next(..) later and if it is an + // error UCOL_NULLORDER the result of ucol_next(..) and 0 will be + // returned. + strsrch->utilIter = coleiter; + } else { + ucol_setText(coleiter, pattern->text, pattern->textLength, status); + } + if(U_FAILURE(*status)) { + return 0; + } + + if (pattern->pces != pcetable && pattern->pces != NULL) { + uprv_free(pattern->pces); + } + + uint16_t offset = 0; + uint16_t result = 0; + int64_t pce; + + icu::UCollationPCE iter(coleiter); + + // ** Should processed CEs be signed or unsigned? + // ** (the rest of the code in this file seems to play fast-and-loose with + // ** whether a CE is signed or unsigned. For example, look at routine above this one.) + while ((pce = iter.nextProcessed(NULL, NULL, status)) != UCOL_PROCESSED_NULLORDER && + U_SUCCESS(*status)) { + int64_t *temp = addTouint64_tArray(pcetable, offset, &pcetablesize, + pce, + patternlength - ucol_getOffset(coleiter) + 1, + status); + + if (U_FAILURE(*status)) { + return 0; + } + + offset += 1; + + if (pcetable != temp && pcetable != pattern->pcesBuffer) { + uprv_free(pcetable); + } + + pcetable = temp; + //result += (uint16_t)(ucol_getMaxExpansion(coleiter, ce) - 1); + } + + pcetable[offset] = 0; + pattern->pces = pcetable; + pattern->pcesLength = offset; return result; } @@ -307,32 +423,49 @@ inline uint16_t initializePatternCETable(UStringSearch *strsrch, * Initializes the pattern struct. * Internal method, status assumed to be success. * @param strsrch UStringSearch data storage -* @param status output error if any, caller to check status before calling +* @param status output error if any, caller to check status before calling * method, status assumed to be success when passed in. * @return expansionsize the total expansion size of the pattern -*/ +*/ static -inline int16_t initializePattern(UStringSearch *strsrch, UErrorCode *status) +inline int16_t initializePattern(UStringSearch *strsrch, UErrorCode *status) { + if (U_FAILURE(*status)) { return 0; } UPattern *pattern = &(strsrch->pattern); const UChar *patterntext = pattern->text; int32_t length = pattern->textLength; int32_t index = 0; - pattern->hasPrefixAccents = getFCD(patterntext, &index, length) >> - SECOND_LAST_BYTE_SHIFT_; - index = length; - UTF_BACK_1(patterntext, 0, index); - pattern->hasSuffixAccents = getFCD(patterntext, &index, length) & - LAST_BYTE_MASK_; + // Since the strength is primary, accents are ignored in the pattern. + if (strsrch->strength == UCOL_PRIMARY) { + pattern->hasPrefixAccents = 0; + pattern->hasSuffixAccents = 0; + } else { + pattern->hasPrefixAccents = getFCD(patterntext, &index, length) >> + SECOND_LAST_BYTE_SHIFT_; + index = length; + U16_BACK_1(patterntext, 0, index); + pattern->hasSuffixAccents = getFCD(patterntext, &index, length) & + LAST_BYTE_MASK_; + } + + // ** HACK ** + if (strsrch->pattern.pces != NULL) { + if (strsrch->pattern.pces != strsrch->pattern.pcesBuffer) { + uprv_free(strsrch->pattern.pces); + } + + strsrch->pattern.pces = NULL; + } + // since intializePattern is an internal method status is a success. - return initializePatternCETable(strsrch, status); + return initializePatternCETable(strsrch, status); } /** * Initializing shift tables, with the default values. * If a corresponding default value is 0, the shift table is not set. -* @param shift table for forwards shift +* @param shift table for forwards shift * @param backshift table for backwards shift * @param cetable table containing pattern ce * @param cesize size of the pattern ces @@ -341,15 +474,15 @@ inline int16_t initializePattern(UStringSearch *strsrch, UErrorCode *status) * @param defaultbackward the default backward value */ static -inline void setShiftTable(int16_t shift[], int16_t backshift[], - int32_t *cetable, int32_t cesize, +inline void setShiftTable(int16_t shift[], int16_t backshift[], + int32_t *cetable, int32_t cesize, int16_t expansionsize, int16_t defaultforward, int16_t defaultbackward) { - // estimate the value to shift. to do that we estimate the smallest + // estimate the value to shift. to do that we estimate the smallest // number of characters to give the relevant ces, ie approximately - // the number of ces minus their expansion, since expansions can come + // the number of ces minus their expansion, since expansions can come // from a character. int32_t count; for (count = 0; count < MAX_TABLE_SIZE_; count ++) { @@ -364,13 +497,13 @@ inline void setShiftTable(int16_t shift[], int16_t backshift[], shift[hash(cetable[cesize])] = 1; // for ignorables we just shift by one. see test examples. shift[hash(0)] = 1; - + for (count = 0; count < MAX_TABLE_SIZE_; count ++) { backshift[count] = defaultbackward; } for (count = cesize; count > 0; count --) { // the original value count does not seem to work - backshift[hash(cetable[count])] = count > expansionsize ? + backshift[hash(cetable[count])] = count > expansionsize ? (int16_t)(count - expansionsize) : 1; } backshift[hash(cetable[0])] = 1; @@ -383,19 +516,19 @@ inline void setShiftTable(int16_t shift[], int16_t backshift[], * The canonical match will only be performed after the default match fails. * For both cases we need to remember the size of the composed and decomposed * versions of the string. Since the Boyer-Moore shift calculations shifts by -* a number of characters in the text and tries to match the pattern from that -* offset, the shift value can not be too large in case we miss some -* characters. To choose a right shift size, we estimate the NFC form of the -* and use its size as a shift guide. The NFC form should be the small +* a number of characters in the text and tries to match the pattern from that +* offset, the shift value can not be too large in case we miss some +* characters. To choose a right shift size, we estimate the NFC form of the +* and use its size as a shift guide. The NFC form should be the small * possible representation of the pattern. Anyways, we'll err on the smaller * shift size. Hence the calculation for minlength. -* Canonical match will be performed slightly differently. We'll split the -* pattern into 3 parts, the prefix accents (PA), the middle string bounded by -* the first and last base character (MS), the ending accents (EA). Matches +* Canonical match will be performed slightly differently. We'll split the +* pattern into 3 parts, the prefix accents (PA), the middle string bounded by +* the first and last base character (MS), the ending accents (EA). Matches * will be done on MS first, and only when we match MS then some processing * will be required for the prefix and end accents in order to determine if -* they match PA and EA. Hence the default shift values -* for the canonical match will take the size of either end's accent into +* they match PA and EA. Hence the default shift values +* for the canonical match will take the size of either end's accent into * consideration. Forwards search will take the end accents into consideration * for the default shift values and the backwards search will take the prefix * accents into consideration. @@ -404,70 +537,102 @@ inline void setShiftTable(int16_t shift[], int16_t backshift[], * @param strsrch UStringSearch data storage * @param status for output errors if it occurs, status is assumed to be a * success when it is passed in. -*/ +*/ static -inline void initialize(UStringSearch *strsrch, UErrorCode *status) +inline void initialize(UStringSearch *strsrch, UErrorCode *status) { - int16_t expandlength = initializePattern(strsrch, status); - if (U_SUCCESS(*status) && strsrch->pattern.CELength > 0) { + int16_t expandlength = initializePattern(strsrch, status); + if (U_SUCCESS(*status) && strsrch->pattern.cesLength > 0) { UPattern *pattern = &strsrch->pattern; - int32_t cesize = pattern->CELength; + int32_t cesize = pattern->cesLength; - int16_t minlength = cesize > expandlength + int16_t minlength = cesize > expandlength ? (int16_t)cesize - expandlength : 1; pattern->defaultShiftSize = minlength; - setShiftTable(pattern->shift, pattern->backShift, pattern->CE, + setShiftTable(pattern->shift, pattern->backShift, pattern->ces, cesize, expandlength, minlength, minlength); return; } strsrch->pattern.defaultShiftSize = 0; } +#if BOYER_MOORE +/** +* Check to make sure that the match length is at the end of the character by +* using the breakiterator. +* @param strsrch string search data +* @param start target text start offset +* @param end target text end offset +*/ +static +void checkBreakBoundary(const UStringSearch *strsrch, int32_t * /*start*/, + int32_t *end) +{ +#if !UCONFIG_NO_BREAK_ITERATION + UBreakIterator *breakiterator = strsrch->search->internalBreakIter; + if (breakiterator) { + int32_t matchend = *end; + //int32_t matchstart = *start; + + if (!ubrk_isBoundary(breakiterator, matchend)) { + *end = ubrk_following(breakiterator, matchend); + } + + /* Check the start of the matched text to make sure it doesn't have any accents + * before it. This code may not be necessary and so it is commented out */ + /*if (!ubrk_isBoundary(breakiterator, matchstart) && !ubrk_isBoundary(breakiterator, matchstart-1)) { + *start = ubrk_preceding(breakiterator, matchstart); + }*/ + } +#endif +} + /** -* Determine whether the target text in UStringSearch bounded by the offset -* start and end is one or more whole units of text as +* Determine whether the target text in UStringSearch bounded by the offset +* start and end is one or more whole units of text as * determined by the breakiterator in UStringSearch. -* @param strsrch string search data +* @param strsrch string search data * @param start target text start offset * @param end target text end offset */ static -inline UBool isBreakUnit(const UStringSearch *strsrch, int32_t start, +UBool isBreakUnit(const UStringSearch *strsrch, int32_t start, int32_t end) { #if !UCONFIG_NO_BREAK_ITERATION UBreakIterator *breakiterator = strsrch->search->breakIter; + //TODO: Add here. if (breakiterator) { int32_t startindex = ubrk_first(breakiterator); int32_t endindex = ubrk_last(breakiterator); - + // out-of-range indexes are never boundary positions if (start < startindex || start > endindex || end < startindex || end > endindex) { return FALSE; } - // otherwise, we can use following() on the position before the - // specified one and return true of the position we get back is the + // otherwise, we can use following() on the position before the + // specified one and return true of the position we get back is the // one the user specified - UBool result = (start == startindex || - ubrk_following(breakiterator, start - 1) == start) && - (end == endindex || + UBool result = (start == startindex || + ubrk_following(breakiterator, start - 1) == start) && + (end == endindex || ubrk_following(breakiterator, end - 1) == end); if (result) { // iterates the individual ces UCollationElements *coleiter = strsrch->utilIter; - const UChar *text = strsrch->search->text + + const UChar *text = strsrch->search->text + start; UErrorCode status = U_ZERO_ERROR; ucol_setText(coleiter, text, end - start, &status); - for (int32_t count = 0; count < strsrch->pattern.CELength; + for (int32_t count = 0; count < strsrch->pattern.cesLength; count ++) { int32_t ce = getCE(strsrch, ucol_next(coleiter, &status)); if (ce == UCOL_IGNORABLE) { count --; continue; } - if (U_FAILURE(status) || ce != strsrch->pattern.CE[count]) { + if (U_FAILURE(status) || ce != strsrch->pattern.ces[count]) { return FALSE; } } @@ -489,8 +654,8 @@ inline UBool isBreakUnit(const UStringSearch *strsrch, int32_t start, } /** -* Getting the next base character offset if current offset is an accent, -* or the current offset if the current character contains a base character. +* Getting the next base character offset if current offset is an accent, +* or the current offset if the current character contains a base character. * accents the following base character will be returned * @param text string * @param textoffset current offset @@ -499,16 +664,16 @@ inline UBool isBreakUnit(const UStringSearch *strsrch, int32_t start, * if the current character is contains a base character. */ static -inline int32_t getNextBaseOffset(const UChar *text, +inline int32_t getNextBaseOffset(const UChar *text, int32_t textoffset, int32_t textlength) { if (textoffset < textlength) { int32_t temp = textoffset; if (getFCD(text, &temp, textlength) >> SECOND_LAST_BYTE_SHIFT_) { - while (temp < textlength) { + while (temp < textlength) { int32_t result = temp; - if ((getFCD(text, &temp, textlength) >> + if ((getFCD(text, &temp, textlength) >> SECOND_LAST_BYTE_SHIFT_) == 0) { return result; } @@ -529,15 +694,15 @@ inline int32_t getNextBaseOffset(const UChar *text, * if the current character is contains a base character. */ static -inline int32_t getNextUStringSearchBaseOffset(UStringSearch *strsrch, +inline int32_t getNextUStringSearchBaseOffset(UStringSearch *strsrch, int32_t textoffset) { int32_t textlength = strsrch->search->textLength; - if (strsrch->pattern.hasSuffixAccents && + if (strsrch->pattern.hasSuffixAccents && textoffset < textlength) { int32_t temp = textoffset; const UChar *text = strsrch->search->text; - UTF_BACK_1(text, 0, temp); + U16_BACK_1(text, 0, temp); if (getFCD(text, &temp, textlength) & LAST_BYTE_MASK_) { return getNextBaseOffset(text, textoffset, textlength); } @@ -566,9 +731,9 @@ inline int32_t shiftForward(UStringSearch *strsrch, UPattern *pattern = &(strsrch->pattern); if (ce != UCOL_NULLORDER) { int32_t shift = pattern->shift[hash(ce)]; - // this is to adjust for characters in the middle of the + // this is to adjust for characters in the middle of the // substring for matching that failed. - int32_t adjust = pattern->CELength - patternceindex; + int32_t adjust = pattern->cesLength - patternceindex; if (adjust > 1 && shift >= adjust) { shift -= adjust - 1; } @@ -577,23 +742,24 @@ inline int32_t shiftForward(UStringSearch *strsrch, else { textoffset += pattern->defaultShiftSize; } - + textoffset = getNextUStringSearchBaseOffset(strsrch, textoffset); // check for unsafe characters - // * if it is the start or middle of a contraction: to be done after + // * if it is the start or middle of a contraction: to be done after // a initial match is found // * thai or lao base consonant character: similar to contraction // * high surrogate character: similar to contraction // * next character is a accent: shift to the next base character return textoffset; } +#endif // #if BOYER_MOORE /** -* sets match not found +* sets match not found * @param strsrch string search data */ static -inline void setMatchNotFound(UStringSearch *strsrch) +inline void setMatchNotFound(UStringSearch *strsrch) { // this method resets the match result regardless of the error status. strsrch->search->matchedIndex = USEARCH_DONE; @@ -606,6 +772,7 @@ inline void setMatchNotFound(UStringSearch *strsrch) } } +#if BOYER_MOORE /** * Gets the offset to the next safe point in text. * ie. not the middle of a contraction, swappable characters or supplementary @@ -617,7 +784,7 @@ inline void setMatchNotFound(UStringSearch *strsrch) * @return offset to the next safe character */ static -inline int32_t getNextSafeOffset(const UCollator *collator, +inline int32_t getNextSafeOffset(const UCollator *collator, const UChar *text, int32_t textoffset, int32_t textlength) @@ -626,22 +793,22 @@ inline int32_t getNextSafeOffset(const UCollator *collator, while (result != textlength && ucol_unsafeCP(text[result], collator)) { result ++; } - return result; + return result; } -/** +/** * This checks for accents in the potential match started with a . * composite character. -* This is really painful... we have to check that composite character do not -* have any extra accents. We have to normalize the potential match and find +* This is really painful... we have to check that composite character do not +* have any extra accents. We have to normalize the potential match and find * the immediate decomposed character before the match. -* The first composite character would have been taken care of by the fcd +* The first composite character would have been taken care of by the fcd * checks in checkForwardExactMatch. -* This is the slow path after the fcd of the first character and -* the last character has been checked by checkForwardExactMatch and we +* This is the slow path after the fcd of the first character and +* the last character has been checked by checkForwardExactMatch and we * determine that the potential match has extra non-ignorable preceding * ces. -* E.g. looking for \u0301 acute in \u01FA A ring above and acute, +* E.g. looking for \u0301 acute in \u01FA A ring above and acute, * checkExtraMatchAccent should fail since there is a middle ring in \u01FA * Note here that accents checking are slow and cautioned in the API docs. * Internal method, status assumed to be a success, caller should check status @@ -656,7 +823,7 @@ inline int32_t getNextSafeOffset(const UCollator *collator, static UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start, - int32_t end, + int32_t end, UErrorCode *status) { UBool result = FALSE; @@ -664,30 +831,30 @@ UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start, int32_t length = end - start; int32_t offset = 0; const UChar *text = strsrch->search->text + start; - - UTF_FWD_1(text, offset, length); + + U16_FWD_1(text, offset, length); // we are only concerned with the first composite character if (unorm_quickCheck(text, offset, UNORM_NFD, status) == UNORM_NO) { - int32_t safeoffset = getNextSafeOffset(strsrch->collator, + int32_t safeoffset = getNextSafeOffset(strsrch->collator, text, 0, length); if (safeoffset != length) { safeoffset ++; } UChar *norm = NULL; UChar buffer[INITIAL_ARRAY_SIZE_]; - int32_t size = unorm_normalize(text, safeoffset, UNORM_NFD, 0, - buffer, INITIAL_ARRAY_SIZE_, - status); + int32_t size = unorm_normalize(text, safeoffset, UNORM_NFD, 0, + buffer, INITIAL_ARRAY_SIZE_, + status); if (U_FAILURE(*status)) { return FALSE; } if (size >= INITIAL_ARRAY_SIZE_) { norm = (UChar *)allocateMemory((size + 1) * sizeof(UChar), status); - // if allocation failed, status will be set to + // if allocation failed, status will be set to // U_MEMORY_ALLOCATION_ERROR and unorm_normalize internally // checks for it. - size = unorm_normalize(text, safeoffset, UNORM_NFD, 0, norm, + size = unorm_normalize(text, safeoffset, UNORM_NFD, 0, norm, size, status); if (U_FAILURE(*status) && norm != NULL) { uprv_free(norm); @@ -700,10 +867,10 @@ UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start, UCollationElements *coleiter = strsrch->utilIter; ucol_setText(coleiter, norm, size, status); - uint32_t firstce = strsrch->pattern.CE[0]; + uint32_t firstce = strsrch->pattern.ces[0]; UBool ignorable = TRUE; uint32_t ce = UCOL_IGNORABLE; - while (U_SUCCESS(*status) && ce != firstce) { + while (U_SUCCESS(*status) && ce != firstce && ce != (uint32_t)UCOL_NULLORDER) { offset = ucol_getOffset(coleiter); if (ce != firstce && ce != UCOL_IGNORABLE) { ignorable = FALSE; @@ -711,7 +878,7 @@ UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start, ce = ucol_next(coleiter, status); } UChar32 codepoint; - UTF_PREV_CHAR(norm, 0, offset, codepoint); + U16_PREV(norm, 0, offset, codepoint); result = !ignorable && (u_getCombiningClass(codepoint) != 0); if (norm != buffer) { @@ -724,36 +891,36 @@ UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start, } /** -* Used by exact matches, checks if there are accents before the match. +* Used by exact matches, checks if there are accents before the match. * This is really painful... we have to check that composite characters at -* the start of the matches have to not have any extra accents. -* We check the FCD of the character first, if it starts with an accent and +* the start of the matches have to not have any extra accents. +* We check the FCD of the character first, if it starts with an accent and * the first pattern ce does not match the first ce of the character, we bail. -* Otherwise we try normalizing the first composite -* character and find the immediate decomposed character before the match to +* Otherwise we try normalizing the first composite +* character and find the immediate decomposed character before the match to * see if it is an non-ignorable accent. -* Now normalizing the first composite character is enough because we ensure -* that when the match is passed in here with extra beginning ces, the +* Now normalizing the first composite character is enough because we ensure +* that when the match is passed in here with extra beginning ces, the * first or last ce that match has to occur within the first character. -* E.g. looking for \u0301 acute in \u01FA A ring above and acute, +* E.g. looking for \u0301 acute in \u01FA A ring above and acute, * checkExtraMatchAccent should fail since there is a middle ring in \u01FA * Note here that accents checking are slow and cautioned in the API docs. * @param strsrch string search data -* @param start offset +* @param start offset * @param end offset -* @return TRUE if there are accents on either side of the match, +* @return TRUE if there are accents on either side of the match, * FALSE otherwise */ static UBool hasAccentsBeforeMatch(const UStringSearch *strsrch, int32_t start, - int32_t end) + int32_t end) { if (strsrch->pattern.hasPrefixAccents) { UCollationElements *coleiter = strsrch->textIter; UErrorCode status = U_ZERO_ERROR; // we have been iterating forwards previously uint32_t ignorable = TRUE; - int32_t firstce = strsrch->pattern.CE[0]; + int32_t firstce = strsrch->pattern.ces[0]; setColEIterOffset(coleiter, start); int32_t ce = getCE(strsrch, ucol_next(coleiter, &status)); @@ -765,7 +932,7 @@ UBool hasAccentsBeforeMatch(const UStringSearch *strsrch, int32_t start, ignorable = FALSE; } ce = getCE(strsrch, ucol_next(coleiter, &status)); - if (U_FAILURE(status)) { + if (U_FAILURE(status) || ce == UCOL_NULLORDER) { return TRUE; } } @@ -777,13 +944,13 @@ UBool hasAccentsBeforeMatch(const UStringSearch *strsrch, int32_t start, // within text int32_t temp = start; // original code - // accent = (getFCD(strsrch->search->text, &temp, - // strsrch->search->textLength) - // >> SECOND_LAST_BYTE_SHIFT_); + // accent = (getFCD(strsrch->search->text, &temp, + // strsrch->search->textLength) + // >> SECOND_LAST_BYTE_SHIFT_); // however this code does not work well with VC7 .net in release mode. - // maybe the inlines for getFCD combined with shifting has bugs in + // maybe the inlines for getFCD combined with shifting has bugs in // VC7. anyways this is a work around. - UBool accent = getFCD(strsrch->search->text, &temp, + UBool accent = getFCD(strsrch->search->text, &temp, strsrch->search->textLength) > 0xFF; if (!accent) { return checkExtraMatchAccents(strsrch, start, end, &status); @@ -793,19 +960,19 @@ UBool hasAccentsBeforeMatch(const UStringSearch *strsrch, int32_t start, } if (start > 0) { temp = start; - UTF_BACK_1(strsrch->search->text, 0, temp); - if (getFCD(strsrch->search->text, &temp, + U16_BACK_1(strsrch->search->text, 0, temp); + if (getFCD(strsrch->search->text, &temp, strsrch->search->textLength) & LAST_BYTE_MASK_) { setColEIterOffset(coleiter, start); ce = ucol_previous(coleiter, &status); - if (U_FAILURE(status) || + if (U_FAILURE(status) || (ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE)) { return TRUE; } } } } - + return FALSE; } @@ -814,39 +981,40 @@ UBool hasAccentsBeforeMatch(const UStringSearch *strsrch, int32_t start, * Note this is the initial boundary check. If the potential match * starts or ends with composite characters, the accents in those * characters will be determined later. -* Not doing backwards iteration here, since discontiguos contraction for +* Not doing backwards iteration here, since discontiguos contraction for * backwards collation element iterator, use up too many characters. -* E.g. looking for \u030A ring in \u01FA A ring above and acute, +* E.g. looking for \u030A ring in \u01FA A ring above and acute, * should fail since there is a acute at the end of \u01FA * Note here that accents checking are slow and cautioned in the API docs. * @param strsrch string search data * @param start offset of match * @param end end offset of the match -* @return TRUE if there are accents on either side of the match, +* @return TRUE if there are accents on either side of the match, * FALSE otherwise */ static -UBool hasAccentsAfterMatch(const UStringSearch *strsrch, int32_t start, - int32_t end) +UBool hasAccentsAfterMatch(const UStringSearch *strsrch, int32_t start, + int32_t end) { if (strsrch->pattern.hasSuffixAccents) { const UChar *text = strsrch->search->text; int32_t temp = end; int32_t textlength = strsrch->search->textLength; - UTF_BACK_1(text, 0, temp); + U16_BACK_1(text, 0, temp); if (getFCD(text, &temp, textlength) & LAST_BYTE_MASK_) { - int32_t firstce = strsrch->pattern.CE[0]; + int32_t firstce = strsrch->pattern.ces[0]; UCollationElements *coleiter = strsrch->textIter; UErrorCode status = U_ZERO_ERROR; + int32_t ce; setColEIterOffset(coleiter, start); - while (getCE(strsrch, ucol_next(coleiter, &status)) != firstce) { - if (U_FAILURE(status)) { + while ((ce = getCE(strsrch, ucol_next(coleiter, &status))) != firstce) { + if (U_FAILURE(status) || ce == UCOL_NULLORDER) { return TRUE; } } int32_t count = 1; - while (count < strsrch->pattern.CELength) { - if (getCE(strsrch, ucol_next(coleiter, &status)) + while (count < strsrch->pattern.cesLength) { + if (getCE(strsrch, ucol_next(coleiter, &status)) == UCOL_IGNORABLE) { // Thai can give an ignorable here. count --; @@ -856,10 +1024,14 @@ UBool hasAccentsAfterMatch(const UStringSearch *strsrch, int32_t start, } count ++; } - int32_t ce = getCE(strsrch, ucol_next(coleiter, &status)); + + ce = ucol_next(coleiter, &status); if (U_FAILURE(status)) { return TRUE; } + if (ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE) { + ce = getCE(strsrch, ce); + } if (ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE) { if (ucol_getOffset(coleiter) <= end) { return TRUE; @@ -872,10 +1044,11 @@ UBool hasAccentsAfterMatch(const UStringSearch *strsrch, int32_t start, } return FALSE; } +#endif // #if BOYER_MOORE /** * Checks if the offset runs out of the text string -* @param offset +* @param offset * @param textlength of the text string * @return TRUE if offset is out of bounds, FALSE otherwise */ @@ -893,37 +1066,26 @@ inline UBool isOutOfBounds(int32_t textlength, int32_t offset) * @return TRUE if identical match is found */ static -inline UBool checkIdentical(const UStringSearch *strsrch, int32_t start, - int32_t end) +inline UBool checkIdentical(const UStringSearch *strsrch, int32_t start, + int32_t end) { - int32_t length = end - start; if (strsrch->strength != UCOL_IDENTICAL) { return TRUE; } + // Note: We could use Normalizer::compare() or similar, but for short strings + // which may not be in FCD it might be faster to just NFD them. UErrorCode status = U_ZERO_ERROR; - int decomplength = unorm_decompose(NULL, -1, - strsrch->search->text + start, length, - FALSE, 0, &status); - if (decomplength != unorm_decompose(NULL, -1, strsrch->pattern.text, - strsrch->pattern.textLength, - FALSE, 0, &status)) { - return FALSE; - } - decomplength ++; - UChar *text = (UChar *)uprv_malloc(decomplength * sizeof(UChar)); - UChar *pattern = (UChar *)uprv_malloc(decomplength * sizeof(UChar)); - unorm_decompose(text, decomplength, strsrch->search->text + start, - length, FALSE, 0, &status); - unorm_decompose(pattern, decomplength, strsrch->pattern.text, - strsrch->pattern.textLength, FALSE, 0, &status); - UBool result = (uprv_memcmp(pattern, text, decomplength * sizeof(UChar)) - == 0); - uprv_free(text); - uprv_free(pattern); - return result; + UnicodeString t2, p2; + strsrch->nfd->normalize( + UnicodeString(FALSE, strsrch->search->text + start, end - start), t2, status); + strsrch->nfd->normalize( + UnicodeString(FALSE, strsrch->pattern.text, strsrch->pattern.textLength), p2, status); + // return FALSE if NFD failed + return U_SUCCESS(status) && t2 == p2; } +#if BOYER_MOORE /** * Checks to see if the match is repeated * @param strsrch string search data @@ -962,7 +1124,7 @@ inline UBool checkRepeatedMatch(UStringSearch *strsrch, * Gets the collation element iterator's current offset. * @param coleiter collation element iterator * @param forwards flag TRUE if we are moving in th forwards direction -* @return current offset +* @return current offset */ static inline int32_t getColElemIterOffset(const UCollationElements *coleiter, @@ -970,19 +1132,19 @@ inline int32_t getColElemIterOffset(const UCollationElements *coleiter, { int32_t result = ucol_getOffset(coleiter); // intricacies of the the backwards collation element iterator - if (!forwards && inNormBuf(coleiter) && !isFCDPointerNull(coleiter)) { + if (FALSE && !forwards && inNormBuf(coleiter) && !isFCDPointerNull(coleiter)) { result ++; } return result; } /** -* Checks match for contraction. +* Checks match for contraction. * If the match ends with a partial contraction we fail. * If the match starts too far off (because of backwards iteration) we try to * chip off the extra characters depending on whether a breakiterator has * been used. -* Internal method, error assumed to be success, caller has to check status +* Internal method, error assumed to be success, caller has to check status * before calling this method. * @param strsrch string search data * @param start offset of potential match, to be modified if necessary @@ -992,34 +1154,34 @@ inline int32_t getColElemIterOffset(const UCollationElements *coleiter, */ static -UBool checkNextExactContractionMatch(UStringSearch *strsrch, - int32_t *start, - int32_t *end, UErrorCode *status) +UBool checkNextExactContractionMatch(UStringSearch *strsrch, + int32_t *start, + int32_t *end, UErrorCode *status) { UCollationElements *coleiter = strsrch->textIter; int32_t textlength = strsrch->search->textLength; - int32_t temp = *start; + int32_t temp = *start; const UCollator *collator = strsrch->collator; const UChar *text = strsrch->search->text; - // This part checks if either ends of the match contains potential + // This part checks if either ends of the match contains potential // contraction. If so we'll have to iterate through them // The start contraction needs to be checked since ucol_previous dumps // all characters till the first safe character into the buffer. - // *start + 1 is used to test for the unsafe characters instead of *start - // because ucol_prev takes all unsafe characters till the first safe - // character ie *start. so by testing *start + 1, we can estimate if - // excess prefix characters has been included in the potential search + // *start + 1 is used to test for the unsafe characters instead of *start + // because ucol_prev takes all unsafe characters till the first safe + // character ie *start. so by testing *start + 1, we can estimate if + // excess prefix characters has been included in the potential search // results. - if ((*end < textlength && ucol_unsafeCP(text[*end], collator)) || - (*start + 1 < textlength + if ((*end < textlength && ucol_unsafeCP(text[*end], collator)) || + (*start + 1 < textlength && ucol_unsafeCP(text[*start + 1], collator))) { int32_t expansion = getExpansionPrefix(coleiter); UBool expandflag = expansion > 0; setColEIterOffset(coleiter, *start); while (expansion > 0) { // getting rid of the redundant ce, caused by setOffset. - // since backward contraction/expansion may have extra ces if we - // are in the normalization buffer, hasAccentsBeforeMatch would + // since backward contraction/expansion may have extra ces if we + // are in the normalization buffer, hasAccentsBeforeMatch would // have taken care of it. // E.g. the character \u01FA will have an expansion of 3, but if // we are only looking for acute and ring \u030A and \u0301, we'll @@ -1035,8 +1197,8 @@ UBool checkNextExactContractionMatch(UStringSearch *strsrch, expansion --; } - int32_t *patternce = strsrch->pattern.CE; - int32_t patterncelength = strsrch->pattern.CELength; + int32_t *patternce = strsrch->pattern.ces; + int32_t patterncelength = strsrch->pattern.cesLength; int32_t count = 0; while (count < patterncelength) { int32_t ce = getCE(strsrch, ucol_next(coleiter, status)); @@ -1049,18 +1211,18 @@ UBool checkNextExactContractionMatch(UStringSearch *strsrch, } if (U_FAILURE(*status) || ce != patternce[count]) { (*end) ++; - *end = getNextUStringSearchBaseOffset(strsrch, *end); + *end = getNextUStringSearchBaseOffset(strsrch, *end); return FALSE; } count ++; } - } + } return TRUE; } /** * Checks and sets the match information if found. -* Checks +* Checks *