blob: 95e3f86bbb4d023fe4a9504270725eb16b22b064 [file] [log] [blame]
/*
**********************************************************************
* Copyright (C) 2001-2010 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 "normalizer2impl.h"
#include "ucol_imp.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
#define LENGTHOF(array) (int32_t)(sizeof(array)/sizeof((array)[0]))
// internal definition ---------------------------------------------------
#define LAST_BYTE_MASK_ 0xFF
#define SECOND_LAST_BYTE_SHIFT_ 8
#define SUPPLEMENTARY_MIN_VALUE_ 0x10000
static const uint16_t *fcdTrieIndex = NULL;
static UChar32 fcdHighStart = 0;
// 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)
{
collIterate *ci = &(elems->iteratordata_);
ci->pos = ci->string + offset;
ci->CEpos = ci->toReturn = ci->extendCEs ? ci->extendCEs : ci->CEs;
if (ci->flags & UCOL_ITER_INNORMBUF) {
ci->flags = ci->origFlags;
}
ci->fcdPosition = NULL;
ci->offsetReturn = NULL;
ci->offsetStore = ci->offsetBuffer;
ci->offsetRepeatCount = ci->offsetRepeatValue = 0;
}
/**
* 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;
}
}
/**
* This is to squeeze the 21bit ces into a 256 table
* @param ce collation element
* @return collapsed version of the collation element
*/
static
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
// are of the value xx000xxx. their hashes will most of the time be 0
// to be discussed on the hash algo.
return UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_;
}
U_CDECL_BEGIN
static UBool U_CALLCONV
usearch_cleanup(void) {
fcdTrieIndex = NULL;
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 (fcdTrieIndex == NULL) {
fcdTrieIndex = unorm_getFCDTrieIndex(fcdHighStart, 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 UChar *str, int32_t *offset,
int32_t strlength)
{
const UChar *temp = str + *offset;
uint16_t result = unorm_nextFCD16(fcdTrieIndex, fcdHighStart, 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 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
* method, status assumed to be success when passed in.
* @return newly allocated array, NULL otherwise
*/
static
inline void * allocateMemory(uint32_t size, UErrorCode *status)
{
uint32_t *result = (uint32_t *)uprv_malloc(size);
if (result == NULL) {
*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 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 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 NULL;
}
uprv_memcpy(temp, destination, sizeof(int32_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 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
* 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 initializePatternCETable(UStringSearch *strsrch,
UErrorCode *status)
{
UPattern *pattern = &(strsrch->pattern);
uint32_t cetablesize = INITIAL_ARRAY_SIZE_;
int32_t *cetable = pattern->CEBuffer;
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 {
uprv_init_collIterate(strsrch->collator, pattern->text,
pattern->textLength,
&coleiter->iteratordata_,
status);
}
if(U_FAILURE(*status)) {
return 0;
}
if (pattern->CE != cetable && pattern->CE) {
uprv_free(pattern->CE);
}
uint16_t offset = 0;
uint16_t result = 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 0;
}
offset ++;
if (cetable != temp && cetable != pattern->CEBuffer) {
uprv_free(cetable);
}
cetable = temp;
}
result += (uint16_t)(ucol_getMaxExpansion(coleiter, ce) - 1);
}
cetable[offset] = 0;
pattern->CE = cetable;
pattern->CELength = 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->PCEBuffer;
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 {
uprv_init_collIterate(strsrch->collator, pattern->text,
pattern->textLength,
&coleiter->iteratordata_,
status);
}
if(U_FAILURE(*status)) {
return 0;
}
if (pattern->PCE != pcetable && pattern->PCE != NULL) {
uprv_free(pattern->PCE);
}
uint16_t offset = 0;
uint16_t result = 0;
int64_t pce;
uprv_init_pce(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 = ucol_nextProcessed(coleiter, 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->PCEBuffer) {
uprv_free(pcetable);
}
pcetable = temp;
//result += (uint16_t)(ucol_getMaxExpansion(coleiter, ce) - 1);
}
pcetable[offset] = 0;
pattern->PCE = pcetable;
pattern->PCELength = offset;
return result;
}
/**
* 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
* 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)
{
UPattern *pattern = &(strsrch->pattern);
const UChar *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;
UTF_BACK_1(patterntext, 0, index);
pattern->hasSuffixAccents = getFCD(patterntext, &index, length) &
LAST_BYTE_MASK_;
}
// ** HACK **
if (strsrch->pattern.PCE != NULL) {
if (strsrch->pattern.PCE != strsrch->pattern.PCEBuffer) {
uprv_free(strsrch->pattern.PCE);
}
strsrch->pattern.PCE = NULL;
}
// since intializePattern is an internal method status is a success.
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 backshift table for backwards shift
* @param cetable table containing pattern ce
* @param cesize size of the pattern ces
* @param expansionsize total size of the expansions
* @param defaultforward the default forward value
* @param defaultbackward the default backward value
*/
static
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
// number of characters to give the relevant ces, ie approximately
// 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 ++) {
shift[count] = defaultforward;
}
cesize --; // down to the last index
for (count = 0; count < cesize; count ++) {
// number of ces from right of array to the count
int temp = defaultforward - count - 1;
shift[hash(cetable[count])] = temp > 1 ? temp : 1;
}
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 ?
(int16_t)(count - expansionsize) : 1;
}
backshift[hash(cetable[0])] = 1;
backshift[hash(0)] = 1;
}
/**
* Building of the pattern collation element list and the boyer moore strsrch
* table.
* 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
* 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
* 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
* 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.
* If pattern has no non-ignorable ce, we return a illegal argument error.
* Internal method, status assumed to be success.
* @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)
{
int16_t expandlength = initializePattern(strsrch, status);
if (U_SUCCESS(*status) && strsrch->pattern.CELength > 0) {
UPattern *pattern = &strsrch->pattern;
int32_t cesize = pattern->CELength;
int16_t minlength = cesize > expandlength
? (int16_t)cesize - expandlength : 1;
pattern->defaultShiftSize = minlength;
setShiftTable(pattern->shift, pattern->backShift, pattern->CE,
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
* determined by the breakiterator in UStringSearch.
* @param strsrch string search data
* @param start target text start offset
* @param end target text end offset
*/
static
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
// one the user specified
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 +
start;
UErrorCode status = U_ZERO_ERROR;
ucol_setText(coleiter, text, end - start, &status);
for (int32_t count = 0; count < strsrch->pattern.CELength;
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]) {
return FALSE;
}
}
int32_t nextce = ucol_next(coleiter, &status);
while (ucol_getOffset(coleiter) == (end - start)
&& getCE(strsrch, nextce) == UCOL_IGNORABLE) {
nextce = ucol_next(coleiter, &status);
}
if (ucol_getOffset(coleiter) == (end - start)
&& nextce != UCOL_NULLORDER) {
// extra collation elements at the end of the match
return FALSE;
}
}
return result;
}
#endif
return TRUE;
}
/**
* 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
* @param textlength length of text string
* @return the next base character or the current offset
* if the current character is contains a base character.
*/
static
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) {
int32_t result = temp;
if ((getFCD(text, &temp, textlength) >>
SECOND_LAST_BYTE_SHIFT_) == 0) {
return result;
}
}
return textlength;
}
}
return textoffset;
}
/**
* Gets the next base character offset depending on the string search pattern
* data
* @param strsrch string search data
* @param textoffset current offset, one offset away from the last character
* to search for.
* @return start index of the next base character or the current offset
* if the current character is contains a base character.
*/
static
inline int32_t getNextUStringSearchBaseOffset(UStringSearch *strsrch,
int32_t textoffset)
{
int32_t textlength = strsrch->search->textLength;
if (strsrch->pattern.hasSuffixAccents &&
textoffset < textlength) {
int32_t temp = textoffset;
const UChar *text = strsrch->search->text;
UTF_BACK_1(text, 0, temp);
if (getFCD(text, &temp, textlength) & LAST_BYTE_MASK_) {
return getNextBaseOffset(text, textoffset, textlength);
}
}
return textoffset;
}
/**
* Shifting the collation element iterator position forward to prepare for
* a following match. If the last character is a unsafe character, we'll only
* shift by 1 to capture contractions, normalization etc.
* Internal method, status assumed to be success.
* @param text strsrch string search data
* @param textoffset start text position to do search
* @param ce the text ce which failed the match.
* @param patternceindex index of the ce within the pattern ce buffer which
* failed the match
* @return final offset
*/
static
inline int32_t shiftForward(UStringSearch *strsrch,
int32_t textoffset,
int32_t ce,
int32_t patternceindex)
{
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
// substring for matching that failed.
int32_t adjust = pattern->CELength - patternceindex;
if (adjust > 1 && shift >= adjust) {
shift -= adjust - 1;
}
textoffset += shift;
}
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
// 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
* @param strsrch string search data
*/
static
inline void setMatchNotFound(UStringSearch *strsrch)
{
// this method resets the match result regardless of the error status.
strsrch->search->matchedIndex = USEARCH_DONE;
strsrch->search->matchedLength = 0;
if (strsrch->search->isForwardSearching) {
setColEIterOffset(strsrch->textIter, strsrch->search->textLength);
}
else {
setColEIterOffset(strsrch->textIter, 0);
}
}
#if BOYER_MOORE
/**
* Gets the offset to the next safe point in text.
* ie. not the middle of a contraction, swappable characters or supplementary
* characters.
* @param collator collation sata
* @param text string to work with
* @param textoffset offset in string
* @param textlength length of text string
* @return offset to the next safe character
*/
static
inline int32_t getNextSafeOffset(const UCollator *collator,
const UChar *text,
int32_t textoffset,
int32_t textlength)
{
int32_t result = textoffset; // first contraction character
while (result != textlength && ucol_unsafeCP(text[result], collator)) {
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
* the immediate decomposed character before the match.
* 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
* determine that the potential match has extra non-ignorable preceding
* ces.
* 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
* before calling this method
* @param strsrch string search data
* @param start index of the potential unfriendly composite character
* @param end index of the potential unfriendly composite character
* @param status output error status if any.
* @return TRUE if there is non-ignorable accents before at the beginning
* of the match, FALSE otherwise.
*/
static
UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start,
int32_t end,
UErrorCode *status)
{
UBool result = FALSE;
if (strsrch->pattern.hasPrefixAccents) {
int32_t length = end - start;
int32_t offset = 0;
const UChar *text = strsrch->search->text + start;
UTF_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,
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);
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
// U_MEMORY_ALLOCATION_ERROR and unorm_normalize internally
// checks for it.
size = unorm_normalize(text, safeoffset, UNORM_NFD, 0, norm,
size, status);
if (U_FAILURE(*status) && norm != NULL) {
uprv_free(norm);
return FALSE;
}
}
else {
norm = buffer;
}
UCollationElements *coleiter = strsrch->utilIter;
ucol_setText(coleiter, norm, size, status);
uint32_t firstce = strsrch->pattern.CE[0];
UBool ignorable = TRUE;
uint32_t ce = UCOL_IGNORABLE;
while (U_SUCCESS(*status) && ce != firstce && ce != (uint32_t)UCOL_NULLORDER) {
offset = ucol_getOffset(coleiter);
if (ce != firstce && ce != UCOL_IGNORABLE) {
ignorable = FALSE;
}
ce = ucol_next(coleiter, status);
}
UChar32 codepoint;
UTF_PREV_CHAR(norm, 0, offset, codepoint);
result = !ignorable && (u_getCombiningClass(codepoint) != 0);
if (norm != buffer) {
uprv_free(norm);
}
}
}
return result;
}
/**
* 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 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
* 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
* 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,
* 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 end offset
* @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)
{
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];
setColEIterOffset(coleiter, start);
int32_t ce = getCE(strsrch, ucol_next(coleiter, &status));
if (U_FAILURE(status)) {
return TRUE;
}
while (ce != firstce) {
if (ce != UCOL_IGNORABLE) {
ignorable = FALSE;
}
ce = getCE(strsrch, ucol_next(coleiter, &status));
if (U_FAILURE(status) || ce == UCOL_NULLORDER) {
return TRUE;
}
}
if (!ignorable && inNormBuf(coleiter)) {
// within normalization buffer, discontiguous handled here
return TRUE;
}
// within text
int32_t temp = start;
// original code
// 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
// VC7. anyways this is a work around.
UBool accent = getFCD(strsrch->search->text, &temp,
strsrch->search->textLength) > 0xFF;
if (!accent) {
return checkExtraMatchAccents(strsrch, start, end, &status);
}
if (!ignorable) {
return TRUE;
}
if (start > 0) {
temp = start;
UTF_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) ||
(ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE)) {
return TRUE;
}
}
}
}
return FALSE;
}
/**
* Used by exact matches, checks if there are accents bounding the match.
* 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
* backwards collation element iterator, use up too many characters.
* 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,
* FALSE otherwise
*/
static
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);
if (getFCD(text, &temp, textlength) & LAST_BYTE_MASK_) {
int32_t firstce = strsrch->pattern.CE[0];
UCollationElements *coleiter = strsrch->textIter;
UErrorCode status = U_ZERO_ERROR;
int32_t ce;
setColEIterOffset(coleiter, start);
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))
== UCOL_IGNORABLE) {
// Thai can give an ignorable here.
count --;
}
if (U_FAILURE(status)) {
return TRUE;
}
count ++;
}
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;
}
if (getFCD(text, &end, textlength) >> SECOND_LAST_BYTE_SHIFT_) {
return TRUE;
}
}
}
}
return FALSE;
}
#endif // #if BOYER_MOORE
/**
* 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;
}
#if BOYER_MOORE
/**
* Checks to see if the match is repeated
* @param strsrch string search data
* @param start new match start index
* @param end new match end index
* @return TRUE if the the match is repeated, FALSE otherwise
*/
static
inline UBool checkRepeatedMatch(UStringSearch *strsrch,
int32_t start,
int32_t end)
{
int32_t lastmatchindex = strsrch->search->matchedIndex;
UBool result;
if (lastmatchindex == USEARCH_DONE) {
return FALSE;
}
if (strsrch->search->isForwardSearching) {
result = start <= lastmatchindex;
}
else {
result = start >= lastmatchindex;
}
if (!result && !strsrch->search->isOverlap) {
if (strsrch->search->isForwardSearching) {
result = start < lastmatchindex + strsrch->search->matchedLength;
}
else {
result = end > lastmatchindex;
}
}
return result;
}
/**
* 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
*/
static
inline int32_t getColElemIterOffset(const UCollationElements *coleiter,
UBool forwards)
{
int32_t result = ucol_getOffset(coleiter);
// intricacies of the the backwards collation element iterator
if (FALSE && !forwards && inNormBuf(coleiter) && !isFCDPointerNull(coleiter)) {
result ++;
}
return result;
}
/**
* 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
* before calling this method.
* @param strsrch string search data
* @param start offset of potential match, to be modified if necessary
* @param end offset of potential match, to be modified if necessary
* @param status output error status if any
* @return TRUE if match passes the contraction test, FALSE otherwise
*/
static
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;
const UCollator *collator = strsrch->collator;
const UChar *text = strsrch->search->text;
// 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
// results.
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
// 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
// have to skip the first ce in the expansion buffer.
ucol_next(coleiter, status);
if (U_FAILURE(*status)) {
return FALSE;
}
if (ucol_getOffset(coleiter) != temp) {
*start = temp;
temp = ucol_getOffset(coleiter);
}
expansion --;
}
int32_t *patternce = strsrch->pattern.CE;
int32_t patterncelength = strsrch->pattern.CELength;
int32_t count = 0;
while (count < patterncelength) {
int32_t ce = getCE(strsrch, ucol_next(coleiter, status));
if (ce == UCOL_IGNORABLE) {
continue;
}
if (expandflag && count == 0 && ucol_getOffset(coleiter) != temp) {
*start = temp;
temp = ucol_getOffset(coleiter);
}
if (U_FAILURE(*status) || ce != patternce[count]) {
(*end) ++;
*end = getNextUStringSearchBaseOffset(strsrch, *end);
return FALSE;
}
count ++;
}
}
return TRUE;
}
/**
* Checks and sets the match information if found.
* Checks
* <ul>
* <li> the potential match does not repeat the previous match
* <li> boundaries are correct
* <li> exact matches has no extra accents
* <li> identical matchesb
* <li> potential match does not end in the middle of a contraction
* <\ul>
* Otherwise the offset will be shifted to the next character.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param textoffset offset in the collation element text. the returned value
* will be the truncated end offset of the match or the new start
* search offset.
* @param status output error status if any
* @return TRUE if the match is valid, FALSE otherwise
*/
static
inline UBool checkNextExactMatch(UStringSearch *strsrch,
int32_t *textoffset, UErrorCode *status)
{
UCollationElements *coleiter = strsrch->textIter;
int32_t start = getColElemIterOffset(coleiter, FALSE);
if (!checkNextExactContractionMatch(strsrch, &start, textoffset, status)) {
return FALSE;
}
// this totally matches, however we need to check if it is repeating
if (!isBreakUnit(strsrch, start, *textoffset) ||
checkRepeatedMatch(strsrch, start, *textoffset) ||
hasAccentsBeforeMatch(strsrch, start, *textoffset) ||
!checkIdentical(strsrch, start, *textoffset) ||
hasAccentsAfterMatch(strsrch, start, *textoffset)) {
(*textoffset) ++;
*textoffset = getNextUStringSearchBaseOffset(strsrch, *textoffset);
return FALSE;
}
//Add breakiterator boundary check for primary strength search.
if (!strsrch->search->breakIter && strsrch->strength == UCOL_PRIMARY) {
checkBreakBoundary(strsrch, &start, textoffset);
}
// totally match, we will get rid of the ending ignorables.
strsrch->search->matchedIndex = start;
strsrch->search->matchedLength = *textoffset - start;
return TRUE;
}
/**
* Getting the previous base character offset, or the current offset if the
* current character is a base character
* @param text string
* @param textoffset one offset after the current character
* @return the offset of the next character after the base character or the first
* composed character with accents
*/
static
inline int32_t getPreviousBaseOffset(const UChar *text,
int32_t textoffset)
{
if (textoffset > 0) {
for (;;) {
int32_t result = textoffset;
UTF_BACK_1(text, 0, textoffset);
int32_t temp = textoffset;
uint16_t fcd = getFCD(text, &temp, result);
if ((fcd >> SECOND_LAST_BYTE_SHIFT_) == 0) {
if (fcd & LAST_BYTE_MASK_) {
return textoffset;
}
return result;
}
if (textoffset == 0) {
return 0;
}
}
}
return textoffset;
}
/**
* Getting the indexes of the accents that are not blocked in the argument
* accent array
* @param accents array of accents in nfd terminated by a 0.
* @param accentsindex array of indexes of the accents that are not blocked
*/
static
inline int getUnblockedAccentIndex(UChar *accents, int32_t *accentsindex)
{
int32_t index = 0;
int32_t length = u_strlen(accents);
UChar32 codepoint = 0;
int cclass = 0;
int result = 0;
int32_t temp;
while (index < length) {
temp = index;
UTF_NEXT_CHAR(accents, index, length, codepoint);
if (u_getCombiningClass(codepoint) != cclass) {
cclass = u_getCombiningClass(codepoint);
accentsindex[result] = temp;
result ++;
}
}
accentsindex[result] = length;
return result;
}
/**
* Appends 3 UChar arrays 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 destinationlength target array size, returning the appended length
* @param source1 null-terminated first array
* @param source2 second array
* @param source2length length of seond array
* @param source3 null-terminated third array
* @param status error status if any
* @return new destination array, destination if there was no new allocation
*/
static
inline UChar * addToUCharArray( UChar *destination,
int32_t *destinationlength,
const UChar *source1,
const UChar *source2,
int32_t source2length,
const UChar *source3,
UErrorCode *status)
{
int32_t source1length = source1 ? u_strlen(source1) : 0;
int32_t source3length = source3 ? u_strlen(source3) : 0;
if (*destinationlength < source1length + source2length + source3length +
1)
{
destination = (UChar *)allocateMemory(
(source1length + source2length + source3length + 1) * sizeof(UChar),
status);
// if error allocating memory, status will be
// U_MEMORY_ALLOCATION_ERROR
if (U_FAILURE(*status)) {
*destinationlength = 0;
return NULL;
}
}
if (source1length != 0) {
uprv_memcpy(destination, source1, sizeof(UChar) * source1length);
}
if (source2length != 0) {
uprv_memcpy(destination + source1length, source2,
sizeof(UChar) * source2length);
}
if (source3length != 0) {
uprv_memcpy(destination + source1length + source2length, source3,
sizeof(UChar) * source3length);
}
*destinationlength = source1length + source2length + source3length;
return destination;
}
/**
* Running through a collation element iterator to see if the contents matches
* pattern in string search data
* @param strsrch string search data
* @param coleiter collation element iterator
* @return TRUE if a match if found, FALSE otherwise
*/
static
inline UBool checkCollationMatch(const UStringSearch *strsrch,
UCollationElements *coleiter)
{
int patternceindex = strsrch->pattern.CELength;
int32_t *patternce = strsrch->pattern.CE;
UErrorCode status = U_ZERO_ERROR;
while (patternceindex > 0) {
int32_t ce = getCE(strsrch, ucol_next(coleiter, &status));
if (ce == UCOL_IGNORABLE) {
continue;
}
if (U_FAILURE(status) || ce != *patternce) {
return FALSE;
}
patternce ++;
patternceindex --;
}
return TRUE;
}
/**
* Rearranges the front accents to try matching.
* Prefix accents in the text will be grouped according to their combining
* class and the groups will be mixed and matched to try find the perfect
* match with the pattern.
* So for instance looking for "\u0301" in "\u030A\u0301\u0325"
* step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
* "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
* "\u0301\u0325".
* step 2: check if any of the generated substrings matches the pattern.
* Internal method, status is assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search match
* @param start first offset of the accents to start searching
* @param end start of the last accent set
* @param status output error status if any
* @return USEARCH_DONE if a match is not found, otherwise return the starting
* offset of the match. Note this start includes all preceding accents.
*/
static
int32_t doNextCanonicalPrefixMatch(UStringSearch *strsrch,
int32_t start,
int32_t end,
UErrorCode *status)
{
const UChar *text = strsrch->search->text;
int32_t textlength = strsrch->search->textLength;
int32_t tempstart = start;
if ((getFCD(text, &tempstart, textlength) & LAST_BYTE_MASK_) == 0) {
// die... failed at a base character
return USEARCH_DONE;
}
int32_t offset = getNextBaseOffset(text, tempstart, textlength);
start = getPreviousBaseOffset(text, tempstart);
UChar accents[INITIAL_ARRAY_SIZE_];
// normalizing the offensive string
unorm_normalize(text + start, offset - start, UNORM_NFD, 0, accents,
INITIAL_ARRAY_SIZE_, status);
if (U_FAILURE(*status)) {
return USEARCH_DONE;
}
int32_t accentsindex[INITIAL_ARRAY_SIZE_];
int32_t accentsize = getUnblockedAccentIndex(accents,
accentsindex);
int32_t count = (2 << (accentsize - 1)) - 1;
UChar buffer[INITIAL_ARRAY_SIZE_];
UCollationElements *coleiter = strsrch->utilIter;
while (U_SUCCESS(*status) && count > 0) {
UChar *rearrange = strsrch->canonicalPrefixAccents;
// copy the base characters
for (int k = 0; k < accentsindex[0]; k ++) {
*rearrange ++ = accents[k];
}
// forming all possible canonical rearrangement by dropping
// sets of accents
for (int i = 0; i <= accentsize - 1; i ++) {
int32_t mask = 1 << (accentsize - i - 1);
if (count & mask) {
for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
*rearrange ++ = accents[j];
}
}
}
*rearrange = 0;
int32_t matchsize = INITIAL_ARRAY_SIZE_;
UChar *match = addToUCharArray(buffer, &matchsize,
strsrch->canonicalPrefixAccents,
strsrch->search->text + offset,
end - offset,
strsrch->canonicalSuffixAccents,
status);
// if status is a failure, ucol_setText does nothing.
// run the collator iterator through this match
ucol_setText(coleiter, match, matchsize, status);
if (U_SUCCESS(*status)) {
if (checkCollationMatch(strsrch, coleiter)) {
if (match != buffer) {
uprv_free(match);
}
return start;
}
}
count --;
}
return USEARCH_DONE;
}
/**
* Gets the offset to the safe point in text before textoffset.
* ie. not the middle of a contraction, swappable characters or supplementary
* characters.
* @param collator collation sata
* @param text string to work with
* @param textoffset offset in string
* @param textlength length of text string
* @return offset to the previous safe character
*/
static
inline uint32_t getPreviousSafeOffset(const UCollator *collator,
const UChar *text,
int32_t textoffset)
{
int32_t result = textoffset; // first contraction character
while (result != 0 && ucol_unsafeCP(text[result - 1], collator)) {
result --;
}
if (result != 0) {
// the first contraction character is consider unsafe here
result --;
}
return result;
}
/**
* Cleaning up after we passed the safe zone
* @param strsrch string search data
* @param safetext safe text array
* @param safebuffer safe text buffer
* @param coleiter collation element iterator for safe text
*/
static
inline void cleanUpSafeText(const UStringSearch *strsrch, UChar *safetext,
UChar *safebuffer)
{
if (safetext != safebuffer && safetext != strsrch->canonicalSuffixAccents)
{
uprv_free(safetext);
}
}
/**
* Take the rearranged end accents and tries matching. If match failed at
* a seperate preceding set of accents (seperated from the rearranged on by
* at least a base character) then we rearrange the preceding accents and
* tries matching again.
* We allow skipping of the ends of the accent set if the ces do not match.
* However if the failure is found before the accent set, it fails.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param textoffset of the start of the rearranged accent
* @param status output error status if any
* @return USEARCH_DONE if a match is not found, otherwise return the starting
* offset of the match. Note this start includes all preceding accents.
*/
static
int32_t doNextCanonicalSuffixMatch(UStringSearch *strsrch,
int32_t textoffset,
UErrorCode *status)
{
const UChar *text = strsrch->search->text;
const UCollator *collator = strsrch->collator;
int32_t safelength = 0;
UChar *safetext;
int32_t safetextlength;
UChar safebuffer[INITIAL_ARRAY_SIZE_];
UCollationElements *coleiter = strsrch->utilIter;
int32_t safeoffset = textoffset;
if (textoffset != 0 && ucol_unsafeCP(strsrch->canonicalSuffixAccents[0],
collator)) {
safeoffset = getPreviousSafeOffset(collator, text, textoffset);
safelength = textoffset - safeoffset;
safetextlength = INITIAL_ARRAY_SIZE_;
safetext = addToUCharArray(safebuffer, &safetextlength, NULL,
text + safeoffset, safelength,
strsrch->canonicalSuffixAccents,
status);
}
else {
safetextlength = u_strlen(strsrch->canonicalSuffixAccents);
safetext = strsrch->canonicalSuffixAccents;
}
// if status is a failure, ucol_setText does nothing
ucol_setText(coleiter, safetext, safetextlength, status);
// status checked in loop below
int32_t *ce = strsrch->pattern.CE;
int32_t celength = strsrch->pattern.CELength;
int ceindex = celength - 1;
UBool isSafe = TRUE; // indication flag for position in safe zone
while (ceindex >= 0) {
int32_t textce = ucol_previous(coleiter, status);
if (U_FAILURE(*status)) {
if (isSafe) {
cleanUpSafeText(strsrch, safetext, safebuffer);
}
return USEARCH_DONE;
}
if (textce == UCOL_NULLORDER) {
// check if we have passed the safe buffer
if (coleiter == strsrch->textIter) {
cleanUpSafeText(strsrch, safetext, safebuffer);
return USEARCH_DONE;
}
cleanUpSafeText(strsrch, safetext, safebuffer);
safetext = safebuffer;
coleiter = strsrch->textIter;
setColEIterOffset(coleiter, safeoffset);
// status checked at the start of the loop
isSafe = FALSE;
continue;
}
textce = getCE(strsrch, textce);
if (textce != UCOL_IGNORABLE && textce != ce[ceindex]) {
// do the beginning stuff
int32_t failedoffset = getColElemIterOffset(coleiter, FALSE);
if (isSafe && failedoffset >= safelength) {
// alas... no hope. failed at rearranged accent set
cleanUpSafeText(strsrch, safetext, safebuffer);
return USEARCH_DONE;
}
else {
if (isSafe) {
failedoffset += safeoffset;
cleanUpSafeText(strsrch, safetext, safebuffer);
}
// try rearranging the front accents
int32_t result = doNextCanonicalPrefixMatch(strsrch,
failedoffset, textoffset, status);
if (result != USEARCH_DONE) {
// if status is a failure, ucol_setOffset does nothing
setColEIterOffset(strsrch->textIter, result);
}
if (U_FAILURE(*status)) {
return USEARCH_DONE;
}
return result;
}
}
if (textce == ce[ceindex]) {
ceindex --;
}
}
// set offset here
if (isSafe) {
int32_t result = getColElemIterOffset(coleiter, FALSE);
// sets the text iterator here with the correct expansion and offset
int32_t leftoverces = getExpansionPrefix(coleiter);
cleanUpSafeText(strsrch, safetext, safebuffer);
if (result >= safelength) {
result = textoffset;
}
else {
result += safeoffset;
}
setColEIterOffset(strsrch->textIter, result);
strsrch->textIter->iteratordata_.toReturn =
setExpansionPrefix(strsrch->textIter, leftoverces);
return result;
}
return ucol_getOffset(coleiter);
}
/**
* Trying out the substring and sees if it can be a canonical match.
* This will try normalizing the end accents and arranging them into canonical
* equivalents and check their corresponding ces with the pattern ce.
* Suffix accents in the text will be grouped according to their combining
* class and the groups will be mixed and matched to try find the perfect
* match with the pattern.
* So for instance looking for "\u0301" in "\u030A\u0301\u0325"
* step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
* "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
* "\u0301\u0325".
* step 2: check if any of the generated substrings matches the pattern.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param textoffset end offset in the collation element text that ends with
* the accents to be rearranged
* @param status error status if any
* @return TRUE if the match is valid, FALSE otherwise
*/
static
UBool doNextCanonicalMatch(UStringSearch *strsrch,
int32_t textoffset,
UErrorCode *status)
{
const UChar *text = strsrch->search->text;
int32_t temp = textoffset;
UTF_BACK_1(text, 0, temp);
if ((getFCD(text, &temp, textoffset) & LAST_BYTE_MASK_) == 0) {
UCollationElements *coleiter = strsrch->textIter;
int32_t offset = getColElemIterOffset(coleiter, FALSE);
if (strsrch->pattern.hasPrefixAccents) {
offset = doNextCanonicalPrefixMatch(strsrch, offset, textoffset,
status);
if (U_SUCCESS(*status) && offset != USEARCH_DONE) {
setColEIterOffset(coleiter, offset);
return TRUE;
}
}
return FALSE;
}
if (!strsrch->pattern.hasSuffixAccents) {
return FALSE;
}
UChar accents[INITIAL_ARRAY_SIZE_];
// offset to the last base character in substring to search
int32_t baseoffset = getPreviousBaseOffset(text, textoffset);
// normalizing the offensive string
unorm_normalize(text + baseoffset, textoffset - baseoffset, UNORM_NFD,
0, accents, INITIAL_ARRAY_SIZE_, status);
// status checked in loop below
int32_t accentsindex[INITIAL_ARRAY_SIZE_];
int32_t size = getUnblockedAccentIndex(accents, accentsindex);
// 2 power n - 1 plus the full set of accents
int32_t count = (2 << (size - 1)) - 1;
while (U_SUCCESS(*status) && count > 0) {
UChar *rearrange = strsrch->canonicalSuffixAccents;
// copy the base characters
for (int k = 0; k < accentsindex[0]; k ++) {
*rearrange ++ = accents[k];
}
// forming all possible canonical rearrangement by dropping
// sets of accents
for (int i = 0; i <= size - 1; i ++) {
int32_t mask = 1 << (size - i - 1);
if (count & mask) {
for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
*rearrange ++ = accents[j];
}
}
}
*rearrange = 0;
int32_t offset = doNextCanonicalSuffixMatch(strsrch, baseoffset,
status);
if (offset != USEARCH_DONE) {
return TRUE; // match found
}
count --;
}
return FALSE;
}
/**
* Gets the previous base character offset depending on the string search
* pattern data
* @param strsrch string search data
* @param textoffset current offset, current character
* @return the offset of the next character after this base character or itself
* if it is a composed character with accents
*/
static
inline int32_t getPreviousUStringSearchBaseOffset(UStringSearch *strsrch,
int32_t textoffset)
{
if (strsrch->pattern.hasPrefixAccents && textoffset > 0) {
const UChar *text = strsrch->search->text;
int32_t offset = textoffset;
if (getFCD(text, &offset, strsrch->search->textLength) >>
SECOND_LAST_BYTE_SHIFT_) {
return getPreviousBaseOffset(text, textoffset);
}
}
return textoffset;
}
/**
* 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
* Internal method, status 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
* @param end offset of potential match, to be modified if necessary
* @param status output error status if any
* @return TRUE if match passes the contraction test, FALSE otherwise
*/
static
UBool checkNextCanonicalContractionMatch(UStringSearch *strsrch,
int32_t *start,
int32_t *end,
UErrorCode *status)
{
UCollationElements *coleiter = strsrch->textIter;
int32_t textlength = strsrch->search->textLength;
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
// contraction. If so we'll have to iterate through them
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
// 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
// have to skip the first ce in the expansion buffer.
ucol_next(coleiter, status);
if (U_FAILURE(*status)) {
return FALSE;
}
if (ucol_getOffset(coleiter) != temp) {
*start = temp;
temp = ucol_getOffset(coleiter);
}
expansion --;
}
int32_t *patternce = strsrch->pattern.CE;
int32_t patterncelength = strsrch->pattern.CELength;
int32_t count = 0;
int32_t textlength = strsrch->search->textLength;
while (count < patterncelength) {
int32_t ce = getCE(strsrch, ucol_next(coleiter, status));
// status checked below, note that if status is a failure
// ucol_next returns UCOL_NULLORDER
if (ce == UCOL_IGNORABLE) {
continue;
}
if (expandflag && count == 0 && ucol_getOffset(coleiter) != temp) {
*start = temp;
temp = ucol_getOffset(coleiter);
}
if (count == 0 && ce != patternce[0]) {
// accents may have extra starting ces, this occurs when a
// pure accent pattern is matched without rearrangement
// text \u0325\u0300 and looking for \u0300
int32_t expected = patternce[0];
if (getFCD(text, start, textlength) & LAST_BYTE_MASK_) {
ce = getCE(strsrch, ucol_next(coleiter, status));
while (U_SUCCESS(*status) && ce != expected &&
ce != UCOL_NULLORDER &&
ucol_getOffset(coleiter) <= *end) {
ce = getCE(strsrch, ucol_next(coleiter, status));
}
}
}
if (U_FAILURE(*status) || ce != patternce[count]) {
(*end) ++;
*end = getNextUStringSearchBaseOffset(strsrch, *end);
return FALSE;
}
count ++;
}
}
return TRUE;
}
/**
* Checks and sets the match information if found.
* Checks
* <ul>
* <li> the potential match does not repeat the previous match
* <li> boundaries are correct
* <li> potential match does not end in the middle of a contraction
* <li> identical matches
* <\ul>
* Otherwise the offset will be shifted to the next character.
* Internal method, status assumed to be success, caller has to check the
* status before calling this method.
* @param strsrch string search data
* @param textoffset offset in the collation element text. the returned value
* will be the truncated end offset of the match or the new start
* search offset.
* @param status output error status if any
* @return TRUE if the match is valid, FALSE otherwise
*/
static
inline UBool checkNextCanonicalMatch(UStringSearch *strsrch,
int32_t *textoffset,
UErrorCode *status)
{
// to ensure that the start and ends are not composite characters
UCollationElements *coleiter = strsrch->textIter;
// if we have a canonical accent match
if ((strsrch->pattern.hasSuffixAccents &&
strsrch->canonicalSuffixAccents[0]) ||
(strsrch->pattern.hasPrefixAccents &&
strsrch->canonicalPrefixAccents[0])) {
strsrch->search->matchedIndex = getPreviousUStringSearchBaseOffset(
strsrch,
ucol_getOffset(coleiter));
strsrch->search->matchedLength = *textoffset -
strsrch->search->matchedIndex;
return TRUE;
}
int32_t start = getColElemIterOffset(coleiter, FALSE);
if (!checkNextCanonicalContractionMatch(strsrch, &start, textoffset,
status) || U_FAILURE(*status)) {
return FALSE;
}
start = getPreviousUStringSearchBaseOffset(strsrch, start);
// this totally matches, however we need to check if it is repeating
if (checkRepeatedMatch(strsrch, start, *textoffset) ||
!isBreakUnit(strsrch, start, *textoffset) ||
!checkIdentical(strsrch, start, *textoffset)) {
(*textoffset) ++;
*textoffset = getNextBaseOffset(strsrch->search->text, *textoffset,
strsrch->search->textLength);
return FALSE;
}
strsrch->search->matchedIndex = start;
strsrch->search->matchedLength = *textoffset - start;
return TRUE;
}
/**
* Shifting the collation element iterator position forward to prepare for
* a preceding match. If the first character is a unsafe character, we'll only
* shift by 1 to capture contractions, normalization etc.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param text strsrch string search data
* @param textoffset start text position to do search
* @param ce the text ce which failed the match.
* @param patternceindex index of the ce within the pattern ce buffer which
* failed the match
* @return final offset
*/
static
inline int32_t reverseShift(UStringSearch *strsrch,
int32_t textoffset,
int32_t ce,
int32_t patternceindex)
{
if (strsrch->search->isOverlap) {
if (textoffset != strsrch->search->textLength) {
textoffset --;
}
else {
textoffset -= strsrch->pattern.defaultShiftSize;
}
}
else {
if (ce != UCOL_NULLORDER) {
int32_t shift = strsrch->pattern.backShift[hash(ce)];
// this is to adjust for characters in the middle of the substring
// for matching that failed.
int32_t adjust = patternceindex;
if (adjust > 1 && shift > adjust) {
shift -= adjust - 1;
}
textoffset -= shift;
}
else {
textoffset -= strsrch->pattern.defaultShiftSize;
}
}
textoffset = getPreviousUStringSearchBaseOffset(strsrch, textoffset);
return textoffset;
}
/**
* Checks match for contraction.
* If the match starts with a partial contraction we fail.
* Internal method, status 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
* @param end offset of potential match, to be modified if necessary
* @param status output error status if any
* @return TRUE if match passes the contraction test, FALSE otherwise
*/
static
UBool checkPreviousExactContractionMatch(UStringSearch *strsrch,
int32_t *start,
int32_t *end, UErrorCode *status)
{
UCollationElements *coleiter = strsrch->textIter;
int32_t textlength = strsrch->search->textLength;
int32_t temp = *end;
const UCollator *collator = strsrch->collator;
const UChar *text = strsrch->search->text;
// This part checks if either if the start of the match contains potential
// contraction. If so we'll have to iterate through them
// Since we used ucol_next while previously looking for the potential
// match, this guarantees that our end will not be a partial contraction,
// or a partial supplementary character.
if (*start < textlength && ucol_unsafeCP(text[*start], collator)) {
int32_t expansion = getExpansionSuffix(coleiter);
UBool expandflag = expansion > 0;
setColEIterOffset(coleiter, *end);
while (U_SUCCESS(*status) && expansion > 0) {
// getting rid of the redundant ce
// since forward 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 A ring A\u030A, we'll have to skip the
// last ce in the expansion buffer
ucol_previous(coleiter, status);
if (U_FAILURE(*status)) {
return FALSE;
}
if (ucol_getOffset(coleiter) != temp) {
*end = temp;
temp = ucol_getOffset(coleiter);
}
expansion --;
}
int32_t *patternce = strsrch->pattern.CE;
int32_t patterncelength = strsrch->pattern.CELength;
int32_t count = patterncelength;
while (count > 0) {
int32_t ce = getCE(strsrch, ucol_previous(coleiter, status));
// status checked below, note that if status is a failure
// ucol_previous returns UCOL_NULLORDER
if (ce == UCOL_IGNORABLE) {
continue;
}
if (expandflag && count == 0 &&
getColElemIterOffset(coleiter, FALSE) != temp) {
*end = temp;
temp = ucol_getOffset(coleiter);
}
if (U_FAILURE(*status) || ce != patternce[count - 1]) {
(*start) --;
*start = getPreviousBaseOffset(text, *start);
return FALSE;
}
count --;
}
}
return TRUE;
}
/**
* Checks and sets the match information if found.
* Checks
* <ul>
* <li> the current match does not repeat the last match
* <li> boundaries are correct
* <li> exact matches has no extra accents
* <li> identical matches
* <\ul>
* Otherwise the offset will be shifted to the preceding character.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param collator
* @param coleiter collation element iterator
* @param text string
* @param textoffset offset in the collation element text. the returned value
* will be the truncated start offset of the match or the new start
* search offset.
* @param status output error status if any
* @return TRUE if the match is valid, FALSE otherwise
*/
static
inline UBool checkPreviousExactMatch(UStringSearch *strsrch,
int32_t *textoffset,
UErrorCode *status)
{
// to ensure that the start and ends are not composite characters
int32_t end = ucol_getOffset(strsrch->textIter);
if (!checkPreviousExactContractionMatch(strsrch, textoffset, &end, status)
|| U_FAILURE(*status)) {
return FALSE;
}
// this totally matches, however we need to check if it is repeating
// the old match
if (checkRepeatedMatch(strsrch, *textoffset, end) ||
!isBreakUnit(strsrch, *textoffset, end) ||
hasAccentsBeforeMatch(strsrch, *textoffset, end) ||
!checkIdentical(strsrch, *textoffset, end) ||
hasAccentsAfterMatch(strsrch, *textoffset, end)) {
(*textoffset) --;
*textoffset = getPreviousBaseOffset(strsrch->search->text,
*textoffset);
return FALSE;
}
//Add breakiterator boundary check for primary strength search.
if (!strsrch->search->breakIter && strsrch->strength == UCOL_PRIMARY) {
checkBreakBoundary(strsrch, textoffset, &end);
}
strsrch->search->matchedIndex = *textoffset;
strsrch->search->matchedLength = end - *textoffset;
return TRUE;
}
/**
* Rearranges the end accents to try matching.
* Suffix accents in the text will be grouped according to their combining
* class and the groups will be mixed and matched to try find the perfect
* match with the pattern.
* So for instance looking for "\u0301" in "\u030A\u0301\u0325"
* step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
* "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
* "\u0301\u0325".
* step 2: check if any of the generated substrings matches the pattern.
* Internal method, status assumed to be success, user has to check status
* before calling this method.
* @param strsrch string search match
* @param start offset of the first base character
* @param end start of the last accent set
* @param status only error status if any
* @return USEARCH_DONE if a match is not found, otherwise return the ending
* offset of the match. Note this start includes all following accents.
*/
static
int32_t doPreviousCanonicalSuffixMatch(UStringSearch *strsrch,
int32_t start,
int32_t end,
UErrorCode *status)
{
const UChar *text = strsrch->search->text;
int32_t tempend = end;
UTF_BACK_1(text, 0, tempend);
if (!(getFCD(text, &tempend, strsrch->search->textLength) &
LAST_BYTE_MASK_)) {
// die... failed at a base character
return USEARCH_DONE;
}
end = getNextBaseOffset(text, end, strsrch->search->textLength);
if (U_SUCCESS(*status)) {
UChar accents[INITIAL_ARRAY_SIZE_];
int32_t offset = getPreviousBaseOffset(text, end);
// normalizing the offensive string
unorm_normalize(text + offset, end - offset, UNORM_NFD, 0, accents,
INITIAL_ARRAY_SIZE_, status);
int32_t accentsindex[INITIAL_ARRAY_SIZE_];
int32_t accentsize = getUnblockedAccentIndex(accents,
accentsindex);
int32_t count = (2 << (accentsize - 1)) - 1;
UChar buffer[INITIAL_ARRAY_SIZE_];
UCollationElements *coleiter = strsrch->utilIter;
while (U_SUCCESS(*status) && count > 0) {
UChar *rearrange = strsrch->canonicalSuffixAccents;
// copy the base characters
for (int k = 0; k < accentsindex[0]; k ++) {
*rearrange ++ = accents[k];
}
// forming all possible canonical rearrangement by dropping
// sets of accents
for (int i = 0; i <= accentsize - 1; i ++) {
int32_t mask = 1 << (accentsize - i - 1);
if (count & mask) {
for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
*rearrange ++ = accents[j];
}
}
}
*rearrange = 0;
int32_t matchsize = INITIAL_ARRAY_SIZE_;
UChar *match = addToUCharArray(buffer, &matchsize,
strsrch->canonicalPrefixAccents,
strsrch->search->text + start,
offset - start,
strsrch->canonicalSuffixAccents,
status);
// run the collator iterator through this match
// if status is a failure ucol_setText does nothing
ucol_setText(coleiter, match, matchsize, status);
if (U_SUCCESS(*status)) {
if (checkCollationMatch(strsrch, coleiter)) {
if (match != buffer) {
uprv_free(match);
}
return end;
}
}
count --;
}
}
return USEARCH_DONE;
}
/**
* Take the rearranged start accents and tries matching. If match failed at
* a seperate following set of accents (seperated from the rearranged on by
* at least a base character) then we rearrange the preceding accents and
* tries matching again.
* We allow skipping of the ends of the accent set if the ces do not match.
* However if the failure is found before the accent set, it fails.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param textoffset of the ends of the rearranged accent
* @param status output error status if any
* @return USEARCH_DONE if a match is not found, otherwise return the ending
* offset of the match. Note this start includes all following accents.
*/
static
int32_t doPreviousCanonicalPrefixMatch(UStringSearch *strsrch,
int32_t textoffset,
UErrorCode *status)
{
const UChar *text = strsrch->search->text;
const UCollator *collator = strsrch->collator;
int32_t safelength = 0;
UChar *safetext;
int32_t safetextlength;
UChar safebuffer[INITIAL_ARRAY_SIZE_];
int32_t safeoffset = textoffset;
if (textoffset &&
ucol_unsafeCP(strsrch->canonicalPrefixAccents[
u_strlen(strsrch->canonicalPrefixAccents) - 1
], collator)) {
safeoffset = getNextSafeOffset(collator, text, textoffset,
strsrch->search->textLength);
safelength = safeoffset - textoffset;
safetextlength = INITIAL_ARRAY_SIZE_;
safetext = addToUCharArray(safebuffer, &safetextlength,
strsrch->canonicalPrefixAccents,
text + textoffset, safelength,
NULL, status);
}
else {
safetextlength = u_strlen(strsrch->canonicalPrefixAccents);
safetext = strsrch->canonicalPrefixAccents;
}
UCollationElements *coleiter = strsrch->utilIter;
// if status is a failure, ucol_setText does nothing
ucol_setText(coleiter, safetext, safetextlength, status);
// status checked in loop below
int32_t *ce = strsrch->pattern.CE;
int32_t celength = strsrch->pattern.CELength;
int ceindex = 0;
UBool isSafe = TRUE; // safe zone indication flag for position
int32_t prefixlength = u_strlen(strsrch->canonicalPrefixAccents);
while (ceindex < celength) {
int32_t textce = ucol_next(coleiter, status);
if (U_FAILURE(*status)) {
if (isSafe) {
cleanUpSafeText(strsrch, safetext, safebuffer);
}
return USEARCH_DONE;
}
if (textce == UCOL_NULLORDER) {
// check if we have passed the safe buffer
if (coleiter == strsrch->textIter) {
cleanUpSafeText(strsrch, safetext, safebuffer);
return USEARCH_DONE;
}
cleanUpSafeText(strsrch, safetext, safebuffer);
safetext = safebuffer;
coleiter = strsrch->textIter;
setColEIterOffset(coleiter, safeoffset);
// status checked at the start of the loop
isSafe = FALSE;
continue;
}
textce = getCE(strsrch, textce);
if (textce != UCOL_IGNORABLE && textce != ce[ceindex]) {
// do the beginning stuff
int32_t failedoffset = ucol_getOffset(coleiter);
if (isSafe && failedoffset <= prefixlength) {
// alas... no hope. failed at rearranged accent set
cleanUpSafeText(strsrch, safetext, safebuffer);
return USEARCH_DONE;
}
else {
if (isSafe) {
failedoffset = safeoffset - failedoffset;
cleanUpSafeText(strsrch, safetext, safebuffer);
}
// try rearranging the end accents
int32_t result = doPreviousCanonicalSuffixMatch(strsrch,
textoffset, failedoffset, status);
if (result != USEARCH_DONE) {
// if status is a failure, ucol_setOffset does nothing
setColEIterOffset(strsrch->textIter, result);
}
if (U_FAILURE(*status)) {
return USEARCH_DONE;
}
return result;
}
}
if (textce == ce[ceindex]) {
ceindex ++;
}
}
// set offset here
if (isSafe) {
int32_t result = ucol_getOffset(coleiter);
// sets the text iterator here with the correct expansion and offset
int32_t leftoverces = getExpansionSuffix(coleiter);
cleanUpSafeText(strsrch, safetext, safebuffer);
if (result <= prefixlength) {
result = textoffset;
}
else {
result = textoffset + (safeoffset - result);
}
setColEIterOffset(strsrch->textIter, result);
setExpansionSuffix(strsrch->textIter, leftoverces);
return result;
}
return ucol_getOffset(coleiter);
}
/**
* Trying out the substring and sees if it can be a canonical match.
* This will try normalizing the starting accents and arranging them into
* canonical equivalents and check their corresponding ces with the pattern ce.
* Prefix accents in the text will be grouped according to their combining
* class and the groups will be mixed and matched to try find the perfect
* match with the pattern.
* So for instance looking for "\u0301" in "\u030A\u0301\u0325"
* step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
* "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
* "\u0301\u0325".
* step 2: check if any of the generated substrings matches the pattern.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param textoffset start offset in the collation element text that starts
* with the accents to be rearranged
* @param status output error status if any
* @return TRUE if the match is valid, FALSE otherwise
*/
static
UBool doPreviousCanonicalMatch(UStringSearch *strsrch,
int32_t textoffset,
UErrorCode *status)
{
const UChar *text = strsrch->search->text;
int32_t temp = textoffset;
int32_t textlength = strsrch->search->textLength;
if ((getFCD(text, &temp, textlength) >> SECOND_LAST_BYTE_SHIFT_) == 0) {
UCollationElements *coleiter = strsrch->textIter;
int32_t offset = ucol_getOffset(coleiter);
if (strsrch->pattern.hasSuffixAccents) {
offset = doPreviousCanonicalSuffixMatch(strsrch, textoffset,
offset, status);
if (U_SUCCESS(*status) && offset != USEARCH_DONE) {
setColEIterOffset(coleiter, offset);
return TRUE;
}
}
return FALSE;
}
if (!strsrch->pattern.hasPrefixAccents) {
return FALSE;
}
UChar accents[INITIAL_ARRAY_SIZE_];
// offset to the last base character in substring to search
int32_t baseoffset = getNextBaseOffset(text, textoffset, textlength);
// normalizing the offensive string
unorm_normalize(text + textoffset, baseoffset - textoffset, UNORM_NFD,
0, accents, INITIAL_ARRAY_SIZE_, status);
// status checked in loop
int32_t accentsindex[INITIAL_ARRAY_SIZE_];
int32_t size = getUnblockedAccentIndex(accents, accentsindex);
// 2 power n - 1 plus the full set of accents
int32_t count = (2 << (size - 1)) - 1;
while (U_SUCCESS(*status) && count > 0) {
UChar *rearrange = strsrch->canonicalPrefixAccents;
// copy the base characters
for (int k = 0; k < accentsindex[0]; k ++) {
*rearrange ++ = accents[k];
}
// forming all possible canonical rearrangement by dropping
// sets of accents
for (int i = 0; i <= size - 1; i ++) {
int32_t mask = 1 << (size - i - 1);
if (count & mask) {
for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
*rearrange ++ = accents[j];
}
}
}
*rearrange = 0;
int32_t offset = doPreviousCanonicalPrefixMatch(strsrch,
baseoffset, status);
if (offset != USEARCH_DONE) {
return TRUE; // match found
}
count --;
}
return FALSE;
}
/**
* Checks match for contraction.
* If the match starts with a partial contraction we fail.
* Internal method, status 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
* @param end offset of potential match, to be modified if necessary
* @param status only error status if any
* @return TRUE if match passes the contraction test, FALSE otherwise
*/
static
UBool checkPreviousCanonicalContractionMatch(UStringSearch *strsrch,
int32_t *start,
int32_t *end, UErrorCode *status)
{
UCollationElements *coleiter = strsrch->textIter;
int32_t textlength = strsrch->search->textLength;
int32_t temp = *end;
const UCollator *collator = strsrch->collator;
const UChar *text = strsrch->search->text;
// This part checks if either if the start of the match contains potential
// contraction. If so we'll have to iterate through them
// Since we used ucol_next while previously looking for the potential
// match, this guarantees that our end will not be a partial contraction,
// or a partial supplementary character.
if (*start < textlength && ucol_unsafeCP(text[*start], collator)) {
int32_t expansion = getExpansionSuffix(coleiter);
UBool expandflag = expansion > 0;
setColEIterOffset(coleiter, *end);
while (expansion > 0) {
// getting rid of the redundant ce
// since forward 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 A ring A\u030A, we'll have to skip the
// last ce in the expansion buffer
ucol_previous(coleiter, status);
if (U_FAILURE(*status)) {
return FALSE;
}
if (ucol_getOffset(coleiter) != temp) {
*end = temp;
temp = ucol_getOffset(coleiter);
}
expansion --;
}
int32_t *patternce = strsrch->pattern.CE;
int32_t patterncelength = strsrch->pattern.CELength;
int32_t count = patterncelength;
while (count > 0) {
int32_t ce = getCE(strsrch, ucol_previous(coleiter, status));
// status checked below, note that if status is a failure
// ucol_previous returns UCOL_NULLORDER
if (ce == UCOL_IGNORABLE) {
continue;
}
if (expandflag && count == 0 &&
getColElemIterOffset(coleiter, FALSE) != temp) {
*end = temp;
temp = ucol_getOffset(coleiter);
}
if (count == patterncelength &&
ce != patternce[patterncelength - 1]) {
// accents may have extra starting ces, this occurs when a
// pure accent pattern is matched without rearrangement
int32_t expected = patternce[patterncelength - 1];
UTF_BACK_1(text, 0, *end);
if (getFCD(text, end, textlength) & LAST_BYTE_MASK_) {
ce = getCE(strsrch, ucol_previous(coleiter, status));
while (U_SUCCESS(*status) && ce != expected &&
ce != UCOL_NULLORDER &&
ucol_getOffset(coleiter) <= *start) {
ce = getCE(strsrch, ucol_previous(coleiter, status));
}
}
}
if (U_FAILURE(*status) || ce != patternce[count - 1]) {
(*start) --;
*start = getPreviousBaseOffset(text, *start);
return FALSE;
}
count --;
}
}
return TRUE;
}
/**
* Checks and sets the match information if found.
* Checks
* <ul>
* <li> the potential match does not repeat the previous match
* <li> boundaries are correct
* <li> potential match does not end in the middle of a contraction
* <li> identical matches
* <\ul>
* Otherwise the offset will be shifted to the next character.
* Internal method, status assumed to be success, caller has to check status
* before calling this method.
* @param strsrch string search data
* @param textoffset offset in the collation element text. the returned value
* will be the truncated start offset of the match or the new start
* search offset.
* @param status only error status if any
* @return TRUE if the match is valid, FALSE otherwise
*/
static
inline UBool checkPreviousCanonicalMatch(UStringSearch *strsrch,
int32_t *textoffset,
UErrorCode *status)
{
// to ensure that the start and ends are not composite characters
UCollationElements *coleiter = strsrch->textIter;
// if we have a canonical accent match
if ((strsrch->pattern.hasSuffixAccents &&
strsrch->canonicalSuffixAccents[0]) ||
(strsrch->pattern.hasPrefixAccents &&
strsrch->canonicalPrefixAccents[0])) {
strsrch->search->matchedIndex = *textoffset;
strsrch->search->matchedLength =
getNextUStringSearchBaseOffset(strsrch,
getColElemIterOffset(coleiter, FALSE))
- *textoffset;
return TRUE;
}
int32_t end = ucol_getOffset(coleiter);
if (!checkPreviousCanonicalContractionMatch(strsrch, textoffset, &end,
status) ||
U_FAILURE(*status)) {
return FALSE;
}
end = getNextUStringSearchBaseOffset(strsrch, end);
// this totally matches, however we need to check if it is repeating
if (checkRepeatedMatch(strsrch, *textoffset, end) ||
!isBreakUnit(strsrch, *textoffset, end) ||
!checkIdentical(strsrch, *textoffset, end)) {
(*textoffset) --;
*textoffset = getPreviousBaseOffset(strsrch->search->text,
*textoffset);
return FALSE;
}
strsrch->search->matchedIndex = *textoffset;
strsrch->search->matchedLength = end - *textoffset;
return TRUE;
}
#endif // #if BOYER_MOORE
// constructors and destructor -------------------------------------------
U_CAPI UStringSearch * U_EXPORT2 usearch_open(const UChar *pattern,
int32_t patternlength,
const UChar *text,
int32_t textlength,
const char *locale,
UBreakIterator *breakiter,
UErrorCode *status)
{
if (U_FAILURE(*status)) {
return NULL;
}
#if UCONFIG_NO_BREAK_ITERATION
if (breakiter != NULL) {
*status = U_UNSUPPORTED_ERROR;
return NULL;
}
#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 == NULL || U_FAILURE(*status)) {
if (collator) {
ucol_close(collator);
}
return NULL;
}
else {
result->ownCollator = TRUE;
}
return result;
}
*status = U_ILLEGAL_ARGUMENT_ERROR;
return NULL;
}
U_CAPI UStringSearch * U_EXPORT2 usearch_openFromCollator(
const UChar *pattern,
int32_t patternlength,
const UChar *text,
int32_t textlength,
const UCollator *collator,
UBreakIterator *breakiter,
UErrorCode *status)
{
if (U_FAILURE(*status)) {
return NULL;
}
#if UCONFIG_NO_BREAK_ITERATION
if (breakiter != NULL) {
*status = U_UNSUPPORTED_ERROR;
return NULL;
}
#endif
if (pattern == NULL || text == NULL || collator == NULL) {
*status = U_ILLEGAL_ARGUMENT_ERROR;
return NULL;
}
// 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 NULL;
}
if (U_SUCCESS(*status)) {
initializeFCD(status);
if (U_FAILURE(*status)) {
return NULL;
}
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 NULL;
}
result = (UStringSearch *)uprv_malloc(sizeof(UStringSearch));
if (result == NULL) {
*status = U_MEMORY_ALLOCATION_ERROR;
return NULL;
}
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 = Normalizer2Factory::getNFDInstance(*status);
if (U_FAILURE(*status)) {
uprv_free(result);
return NULL;
}
result->search = (USearch *)uprv_malloc(sizeof(USearch));
if (result->search == NULL) {
*status = U_MEMORY_ALLOCATION_ERROR;
uprv_free(result);
return NULL;
}
result->search->text = text;
result->search->textLength = textlength;
result->pattern.text = pattern;
result->pattern.textLength = patternlength;