// © 2016 and later: Unicode, Inc. and others. // License & terms of use: http://www.unicode.org/copyright.html /* ********************************************************************** * Copyright (C) 2001-2015 IBM and others. All rights reserved. ********************************************************************** * Date Name Description * 07/02/2001 synwee Creation. ********************************************************************** */ #include "unicode/utypes.h" #if !UCONFIG_NO_COLLATION && !UCONFIG_NO_BREAK_ITERATION #include "unicode/usearch.h" #include "unicode/ustring.h" #include "unicode/uchar.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 // internal definition --------------------------------------------------- #define LAST_BYTE_MASK_ 0xFF #define SECOND_LAST_BYTE_SHIFT_ 8 #define SUPPLEMENTARY_MIN_VALUE_ 0x10000 static const Normalizer2Impl *g_nfcImpl = nullptr; // internal methods ------------------------------------------------- /** * Fast collation element iterator setOffset. * This function does not check for bounds. * @param coleiter collation element iterator * @param offset to set */ static inline void setColEIterOffset(UCollationElements *elems, int32_t offset, UErrorCode &status) { // Note: Not "fast" any more after the 2013 collation rewrite. // We do not want to expose more internals than necessary. ucol_setOffset(elems, offset, &status); } /** * Getting the mask for collation strength * @param strength collation strength * @return collation element mask */ static inline uint32_t getMask(UCollationStrength strength) { switch (strength) { case UCOL_PRIMARY: return UCOL_PRIMARYORDERMASK; case UCOL_SECONDARY: return UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK; default: return UCOL_TERTIARYORDERMASK | UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK; } } U_CDECL_BEGIN static UBool U_CALLCONV usearch_cleanup() { g_nfcImpl = nullptr; return true; } 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 * method, status assumed to be success when passed in. */ static inline void initializeFCD(UErrorCode *status) { if (g_nfcImpl == nullptr) { g_nfcImpl = Normalizer2Factory::getNFCImpl(*status); ucln_i18n_registerCleanup(UCLN_I18N_USEARCH, usearch_cleanup); } } /** * 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 * surrogate characters into consideration. * @param strlength length of the argument string * @return fcd value */ static uint16_t getFCD(const char16_t *str, int32_t *offset, int32_t strlength) { const char16_t *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 * attributes * @param strsrch string search data * @param sourcece * @return the modified collation element */ static inline int32_t getCE(const UStringSearch *strsrch, uint32_t sourcece) { // note for tertiary we can't use the collator->tertiaryMask, that // 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 // if the ce is a variable, we mask and get only the primary values // 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) { sourcece &= UCOL_PRIMARYORDERMASK; } else { sourcece = UCOL_IGNORABLE; } } } else if (strsrch->strength >= UCOL_QUATERNARY && sourcece == UCOL_IGNORABLE) { sourcece = 0xFFFF; } return sourcece; } /** * Allocate a memory and returns nullptr 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 * method, status assumed to be success when passed in. * @return newly allocated array, nullptr otherwise */ static inline void * allocateMemory(uint32_t size, UErrorCode *status) { uint32_t *result = (uint32_t *)uprv_malloc(size); if (result == nullptr) { *status = U_MEMORY_ALLOCATION_ERROR; } return result; } /** * Adds a uint32_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 nullptr 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 int32_t * addTouint32_tArray(int32_t *destination, uint32_t offset, uint32_t *destinationlength, uint32_t value, uint32_t increments, UErrorCode *status) { uint32_t newlength = *destinationlength; if (offset + 1 == newlength) { newlength += increments; int32_t *temp = (int32_t *)allocateMemory( sizeof(int32_t) * newlength, status); if (U_FAILURE(*status)) { return nullptr; } uprv_memcpy(temp, destination, sizeof(int32_t) * (size_t)offset); *destinationlength = newlength; destination = temp; } destination[offset] = value; 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 nullptr 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 nullptr; } uprv_memcpy(temp, destination, sizeof(int64_t) * (size_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 * 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. */ static inline void initializePatternCETable(UStringSearch *strsrch, UErrorCode *status) { UPattern *pattern = &(strsrch->pattern); uint32_t cetablesize = INITIAL_ARRAY_SIZE_; int32_t *cetable = pattern->cesBuffer; uint32_t patternlength = pattern->textLength; UCollationElements *coleiter = strsrch->utilIter; if (coleiter == nullptr) { 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; } if (pattern->ces != cetable && pattern->ces) { uprv_free(pattern->ces); } uint32_t offset = 0; int32_t ce; while ((ce = ucol_next(coleiter, status)) != UCOL_NULLORDER && U_SUCCESS(*status)) { uint32_t newce = getCE(strsrch, ce); if (newce) { int32_t *temp = addTouint32_tArray(cetable, offset, &cetablesize, newce, patternlength - ucol_getOffset(coleiter) + 1, status); if (U_FAILURE(*status)) { return; } offset ++; if (cetable != temp && cetable != pattern->cesBuffer) { uprv_free(cetable); } cetable = temp; } } cetable[offset] = 0; pattern->ces = cetable; pattern->cesLength = offset; } /** * 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. */ static inline void 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 == nullptr) { coleiter = ucol_openElements(strsrch->collator, pattern->text, patternlength, status); // status will be checked in nextProcessed(..) later and if it is an error // then UCOL_PROCESSED_NULLORDER is returned by nextProcessed(..), so 0 will be // returned. strsrch->utilIter = coleiter; } else { ucol_setText(coleiter, pattern->text, pattern->textLength, status); } if(U_FAILURE(*status)) { return; } if (pattern->pces != pcetable && pattern->pces != nullptr) { uprv_free(pattern->pces); } uint32_t offset = 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(nullptr, nullptr, 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; } offset += 1; if (pcetable != temp && pcetable != pattern->pcesBuffer) { uprv_free(pcetable); } pcetable = temp; } pcetable[offset] = 0; pattern->pces = pcetable; pattern->pcesLength = offset; } /** * Initializes the pattern struct. * @param strsrch UStringSearch data storage * @param status output error if any, caller to check status before calling * method, status assumed to be success when passed in. */ static inline void initializePattern(UStringSearch *strsrch, UErrorCode *status) { if (U_FAILURE(*status)) { return; } UPattern *pattern = &(strsrch->pattern); const char16_t *patterntext = pattern->text; int32_t length = pattern->textLength; int32_t index = 0; // 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 != nullptr) { if (strsrch->pattern.pces != strsrch->pattern.pcesBuffer) { uprv_free(strsrch->pattern.pces); } strsrch->pattern.pces = nullptr; } initializePatternCETable(strsrch, status); } /** * Initializes the pattern struct and builds the pattern collation element table. * @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) { initializePattern(strsrch, status); } #if !UCONFIG_NO_BREAK_ITERATION // If the caller provided a character breakiterator we'll return that, // otherwise we lazily create the internal break iterator. static UBreakIterator* getBreakIterator(UStringSearch *strsrch, UErrorCode &status) { if (U_FAILURE(status)) { return nullptr; } if (strsrch->search->breakIter != nullptr) { return strsrch->search->breakIter; } if (strsrch->search->internalBreakIter != nullptr) { return strsrch->search->internalBreakIter; } // Need to create the internal break iterator. strsrch->search->internalBreakIter = ubrk_open(UBRK_CHARACTER, ucol_getLocaleByType(strsrch->collator, ULOC_VALID_LOCALE, &status), strsrch->search->text, strsrch->search->textLength, &status); return strsrch->search->internalBreakIter; } #endif /** * Sets the match result to "not found", regardless of the incoming error status. * If an error occurs while setting the result, it is reported back. * * @param strsrch string search data * @param status for output errors, if they occur. */ static inline void setMatchNotFound(UStringSearch *strsrch, UErrorCode &status) { UErrorCode localStatus = U_ZERO_ERROR; strsrch->search->matchedIndex = USEARCH_DONE; strsrch->search->matchedLength = 0; if (strsrch->search->isForwardSearching) { setColEIterOffset(strsrch->textIter, strsrch->search->textLength, localStatus); } else { setColEIterOffset(strsrch->textIter, 0, localStatus); } // If an error occurred while setting the result to not found (ex: OOM), // then we want to report that error back to the caller. if (U_SUCCESS(status) && U_FAILURE(localStatus)) { status = localStatus; } } /** * Checks if the offset runs out of the text string * @param offset * @param textlength of the text string * @return true if offset is out of bounds, false otherwise */ static inline UBool isOutOfBounds(int32_t textlength, int32_t offset) { return offset < 0 || offset > textlength; } /** * Checks for identical match * @param strsrch string search data * @param start offset of possible match * @param end offset of possible match * @return true if identical match is found */ static inline UBool checkIdentical(const UStringSearch *strsrch, int32_t start, int32_t end) { 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; 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; } // constructors and destructor ------------------------------------------- U_CAPI UStringSearch * U_EXPORT2 usearch_open(const char16_t *pattern, int32_t patternlength, const char16_t *text, int32_t textlength, const char *locale, UBreakIterator *breakiter, UErrorCode *status) { if (U_FAILURE(*status)) { return nullptr; } #if UCONFIG_NO_BREAK_ITERATION if (breakiter != nullptr) { *status = U_UNSUPPORTED_ERROR; return nullptr; } #endif if (locale) { // ucol_open internally checks for status UCollator *collator = ucol_open(locale, status); // pattern, text checks are done in usearch_openFromCollator UStringSearch *result = usearch_openFromCollator(pattern, patternlength, text, textlength, collator, breakiter, status); if (result == nullptr || U_FAILURE(*status)) { if (collator) { ucol_close(collator); } return nullptr; } else { result->ownCollator = true; } return result; } *status = U_ILLEGAL_ARGUMENT_ERROR; return nullptr; } U_CAPI UStringSearch * U_EXPORT2 usearch_openFromCollator( const char16_t *pattern, int32_t patternlength, const char16_t *text, int32_t textlength, const UCollator *collator, UBreakIterator *breakiter, UErrorCode *status) { if (U_FAILURE(*status)) { return nullptr; } #if UCONFIG_NO_BREAK_ITERATION if (breakiter != nullptr) { *status = U_UNSUPPORTED_ERROR; return nullptr; } #endif if (pattern == nullptr || text == nullptr || collator == nullptr) { *status = U_ILLEGAL_ARGUMENT_ERROR; return nullptr; } // string search does not really work when numeric collation is turned on if(ucol_getAttribute(collator, UCOL_NUMERIC_COLLATION, status) == UCOL_ON) { *status = U_UNSUPPORTED_ERROR; return nullptr; } if (U_SUCCESS(*status)) { initializeFCD(status); if (U_FAILURE(*status)) { return nullptr; } UStringSearch *result; if (textlength == -1) { textlength = u_strlen(text); } if (patternlength == -1) { patternlength = u_strlen(pattern); } if (textlength <= 0 || patternlength <= 0) { *status = U_ILLEGAL_ARGUMENT_ERROR; return nullptr; } result = (UStringSearch *)uprv_malloc(sizeof(UStringSearch)); if (result == nullptr) { *status = U_MEMORY_ALLOCATION_ERROR; return nullptr; } result->collator = collator; result->strength = ucol_getStrength(collator); result->ceMask = getMask(result->strength); result->toShift = ucol_getAttribute(collator, UCOL_ALTERNATE_HANDLING, status) == UCOL_SHIFTED; result->variableTop = ucol_getVariableTop(collator, status); result->nfd = Normalizer2::getNFDInstance(*status); if (U_FAILURE(*status)) { uprv_free(result); return nullptr; } result->search = (USearch *)uprv_malloc(sizeof(USearch)); if (result->search == nullptr) { *status = U_MEMORY_ALLOCATION_ERROR; uprv_free(result); return nullptr; } result->search->text = text; result->search->textLength = textlength; result->pattern.text = pattern; result->pattern.textLength = patternlength; result->pattern.ces = nullptr; result->pattern.pces = nullptr; result->search->breakIter = breakiter; #if !UCONFIG_NO_BREAK_ITERATION result->search->internalBreakIter = nullptr; // Lazily created. if (breakiter) { ubrk_setText(breakiter, text, textlength, status); } #endif result->ownCollator = false; result->search->matchedLength = 0; result->search->matchedIndex = USEARCH_DONE; result->utilIter = nullptr; result->textIter = ucol_openElements(collator, text, textlength, status); result->textProcessedIter = nullptr; if (U_FAILURE(*status)) { usearch_close(result); return nullptr; } result->search->isOverlap = false; result->search->isCanonicalMatch = false; result->search->elementComparisonType = 0; result->search->isForwardSearching = true; result->search->reset = true; initialize(result, status); if (U_FAILURE(*status)) { usearch_close(result); return nullptr; } return result; } return nullptr; } U_CAPI void U_EXPORT2 usearch_close(UStringSearch *strsrch) { if (strsrch) { if (strsrch->pattern.ces != strsrch->pattern.cesBuffer && strsrch->pattern.ces) { uprv_free(strsrch->pattern.ces); } if (strsrch->pattern.pces != nullptr && strsrch->pattern.pces != strsrch->pattern.pcesBuffer) { uprv_free(strsrch->pattern.pces); } delete strsrch->textProcessedIter; ucol_closeElements(strsrch->textIter); ucol_closeElements(strsrch->utilIter); if (strsrch->ownCollator && strsrch->collator) { ucol_close((UCollator *)strsrch->collator); } #if !UCONFIG_NO_BREAK_ITERATION if (strsrch->search->internalBreakIter != nullptr) { ubrk_close(strsrch->search->internalBreakIter); } #endif uprv_free(strsrch->search); uprv_free(strsrch); } } namespace { UBool initTextProcessedIter(UStringSearch *strsrch, UErrorCode *status) { if (U_FAILURE(*status)) { return false; } if (strsrch->textProcessedIter == nullptr) { strsrch->textProcessedIter = new icu::UCollationPCE(strsrch->textIter); if (strsrch->textProcessedIter == nullptr) { *status = U_MEMORY_ALLOCATION_ERROR; return false; } } else { strsrch->textProcessedIter->init(strsrch->textIter); } return true; } } // set and get methods -------------------------------------------------- U_CAPI void U_EXPORT2 usearch_setOffset(UStringSearch *strsrch, int32_t position, UErrorCode *status) { if (U_SUCCESS(*status) && strsrch) { if (isOutOfBounds(strsrch->search->textLength, position)) { *status = U_INDEX_OUTOFBOUNDS_ERROR; } else { setColEIterOffset(strsrch->textIter, position, *status); } strsrch->search->matchedIndex = USEARCH_DONE; strsrch->search->matchedLength = 0; strsrch->search->reset = false; } } U_CAPI int32_t U_EXPORT2 usearch_getOffset(const UStringSearch *strsrch) { if (strsrch) { int32_t result = ucol_getOffset(strsrch->textIter); if (isOutOfBounds(strsrch->search->textLength, result)) { return USEARCH_DONE; } return result; } return USEARCH_DONE; } U_CAPI void U_EXPORT2 usearch_setAttribute(UStringSearch *strsrch, USearchAttribute attribute, USearchAttributeValue value, UErrorCode *status) { if (U_SUCCESS(*status) && strsrch) { switch (attribute) { case USEARCH_OVERLAP : strsrch->search->isOverlap = (value == USEARCH_ON ? true : false); break; case USEARCH_CANONICAL_MATCH : strsrch->search->isCanonicalMatch = (value == USEARCH_ON ? true : false); break; case USEARCH_ELEMENT_COMPARISON : if (value == USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD || value == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD) { strsrch->search->elementComparisonType = (int16_t)value; } else { strsrch->search->elementComparisonType = 0; } break; case USEARCH_ATTRIBUTE_COUNT : default: *status = U_ILLEGAL_ARGUMENT_ERROR; } } if (value == USEARCH_ATTRIBUTE_VALUE_COUNT) { *status = U_ILLEGAL_ARGUMENT_ERROR; } } U_CAPI USearchAttributeValue U_EXPORT2 usearch_getAttribute( const UStringSearch *strsrch, USearchAttribute attribute) { if (strsrch) { switch (attribute) { case USEARCH_OVERLAP : return (strsrch->search->isOverlap ? USEARCH_ON : USEARCH_OFF); case USEARCH_CANONICAL_MATCH : return (strsrch->search->isCanonicalMatch ? USEARCH_ON : USEARCH_OFF); case USEARCH_ELEMENT_COMPARISON : { int16_t value = strsrch->search->elementComparisonType; if (value == USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD || value == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD) { return (USearchAttributeValue)value; } else { return USEARCH_STANDARD_ELEMENT_COMPARISON; } } case USEARCH_ATTRIBUTE_COUNT : return USEARCH_DEFAULT; } } return USEARCH_DEFAULT; } U_CAPI int32_t U_EXPORT2 usearch_getMatchedStart( const UStringSearch *strsrch) { if (strsrch == nullptr) { return USEARCH_DONE; } return strsrch->search->matchedIndex; } U_CAPI int32_t U_EXPORT2 usearch_getMatchedText(const UStringSearch *strsrch, char16_t *result, int32_t resultCapacity, UErrorCode *status) { if (U_FAILURE(*status)) { return USEARCH_DONE; } if (strsrch == nullptr || resultCapacity < 0 || (resultCapacity > 0 && result == nullptr)) { *status = U_ILLEGAL_ARGUMENT_ERROR; return USEARCH_DONE; } int32_t copylength = strsrch->search->matchedLength; int32_t copyindex = strsrch->search->matchedIndex; if (copyindex == USEARCH_DONE) { u_terminateUChars(result, resultCapacity, 0, status); return USEARCH_DONE; } if (resultCapacity < copylength) { copylength = resultCapacity; } if (copylength > 0) { uprv_memcpy(result, strsrch->search->text + copyindex, copylength * sizeof(char16_t)); } return u_terminateUChars(result, resultCapacity, strsrch->search->matchedLength, status); } U_CAPI int32_t U_EXPORT2 usearch_getMatchedLength( const UStringSearch *strsrch) { if (strsrch) { return strsrch->search->matchedLength; } return USEARCH_DONE; } #if !UCONFIG_NO_BREAK_ITERATION U_CAPI void U_EXPORT2 usearch_setBreakIterator(UStringSearch *strsrch, UBreakIterator *breakiter, UErrorCode *status) { if (U_SUCCESS(*status) && strsrch) { strsrch->search->breakIter = breakiter; if (breakiter) { ubrk_setText(breakiter, strsrch->search->text, strsrch->search->textLength, status); } } } U_CAPI const UBreakIterator* U_EXPORT2 usearch_getBreakIterator(const UStringSearch *strsrch) { if (strsrch) { return strsrch->search->breakIter; } return nullptr; } #endif U_CAPI void U_EXPORT2 usearch_setText( UStringSearch *strsrch, const char16_t *text, int32_t textlength, UErrorCode *status) { if (U_SUCCESS(*status)) { if (strsrch == nullptr || text == nullptr || textlength < -1 || textlength == 0) { *status = U_ILLEGAL_ARGUMENT_ERROR; } else { if (textlength == -1) { textlength = u_strlen(text); } strsrch->search->text = text; strsrch->search->textLength = textlength; ucol_setText(strsrch->textIter, text, textlength, status); strsrch->search->matchedIndex = USEARCH_DONE; strsrch->search->matchedLength = 0; strsrch->search->reset = true; #if !UCONFIG_NO_BREAK_ITERATION if (strsrch->search->breakIter != nullptr) { ubrk_setText(strsrch->search->breakIter, text, textlength, status); } if (strsrch->search->internalBreakIter != nullptr) { ubrk_setText(strsrch->search->internalBreakIter, text, textlength, status); } #endif } } } U_CAPI const char16_t * U_EXPORT2 usearch_getText(const UStringSearch *strsrch, int32_t *length) { if (strsrch) { *length = strsrch->search->textLength; return strsrch->search->text; } return nullptr; } U_CAPI void U_EXPORT2 usearch_setCollator( UStringSearch *strsrch, const UCollator *collator, UErrorCode *status) { if (U_SUCCESS(*status)) { if (collator == nullptr) { *status = U_ILLEGAL_ARGUMENT_ERROR; return; } if (strsrch) { delete strsrch->textProcessedIter; strsrch->textProcessedIter = nullptr; ucol_closeElements(strsrch->textIter); ucol_closeElements(strsrch->utilIter); strsrch->textIter = strsrch->utilIter = nullptr; if (strsrch->ownCollator && (strsrch->collator != collator)) { ucol_close((UCollator *)strsrch->collator); strsrch->ownCollator = false; } strsrch->collator = collator; strsrch->strength = ucol_getStrength(collator); strsrch->ceMask = getMask(strsrch->strength); #if !UCONFIG_NO_BREAK_ITERATION if (strsrch->search->internalBreakIter != nullptr) { ubrk_close(strsrch->search->internalBreakIter); strsrch->search->internalBreakIter = nullptr; // Lazily created. } #endif // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT strsrch->toShift = ucol_getAttribute(collator, UCOL_ALTERNATE_HANDLING, status) == UCOL_SHIFTED; // if status is a failure, ucol_getVariableTop returns 0 strsrch->variableTop = ucol_getVariableTop(collator, status); strsrch->textIter = ucol_openElements(collator, strsrch->search->text, strsrch->search->textLength, status); strsrch->utilIter = ucol_openElements( collator, strsrch->pattern.text, strsrch->pattern.textLength, status); // initialize() _after_ setting the iterators for the new collator. initialize(strsrch, status); } // **** are these calls needed? // **** we call uprv_init_pce in initializePatternPCETable // **** and the CEIBuffer constructor... #if 0 uprv_init_pce(strsrch->textIter); uprv_init_pce(strsrch->utilIter); #endif } } U_CAPI UCollator * U_EXPORT2 usearch_getCollator(const UStringSearch *strsrch) { if (strsrch) { return (UCollator *)strsrch->collator; } return nullptr; } U_CAPI void U_EXPORT2 usearch_setPattern( UStringSearch *strsrch, const char16_t *pattern, int32_t patternlength, UErrorCode *status) { if (U_SUCCESS(*status)) { if (strsrch == nullptr || pattern == nullptr) { *status = U_ILLEGAL_ARGUMENT_ERROR; } else { if (patternlength == -1) { patternlength = u_strlen(pattern); } if (patternlength == 0) { *status = U_ILLEGAL_ARGUMENT_ERROR; return; } strsrch->pattern.text = pattern; strsrch->pattern.textLength = patternlength; initialize(strsrch, status); } } } U_CAPI const char16_t* U_EXPORT2 usearch_getPattern(const UStringSearch *strsrch, int32_t *length) { if (strsrch) { *length = strsrch->pattern.textLength; return strsrch->pattern.text; } return nullptr; } // miscellaneous methods -------------------------------------------------- U_CAPI int32_t U_EXPORT2 usearch_first(UStringSearch *strsrch, UErrorCode *status) { if (strsrch && U_SUCCESS(*status)) { strsrch->search->isForwardSearching = true; usearch_setOffset(strsrch, 0, status); if (U_SUCCESS(*status)) { return usearch_next(strsrch, status); } } return USEARCH_DONE; } U_CAPI int32_t U_EXPORT2 usearch_following(UStringSearch *strsrch, int32_t position, UErrorCode *status) { if (strsrch && U_SUCCESS(*status)) { strsrch->search->isForwardSearching = true; // position checked in usearch_setOffset usearch_setOffset(strsrch, position, status); if (U_SUCCESS(*status)) { return usearch_next(strsrch, status); } } return USEARCH_DONE; } U_CAPI int32_t U_EXPORT2 usearch_last(UStringSearch *strsrch, UErrorCode *status) { if (strsrch && U_SUCCESS(*status)) { strsrch->search->isForwardSearching = false; usearch_setOffset(strsrch, strsrch->search->textLength, status); if (U_SUCCESS(*status)) { return usearch_previous(strsrch, status); } } return USEARCH_DONE; } U_CAPI int32_t U_EXPORT2 usearch_preceding(UStringSearch *strsrch, int32_t position, UErrorCode *status) { if (strsrch && U_SUCCESS(*status)) { strsrch->search->isForwardSearching = false; // position checked in usearch_setOffset usearch_setOffset(strsrch, position, status); if (U_SUCCESS(*status)) { return usearch_previous(strsrch, status); } } return USEARCH_DONE; } /** * If a direction switch is required, we'll count the number of ces till the * beginning of the collation element iterator and iterate forwards that * number of times. This is so that we get to the correct point within the * string to continue the search in. Imagine when we are in the middle of the * normalization buffer when the change in direction is request. arrrgghh.... * After searching the offset within the collation element iterator will be * shifted to the start of the match. If a match is not found, the offset would * have been set to the end of the text string in the collation element * iterator. * Okay, here's my take on normalization buffer. The only time when there can * be 2 matches within the same normalization is when the pattern is consists * of all accents. But since the offset returned is from the text string, we * should not confuse the caller by returning the second match within the * same normalization buffer. If we do, the 2 results will have the same match * offsets, and that'll be confusing. I'll return the next match that doesn't * fall within the same normalization buffer. Note this does not affect the * results of matches spanning the text and the normalization buffer. * The position to start searching is taken from the collation element * iterator. Callers of this API would have to set the offset in the collation * element iterator before using this method. */ U_CAPI int32_t U_EXPORT2 usearch_next(UStringSearch *strsrch, UErrorCode *status) { if (U_SUCCESS(*status) && strsrch) { // note offset is either equivalent to the start of the previous match // or is set by the user int32_t offset = usearch_getOffset(strsrch); USearch *search = strsrch->search; search->reset = false; int32_t textlength = search->textLength; if (search->isForwardSearching) { if (offset == textlength || (! search->isOverlap && (search->matchedIndex != USEARCH_DONE && offset + search->matchedLength > textlength))) { // not enough characters to match setMatchNotFound(strsrch, *status); return USEARCH_DONE; } } else { // switching direction. // if matchedIndex == USEARCH_DONE, it means that either a // setOffset has been called or that previous ran off the text // string. the iterator would have been set to offset 0 if a // match is not found. search->isForwardSearching = true; if (search->matchedIndex != USEARCH_DONE) { // there's no need to set the collation element iterator // the next call to next will set the offset. return search->matchedIndex; } } if (U_SUCCESS(*status)) { if (strsrch->pattern.cesLength == 0) { if (search->matchedIndex == USEARCH_DONE) { search->matchedIndex = offset; } else { // moves by codepoints U16_FWD_1(search->text, search->matchedIndex, textlength); } search->matchedLength = 0; setColEIterOffset(strsrch->textIter, search->matchedIndex, *status); // status checked below if (search->matchedIndex == textlength) { search->matchedIndex = USEARCH_DONE; } } else { if (search->matchedLength > 0) { // if matchlength is 0 we are at the start of the iteration if (search->isOverlap) { ucol_setOffset(strsrch->textIter, offset + 1, status); } else { ucol_setOffset(strsrch->textIter, offset + search->matchedLength, status); } } else { // for boundary check purposes. this will ensure that the // next match will not precede the current offset // note search->matchedIndex will always be set to something // in the code search->matchedIndex = offset - 1; } if (search->isCanonicalMatch) { // can't use exact here since extra accents are allowed. usearch_handleNextCanonical(strsrch, status); } else { usearch_handleNextExact(strsrch, status); } } if (U_FAILURE(*status)) { return USEARCH_DONE; } if (search->matchedIndex == USEARCH_DONE) { ucol_setOffset(strsrch->textIter, search->textLength, status); } else { ucol_setOffset(strsrch->textIter, search->matchedIndex, status); } return search->matchedIndex; } } return USEARCH_DONE; } U_CAPI int32_t U_EXPORT2 usearch_previous(UStringSearch *strsrch, UErrorCode *status) { if (U_SUCCESS(*status) && strsrch) { int32_t offset; USearch *search = strsrch->search; if (search->reset) { offset = search->textLength; search->isForwardSearching = false; search->reset = false; setColEIterOffset(strsrch->textIter, offset, *status); } else { offset = usearch_getOffset(strsrch); } int32_t matchedindex = search->matchedIndex; if (search->isForwardSearching) { // switching direction. // if matchedIndex == USEARCH_DONE, it means that either a // setOffset has been called or that next ran off the text // string. the iterator would have been set to offset textLength if // a match is not found. search->isForwardSearching = false; if (matchedindex != USEARCH_DONE) { return matchedindex; } } else { // Could check pattern length, but the // linear search will do the right thing if (offset == 0 || matchedindex == 0) { setMatchNotFound(strsrch, *status); return USEARCH_DONE; } } if (U_SUCCESS(*status)) { if (strsrch->pattern.cesLength == 0) { search->matchedIndex = (matchedindex == USEARCH_DONE ? offset : matchedindex); if (search->matchedIndex == 0) { setMatchNotFound(strsrch, *status); // status checked below } else { // move by codepoints U16_BACK_1(search->text, 0, search->matchedIndex); setColEIterOffset(strsrch->textIter, search->matchedIndex, *status); // status checked below search->matchedLength = 0; } } else { if (strsrch->search->isCanonicalMatch) { // can't use exact here since extra accents are allowed. usearch_handlePreviousCanonical(strsrch, status); // status checked below } else { usearch_handlePreviousExact(strsrch, status); // status checked below } } if (U_FAILURE(*status)) { return USEARCH_DONE; } return search->matchedIndex; } } return USEARCH_DONE; } U_CAPI void U_EXPORT2 usearch_reset(UStringSearch *strsrch) { /* reset is setting the attributes that are already in string search, hence all attributes in the collator should be retrieved without any problems */ if (strsrch) { UErrorCode status = U_ZERO_ERROR; UBool sameCollAttribute = true; uint32_t ceMask; UBool shift; uint32_t varTop; // **** hack to deal w/ how processed CEs encode quaternary **** UCollationStrength newStrength = ucol_getStrength(strsrch->collator); if ((strsrch->strength < UCOL_QUATERNARY && newStrength >= UCOL_QUATERNARY) || (strsrch->strength >= UCOL_QUATERNARY && newStrength < UCOL_QUATERNARY)) { sameCollAttribute = false; } strsrch->strength = ucol_getStrength(strsrch->collator); ceMask = getMask(strsrch->strength); if (strsrch->ceMask != ceMask) { strsrch->ceMask = ceMask; sameCollAttribute = false; } // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT shift = ucol_getAttribute(strsrch->collator, UCOL_ALTERNATE_HANDLING, &status) == UCOL_SHIFTED; if (strsrch->toShift != shift) { strsrch->toShift = shift; sameCollAttribute = false; } // if status is a failure, ucol_getVariableTop returns 0 varTop = ucol_getVariableTop(strsrch->collator, &status); if (strsrch->variableTop != varTop) { strsrch->variableTop = varTop; sameCollAttribute = false; } if (!sameCollAttribute) { initialize(strsrch, &status); } ucol_setText(strsrch->textIter, strsrch->search->text, strsrch->search->textLength, &status); strsrch->search->matchedLength = 0; strsrch->search->matchedIndex = USEARCH_DONE; strsrch->search->isOverlap = false; strsrch->search->isCanonicalMatch = false; strsrch->search->elementComparisonType = 0; strsrch->search->isForwardSearching = true; strsrch->search->reset = true; } } // // CEI Collation Element + source text index. // These structs are kept in the circular buffer. // struct CEI { int64_t ce; int32_t lowIndex; int32_t highIndex; }; U_NAMESPACE_BEGIN namespace { // // CEIBuffer A circular buffer of CEs-with-index from the text being searched. // #define DEFAULT_CEBUFFER_SIZE 96 #define CEBUFFER_EXTRA 32 // Some typical max values to make buffer size more reasonable for asymmetric search. // #8694 is for a better long-term solution to allocation of this buffer. #define MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L 8 #define MAX_TARGET_IGNORABLES_PER_PAT_OTHER 3 #define MIGHT_BE_JAMO_L(c) ((c >= 0x1100 && c <= 0x115E) || (c >= 0x3131 && c <= 0x314E) || (c >= 0x3165 && c <= 0x3186)) struct CEIBuffer { CEI defBuf[DEFAULT_CEBUFFER_SIZE]; CEI *buf; int32_t bufSize; int32_t firstIx; int32_t limitIx; UCollationElements *ceIter; UStringSearch *strSearch; CEIBuffer(UStringSearch *ss, UErrorCode *status); ~CEIBuffer(); const CEI *get(int32_t index); const CEI *getPrevious(int32_t index); }; CEIBuffer::CEIBuffer(UStringSearch *ss, UErrorCode *status) { buf = defBuf; strSearch = ss; bufSize = ss->pattern.pcesLength + CEBUFFER_EXTRA; if (ss->search->elementComparisonType != 0) { const char16_t * patText = ss->pattern.text; if (patText) { const char16_t * patTextLimit = patText + ss->pattern.textLength; while ( patText < patTextLimit ) { char16_t c = *patText++; if (MIGHT_BE_JAMO_L(c)) { bufSize += MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L; } else { // No check for surrogates, we might allocate slightly more buffer than necessary. bufSize += MAX_TARGET_IGNORABLES_PER_PAT_OTHER; } } } } ceIter = ss->textIter; firstIx = 0; limitIx = 0; if (!initTextProcessedIter(ss, status)) { return; } if (bufSize>DEFAULT_CEBUFFER_SIZE) { buf = (CEI *)uprv_malloc(bufSize * sizeof(CEI)); if (buf == nullptr) { *status = U_MEMORY_ALLOCATION_ERROR; } } } // TODO: add a reset or init function so that allocated // buffers can be retained & reused. CEIBuffer::~CEIBuffer() { if (buf != defBuf) { uprv_free(buf); } } // Get the CE with the specified index. // Index must be in the range // n-history_size < index < n+1 // where n is the largest index to have been fetched by some previous call to this function. // The CE value will be UCOL__PROCESSED_NULLORDER at end of input. // const CEI *CEIBuffer::get(int32_t index) { int i = index % bufSize; if (index>=firstIx && index= bufSize) { // The buffer is full, knock out the lowest-indexed entry. firstIx++; } UErrorCode status = U_ZERO_ERROR; buf[i].ce = strSearch->textProcessedIter->nextProcessed(&buf[i].lowIndex, &buf[i].highIndex, &status); return &buf[i]; } // Get the CE with the specified index. // Index must be in the range // n-history_size < index < n+1 // where n is the largest index to have been fetched by some previous call to this function. // The CE value will be UCOL__PROCESSED_NULLORDER at end of input. // const CEI *CEIBuffer::getPrevious(int32_t index) { int i = index % bufSize; if (index>=firstIx && index= bufSize) { // The buffer is full, knock out the lowest-indexed entry. firstIx++; } UErrorCode status = U_ZERO_ERROR; buf[i].ce = strSearch->textProcessedIter->previousProcessed(&buf[i].lowIndex, &buf[i].highIndex, &status); return &buf[i]; } } U_NAMESPACE_END // #define USEARCH_DEBUG #ifdef USEARCH_DEBUG #include #include #endif /* * Find the next break boundary after startIndex. If the UStringSearch object * has an external break iterator, use that. Otherwise use the internal character * break iterator. */ static int32_t nextBoundaryAfter(UStringSearch *strsrch, int32_t startIndex, UErrorCode &status) { if (U_FAILURE(status)) { return startIndex; } #if 0 const char16_t *text = strsrch->search->text; int32_t textLen = strsrch->search->textLength; U_ASSERT(startIndex>=0); U_ASSERT(startIndex<=textLen); if (startIndex >= textLen) { return startIndex; } UChar32 c; int32_t i = startIndex; U16_NEXT(text, i, textLen, c); // If we are on a control character, stop without looking for combining marks. // Control characters do not combine. int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK); if (gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR) { return i; } // The initial character was not a control, and can thus accept trailing // combining characters. Advance over however many of them there are. int32_t indexOfLastCharChecked; for (;;) { indexOfLastCharChecked = i; if (i>=textLen) { break; } U16_NEXT(text, i, textLen, c); gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK); if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) { break; } } return indexOfLastCharChecked; #elif !UCONFIG_NO_BREAK_ITERATION UBreakIterator *breakiterator = getBreakIterator(strsrch, status); if (U_FAILURE(status)) { return startIndex; } return ubrk_following(breakiterator, startIndex); #else // **** or should we use the original code? **** return startIndex; #endif } /* * Returns true if index is on a break boundary. If the UStringSearch * has an external break iterator, test using that, otherwise test * using the internal character break iterator. */ static UBool isBreakBoundary(UStringSearch *strsrch, int32_t index, UErrorCode &status) { if (U_FAILURE(status)) { return true; } #if 0 const char16_t *text = strsrch->search->text; int32_t textLen = strsrch->search->textLength; U_ASSERT(index>=0); U_ASSERT(index<=textLen); if (index>=textLen || index<=0) { return true; } // If the character at the current index is not a GRAPHEME_EXTEND // then we can not be within a combining sequence. UChar32 c; U16_GET(text, 0, index, textLen, c); int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK); if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) { return true; } // We are at a combining mark. If the preceding character is anything // except a CONTROL, CR or LF, we are in a combining sequence. U16_PREV(text, 0, index, c); gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK); UBool combining = !(gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR); return !combining; #elif !UCONFIG_NO_BREAK_ITERATION UBreakIterator *breakiterator = getBreakIterator(strsrch, status); if (U_FAILURE(status)) { return true; } return ubrk_isBoundary(breakiterator, index); #else // **** or use the original code? **** return true; #endif } #if 0 static UBool onBreakBoundaries(const UStringSearch *strsrch, int32_t start, int32_t end, UErrorCode &status) { if (U_FAILURE(status)) { return true; } #if !UCONFIG_NO_BREAK_ITERATION UBreakIterator *breakiterator = getBreakIterator(strsrch, status); if (U_SUCCESS(status)) { 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; } return ubrk_isBoundary(breakiterator, start) && ubrk_isBoundary(breakiterator, end); } #endif return true; } #endif typedef enum { U_CE_MATCH = -1, U_CE_NO_MATCH = 0, U_CE_SKIP_TARG, U_CE_SKIP_PATN } UCompareCEsResult; #define U_CE_LEVEL2_BASE 0x00000005 #define U_CE_LEVEL3_BASE 0x00050000 static UCompareCEsResult compareCE64s(int64_t targCE, int64_t patCE, int16_t compareType) { if (targCE == patCE) { return U_CE_MATCH; } if (compareType == 0) { return U_CE_NO_MATCH; } int64_t targCEshifted = targCE >> 32; int64_t patCEshifted = patCE >> 32; int64_t mask; mask = 0xFFFF0000; int32_t targLev1 = (int32_t)(targCEshifted & mask); int32_t patLev1 = (int32_t)(patCEshifted & mask); if ( targLev1 != patLev1 ) { if ( targLev1 == 0 ) { return U_CE_SKIP_TARG; } if ( patLev1 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) { return U_CE_SKIP_PATN; } return U_CE_NO_MATCH; } mask = 0x0000FFFF; int32_t targLev2 = (int32_t)(targCEshifted & mask); int32_t patLev2 = (int32_t)(patCEshifted & mask); if ( targLev2 != patLev2 ) { if ( targLev2 == 0 ) { return U_CE_SKIP_TARG; } if ( patLev2 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) { return U_CE_SKIP_PATN; } return (patLev2 == U_CE_LEVEL2_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev2 == U_CE_LEVEL2_BASE) )? U_CE_MATCH: U_CE_NO_MATCH; } mask = 0xFFFF0000; int32_t targLev3 = (int32_t)(targCE & mask); int32_t patLev3 = (int32_t)(patCE & mask); if ( targLev3 != patLev3 ) { return (patLev3 == U_CE_LEVEL3_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev3 == U_CE_LEVEL3_BASE) )? U_CE_MATCH: U_CE_NO_MATCH; } return U_CE_MATCH; } namespace { UChar32 codePointAt(const USearch &search, int32_t index) { if (index < search.textLength) { UChar32 c; U16_NEXT(search.text, index, search.textLength, c); return c; } return U_SENTINEL; } UChar32 codePointBefore(const USearch &search, int32_t index) { if (0 < index) { UChar32 c; U16_PREV(search.text, 0, index, c); return c; } return U_SENTINEL; } } // namespace U_CAPI UBool U_EXPORT2 usearch_search(UStringSearch *strsrch, int32_t startIdx, int32_t *matchStart, int32_t *matchLimit, UErrorCode *status) { if (U_FAILURE(*status)) { return false; } // TODO: reject search patterns beginning with a combining char. #ifdef USEARCH_DEBUG if (getenv("USEARCH_DEBUG") != nullptr) { printf("Pattern CEs\n"); for (int ii=0; iipattern.cesLength; ii++) { printf(" %8x", strsrch->pattern.ces[ii]); } printf("\n"); } #endif // Input parameter sanity check. // TODO: should input indices clip to the text length // in the same way that UText does. if(strsrch->pattern.cesLength == 0 || startIdx < 0 || startIdx > strsrch->search->textLength || strsrch->pattern.ces == nullptr) { *status = U_ILLEGAL_ARGUMENT_ERROR; return false; } if (strsrch->pattern.pces == nullptr) { initializePatternPCETable(strsrch, status); } ucol_setOffset(strsrch->textIter, startIdx, status); CEIBuffer ceb(strsrch, status); // An out-of-memory (OOM) failure can occur in the initializePatternPCETable function // or CEIBuffer constructor above, so we need to check the status. if (U_FAILURE(*status)) { return false; } int32_t targetIx = 0; const CEI *targetCEI = nullptr; int32_t patIx; UBool found; int32_t mStart = -1; int32_t mLimit = -1; int32_t minLimit; int32_t maxLimit; // Outer loop moves over match starting positions in the // target CE space. // Here we see the target as a sequence of collation elements, resulting from the following: // 1. Target characters were decomposed, and (if appropriate) other compressions and expansions are applied // (for example, digraphs such as IJ may be broken into two characters). // 2. An int64_t CE weight is determined for each resulting unit (high 16 bits are primary strength, next // 16 bits are secondary, next 16 (the high 16 bits of the low 32-bit half) are tertiary. Any of these // fields that are for strengths below that of the collator are set to 0. If this makes the int64_t // CE weight 0 (as for a combining diacritic with secondary weight when the collator strength is primary), // then the CE is deleted, so the following code sees only CEs that are relevant. // For each CE, the lowIndex and highIndex correspond to where this CE begins and ends in the original text. // If lowIndex==highIndex, either the CE resulted from an expansion/decomposition of one of the original text // characters, or the CE marks the limit of the target text (in which case the CE weight is UCOL_PROCESSED_NULLORDER). // for(targetIx=0; ; targetIx++) { found = true; // Inner loop checks for a match beginning at each // position from the outer loop. int32_t targetIxOffset = 0; int64_t patCE = 0; // For targetIx > 0, this ceb.get gets a CE that is as far back in the ring buffer // (compared to the last CE fetched for the previous targetIx value) as we need to go // for this targetIx value, so if it is non-nullptr then other ceb.get calls should be OK. const CEI *firstCEI = ceb.get(targetIx); if (firstCEI == nullptr) { *status = U_INTERNAL_PROGRAM_ERROR; found = false; break; } for (patIx=0; patIxpattern.pcesLength; patIx++) { patCE = strsrch->pattern.pces[patIx]; targetCEI = ceb.get(targetIx+patIx+targetIxOffset); // Compare CE from target string with CE from the pattern. // Note that the target CE will be UCOL_PROCESSED_NULLORDER if we reach the end of input, // which will fail the compare, below. UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType); if ( ceMatch == U_CE_NO_MATCH ) { found = false; break; } else if ( ceMatch > U_CE_NO_MATCH ) { if ( ceMatch == U_CE_SKIP_TARG ) { // redo with same patCE, next targCE patIx--; targetIxOffset++; } else { // ceMatch == U_CE_SKIP_PATN // redo with same targCE, next patCE targetIxOffset--; } } } targetIxOffset += strsrch->pattern.pcesLength; // this is now the offset in target CE space to end of the match so far if (!found && ((targetCEI == nullptr) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) { // No match at this targetIx. Try again at the next. continue; } if (!found) { // No match at all, we have run off the end of the target text. break; } // We have found a match in CE space. // Now determine the bounds in string index space. // There still is a chance of match failure if the CE range not correspond to // an acceptable character range. // const CEI *lastCEI = ceb.get(targetIx + targetIxOffset - 1); mStart = firstCEI->lowIndex; minLimit = lastCEI->lowIndex; // Look at the CE following the match. If it is UCOL_NULLORDER the match // extended to the end of input, and the match is good. // Look at the high and low indices of the CE following the match. If // they are the same it means one of two things: // 1. The match extended to the last CE from the target text, which is OK, or // 2. The last CE that was part of the match is in an expansion that extends // to the first CE after the match. In this case, we reject the match. const CEI *nextCEI = 0; if (strsrch->search->elementComparisonType == 0) { nextCEI = ceb.get(targetIx + targetIxOffset); maxLimit = nextCEI->lowIndex; if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) { found = false; } } else { for ( ; ; ++targetIxOffset ) { nextCEI = ceb.get(targetIx + targetIxOffset); maxLimit = nextCEI->lowIndex; // If we are at the end of the target too, match succeeds if ( nextCEI->ce == UCOL_PROCESSED_NULLORDER ) { break; } // As long as the next CE has primary weight of 0, // it is part of the last target element matched by the pattern; // make sure it can be part of a match with the last patCE if ( (((nextCEI->ce) >> 32) & 0xFFFF0000UL) == 0 ) { UCompareCEsResult ceMatch = compareCE64s(nextCEI->ce, patCE, strsrch->search->elementComparisonType); if ( ceMatch == U_CE_NO_MATCH || ceMatch == U_CE_SKIP_PATN ) { found = false; break; } // If lowIndex == highIndex, this target CE is part of an expansion of the last matched // target element, but it has non-zero primary weight => match fails } else if ( nextCEI->lowIndex == nextCEI->highIndex ) { found = false; break; // Else the target CE is not part of an expansion of the last matched element, match succeeds } else { break; } } } // Check for the start of the match being within a combining sequence. // This can happen if the pattern itself begins with a combining char, and // the match found combining marks in the target text that were attached // to something else. // This type of match should be rejected for not completely consuming a // combining sequence. if (!isBreakBoundary(strsrch, mStart, *status)) { found = false; } if (U_FAILURE(*status)) { break; } // Check for the start of the match being within an Collation Element Expansion, // meaning that the first char of the match is only partially matched. // With expansions, the first CE will report the index of the source // character, and all subsequent (expansions) CEs will report the source index of the // _following_ character. int32_t secondIx = firstCEI->highIndex; if (mStart == secondIx) { found = false; } // Allow matches to end in the middle of a grapheme cluster if the following // conditions are met; this is needed to make prefix search work properly in // Indic, see #11750 // * the default breakIter is being used // * the next collation element after this combining sequence // - has non-zero primary weight // - corresponds to a separate character following the one at end of the current match // (the second of these conditions, and perhaps both, may be redundant given the // subsequent check for normalization boundary; however they are likely much faster // tests in any case) // * the match limit is a normalization boundary UBool allowMidclusterMatch = false; if (strsrch->search->text != nullptr && strsrch->search->textLength > maxLimit) { allowMidclusterMatch = strsrch->search->breakIter == nullptr && nextCEI != nullptr && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 && maxLimit >= lastCEI->highIndex && nextCEI->highIndex > maxLimit && (strsrch->nfd->hasBoundaryBefore(codePointAt(*strsrch->search, maxLimit)) || strsrch->nfd->hasBoundaryAfter(codePointBefore(*strsrch->search, maxLimit))); } // If those conditions are met, then: // * do NOT advance the candidate match limit (mLimit) to a break boundary; however // the match limit may be backed off to a previous break boundary. This handles // cases in which mLimit includes target characters that are ignorable with current // settings (such as space) and which extend beyond the pattern match. // * do NOT require that end of the combining sequence not extend beyond the match in CE space // * do NOT require that match limit be on a breakIter boundary // Advance the match end position to the first acceptable match boundary. // This advances the index over any combining characters. mLimit = maxLimit; if (minLimit < maxLimit) { // When the last CE's low index is same with its high index, the CE is likely // a part of expansion. In this case, the index is located just after the // character corresponding to the CEs compared above. If the index is right // at the break boundary, move the position to the next boundary will result // incorrect match length when there are ignorable characters exist between // the position and the next character produces CE(s). See ticket#8482. if (minLimit == lastCEI->highIndex && isBreakBoundary(strsrch, minLimit, *status)) { mLimit = minLimit; } else { int32_t nba = nextBoundaryAfter(strsrch, minLimit, *status); // Note that we can have nba < maxLimit && nba >= minLImit, in which // case we want to set mLimit to nba regardless of allowMidclusterMatch // (i.e. we back off mLimit to the previous breakIterator boundary). if (nba >= lastCEI->highIndex && (!allowMidclusterMatch || nba < maxLimit)) { mLimit = nba; } } } if (U_FAILURE(*status)) { break; } #ifdef USEARCH_DEBUG if (getenv("USEARCH_DEBUG") != nullptr) { printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit); } #endif if (!allowMidclusterMatch) { // If advancing to the end of a combining sequence in character indexing space // advanced us beyond the end of the match in CE space, reject this match. if (mLimit > maxLimit) { found = false; } if (!isBreakBoundary(strsrch, mLimit, *status)) { found = false; } if (U_FAILURE(*status)) { break; } } if (! checkIdentical(strsrch, mStart, mLimit)) { found = false; } if (found) { break; } } #ifdef USEARCH_DEBUG if (getenv("USEARCH_DEBUG") != nullptr) { printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx); int32_t lastToPrint = ceb.limitIx+2; for (int ii=ceb.firstIx; iice, ceb.get(ii)->srcIndex); } printf("\n%s\n", found? "match found" : "no match"); } #endif // All Done. Store back the match bounds to the caller. // if (U_FAILURE(*status)) { found = false; // No match if a failure occured. } if (found==false) { mLimit = -1; mStart = -1; } if (matchStart != nullptr) { *matchStart= mStart; } if (matchLimit != nullptr) { *matchLimit = mLimit; } return found; } U_CAPI UBool U_EXPORT2 usearch_searchBackwards(UStringSearch *strsrch, int32_t startIdx, int32_t *matchStart, int32_t *matchLimit, UErrorCode *status) { if (U_FAILURE(*status)) { return false; } // TODO: reject search patterns beginning with a combining char. #ifdef USEARCH_DEBUG if (getenv("USEARCH_DEBUG") != nullptr) { printf("Pattern CEs\n"); for (int ii=0; iipattern.cesLength; ii++) { printf(" %8x", strsrch->pattern.ces[ii]); } printf("\n"); } #endif // Input parameter sanity check. // TODO: should input indices clip to the text length // in the same way that UText does. if(strsrch->pattern.cesLength == 0 || startIdx < 0 || startIdx > strsrch->search->textLength || strsrch->pattern.ces == nullptr) { *status = U_ILLEGAL_ARGUMENT_ERROR; return false; } if (strsrch->pattern.pces == nullptr) { initializePatternPCETable(strsrch, status); } CEIBuffer ceb(strsrch, status); int32_t targetIx = 0; /* * Pre-load the buffer with the CE's for the grapheme * after our starting position so that we're sure that * we can look at the CE following the match when we * check the match boundaries. * * This will also pre-fetch the first CE that we'll * consider for the match. */ if (startIdx < strsrch->search->textLength) { UBreakIterator *breakiterator = getBreakIterator(strsrch, *status); if (U_FAILURE(*status)) { return false; } int32_t next = ubrk_following(breakiterator, startIdx); ucol_setOffset(strsrch->textIter, next, status); for (targetIx = 0; ; targetIx += 1) { if (ceb.getPrevious(targetIx)->lowIndex < startIdx) { break; } } } else { ucol_setOffset(strsrch->textIter, startIdx, status); } // An out-of-memory (OOM) failure can occur above, so we need to check the status. if (U_FAILURE(*status)) { return false; } const CEI *targetCEI = nullptr; int32_t patIx; UBool found; int32_t limitIx = targetIx; int32_t mStart = -1; int32_t mLimit = -1; int32_t minLimit; int32_t maxLimit; // Outer loop moves over match starting positions in the // target CE space. // Here, targetIx values increase toward the beginning of the base text (i.e. we get the text CEs in reverse order). // But patIx is 0 at the beginning of the pattern and increases toward the end. // So this loop performs a comparison starting with the end of pattern, and prcessd toward the beginning of the pattern // and the beginning of the base text. for(targetIx = limitIx; ; targetIx += 1) { found = true; // For targetIx > limitIx, this ceb.getPrevious gets a CE that is as far back in the ring buffer // (compared to the last CE fetched for the previous targetIx value) as we need to go // for this targetIx value, so if it is non-nullptr then other ceb.getPrevious calls should be OK. const CEI *lastCEI = ceb.getPrevious(targetIx); if (lastCEI == nullptr) { *status = U_INTERNAL_PROGRAM_ERROR; found = false; break; } // Inner loop checks for a match beginning at each // position from the outer loop. int32_t targetIxOffset = 0; for (patIx = strsrch->pattern.pcesLength - 1; patIx >= 0; patIx -= 1) { int64_t patCE = strsrch->pattern.pces[patIx]; targetCEI = ceb.getPrevious(targetIx + strsrch->pattern.pcesLength - 1 - patIx + targetIxOffset); // Compare CE from target string with CE from the pattern. // Note that the target CE will be UCOL_NULLORDER if we reach the end of input, // which will fail the compare, below. UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType); if ( ceMatch == U_CE_NO_MATCH ) { found = false; break; } else if ( ceMatch > U_CE_NO_MATCH ) { if ( ceMatch == U_CE_SKIP_TARG ) { // redo with same patCE, next targCE patIx++; targetIxOffset++; } else { // ceMatch == U_CE_SKIP_PATN // redo with same targCE, next patCE targetIxOffset--; } } } if (!found && ((targetCEI == nullptr) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) { // No match at this targetIx. Try again at the next. continue; } if (!found) { // No match at all, we have run off the end of the target text. break; } // We have found a match in CE space. // Now determine the bounds in string index space. // There still is a chance of match failure if the CE range not correspond to // an acceptable character range. // const CEI *firstCEI = ceb.getPrevious(targetIx + strsrch->pattern.pcesLength - 1 + targetIxOffset); mStart = firstCEI->lowIndex; // Check for the start of the match being within a combining sequence. // This can happen if the pattern itself begins with a combining char, and // the match found combining marks in the target text that were attached // to something else. // This type of match should be rejected for not completely consuming a // combining sequence. if (!isBreakBoundary(strsrch, mStart, *status)) { found = false; } if (U_FAILURE(*status)) { break; } // Look at the high index of the first CE in the match. If it's the same as the // low index, the first CE in the match is in the middle of an expansion. if (mStart == firstCEI->highIndex) { found = false; } minLimit = lastCEI->lowIndex; if (targetIx > 0) { // Look at the CE following the match. If it is UCOL_NULLORDER the match // extended to the end of input, and the match is good. // Look at the high and low indices of the CE following the match. If // they are the same it means one of two things: // 1. The match extended to the last CE from the target text, which is OK, or // 2. The last CE that was part of the match is in an expansion that extends // to the first CE after the match. In this case, we reject the match. const CEI *nextCEI = ceb.getPrevious(targetIx - 1); if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) { found = false; } mLimit = maxLimit = nextCEI->lowIndex; // Allow matches to end in the middle of a grapheme cluster if the following // conditions are met; this is needed to make prefix search work properly in // Indic, see #11750 // * the default breakIter is being used // * the next collation element after this combining sequence // - has non-zero primary weight // - corresponds to a separate character following the one at end of the current match // (the second of these conditions, and perhaps both, may be redundant given the // subsequent check for normalization boundary; however they are likely much faster // tests in any case) // * the match limit is a normalization boundary UBool allowMidclusterMatch = false; if (strsrch->search->text != nullptr && strsrch->search->textLength > maxLimit) { allowMidclusterMatch = strsrch->search->breakIter == nullptr && nextCEI != nullptr && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 && maxLimit >= lastCEI->highIndex && nextCEI->highIndex > maxLimit && (strsrch->nfd->hasBoundaryBefore(codePointAt(*strsrch->search, maxLimit)) || strsrch->nfd->hasBoundaryAfter(codePointBefore(*strsrch->search, maxLimit))); } // If those conditions are met, then: // * do NOT advance the candidate match limit (mLimit) to a break boundary; however // the match limit may be backed off to a previous break boundary. This handles // cases in which mLimit includes target characters that are ignorable with current // settings (such as space) and which extend beyond the pattern match. // * do NOT require that end of the combining sequence not extend beyond the match in CE space // * do NOT require that match limit be on a breakIter boundary // Advance the match end position to the first acceptable match boundary. // This advances the index over any combining characters. if (minLimit < maxLimit) { int32_t nba = nextBoundaryAfter(strsrch, minLimit, *status); // Note that we can have nba < maxLimit && nba >= minLImit, in which // case we want to set mLimit to nba regardless of allowMidclusterMatch // (i.e. we back off mLimit to the previous breakIterator boundary). if (nba >= lastCEI->highIndex && (!allowMidclusterMatch || nba < maxLimit)) { mLimit = nba; } } if (!allowMidclusterMatch) { // If advancing to the end of a combining sequence in character indexing space // advanced us beyond the end of the match in CE space, reject this match. if (mLimit > maxLimit) { found = false; } // Make sure the end of the match is on a break boundary if (!isBreakBoundary(strsrch, mLimit, *status)) { found = false; } if (U_FAILURE(*status)) { break; } } } else { // No non-ignorable CEs after this point. // The maximum position is detected by boundary after // the last non-ignorable CE. Combining sequence // across the start index will be truncated. int32_t nba = nextBoundaryAfter(strsrch, minLimit, *status); mLimit = maxLimit = (nba > 0) && (startIdx > nba) ? nba : startIdx; } #ifdef USEARCH_DEBUG if (getenv("USEARCH_DEBUG") != nullptr) { printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit); } #endif if (! checkIdentical(strsrch, mStart, mLimit)) { found = false; } if (found) { break; } } #ifdef USEARCH_DEBUG if (getenv("USEARCH_DEBUG") != nullptr) { printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx); int32_t lastToPrint = ceb.limitIx+2; for (int ii=ceb.firstIx; iice, ceb.get(ii)->srcIndex); } printf("\n%s\n", found? "match found" : "no match"); } #endif // All Done. Store back the match bounds to the caller. // if (U_FAILURE(*status)) { found = false; // No match if a failure occured. } if (found==false) { mLimit = -1; mStart = -1; } if (matchStart != nullptr) { *matchStart= mStart; } if (matchLimit != nullptr) { *matchLimit = mLimit; } return found; } // internal use methods declared in usrchimp.h ----------------------------- UBool usearch_handleNextExact(UStringSearch *strsrch, UErrorCode *status) { if (U_FAILURE(*status)) { setMatchNotFound(strsrch, *status); return false; } int32_t textOffset = ucol_getOffset(strsrch->textIter); int32_t start = -1; int32_t end = -1; if (usearch_search(strsrch, textOffset, &start, &end, status)) { strsrch->search->matchedIndex = start; strsrch->search->matchedLength = end - start; return true; } else { setMatchNotFound(strsrch, *status); return false; } } UBool usearch_handleNextCanonical(UStringSearch *strsrch, UErrorCode *status) { if (U_FAILURE(*status)) { setMatchNotFound(strsrch, *status); return false; } int32_t textOffset = ucol_getOffset(strsrch->textIter); int32_t start = -1; int32_t end = -1; if (usearch_search(strsrch, textOffset, &start, &end, status)) { strsrch->search->matchedIndex = start; strsrch->search->matchedLength = end - start; return true; } else { setMatchNotFound(strsrch, *status); return false; } } UBool usearch_handlePreviousExact(UStringSearch *strsrch, UErrorCode *status) { if (U_FAILURE(*status)) { setMatchNotFound(strsrch, *status); return false; } int32_t textOffset; if (strsrch->search->isOverlap) { if (strsrch->search->matchedIndex != USEARCH_DONE) { textOffset = strsrch->search->matchedIndex + strsrch->search->matchedLength - 1; } else { // move the start position at the end of possible match initializePatternPCETable(strsrch, status); if (!initTextProcessedIter(strsrch, status)) { setMatchNotFound(strsrch, *status); return false; } for (int32_t nPCEs = 0; nPCEs < strsrch->pattern.pcesLength - 1; nPCEs++) { int64_t pce = strsrch->textProcessedIter->nextProcessed(nullptr, nullptr, status); if (pce == UCOL_PROCESSED_NULLORDER) { // at the end of the text break; } } if (U_FAILURE(*status)) { setMatchNotFound(strsrch, *status); return false; } textOffset = ucol_getOffset(strsrch->textIter); } } else { textOffset = ucol_getOffset(strsrch->textIter); } int32_t start = -1; int32_t end = -1; if (usearch_searchBackwards(strsrch, textOffset, &start, &end, status)) { strsrch->search->matchedIndex = start; strsrch->search->matchedLength = end - start; return true; } else { setMatchNotFound(strsrch, *status); return false; } } UBool usearch_handlePreviousCanonical(UStringSearch *strsrch, UErrorCode *status) { if (U_FAILURE(*status)) { setMatchNotFound(strsrch, *status); return false; } int32_t textOffset; if (strsrch->search->isOverlap) { if (strsrch->search->matchedIndex != USEARCH_DONE) { textOffset = strsrch->search->matchedIndex + strsrch->search->matchedLength - 1; } else { // move the start position at the end of possible match initializePatternPCETable(strsrch, status); if (!initTextProcessedIter(strsrch, status)) { setMatchNotFound(strsrch, *status); return false; } for (int32_t nPCEs = 0; nPCEs < strsrch->pattern.pcesLength - 1; nPCEs++) { int64_t pce = strsrch->textProcessedIter->nextProcessed(nullptr, nullptr, status); if (pce == UCOL_PROCESSED_NULLORDER) { // at the end of the text break; } } if (U_FAILURE(*status)) { setMatchNotFound(strsrch, *status); return false; } textOffset = ucol_getOffset(strsrch->textIter); } } else { textOffset = ucol_getOffset(strsrch->textIter); } int32_t start = -1; int32_t end = -1; if (usearch_searchBackwards(strsrch, textOffset, &start, &end, status)) { strsrch->search->matchedIndex = start; strsrch->search->matchedLength = end - start; return true; } else { setMatchNotFound(strsrch, *status); return false; } } #endif /* #if !UCONFIG_NO_COLLATION */