michael@0: /*
michael@0: **********************************************************************
michael@0: *   Copyright (C) 2001-2011 IBM and others. All rights reserved.
michael@0: **********************************************************************
michael@0: *   Date        Name        Description
michael@0: *  07/02/2001   synwee      Creation.
michael@0: **********************************************************************
michael@0: */
michael@0: 
michael@0: #include "unicode/utypes.h"
michael@0: 
michael@0: #if !UCONFIG_NO_COLLATION && !UCONFIG_NO_BREAK_ITERATION
michael@0: 
michael@0: #include "unicode/usearch.h"
michael@0: #include "unicode/ustring.h"
michael@0: #include "unicode/uchar.h"
michael@0: #include "unicode/utf16.h"
michael@0: #include "normalizer2impl.h"
michael@0: #include "ucol_imp.h"
michael@0: #include "usrchimp.h"
michael@0: #include "cmemory.h"
michael@0: #include "ucln_in.h"
michael@0: #include "uassert.h"
michael@0: #include "ustr_imp.h"
michael@0: 
michael@0: U_NAMESPACE_USE
michael@0: 
michael@0: // don't use Boyer-Moore
michael@0: // (and if we decide to turn this on again there are several new TODOs that will need to be addressed)
michael@0: #define BOYER_MOORE 0
michael@0: 
michael@0: #define LENGTHOF(array) (int32_t)(sizeof(array)/sizeof((array)[0]))
michael@0: 
michael@0: // internal definition ---------------------------------------------------
michael@0: 
michael@0: #define LAST_BYTE_MASK_          0xFF
michael@0: #define SECOND_LAST_BYTE_SHIFT_  8
michael@0: #define SUPPLEMENTARY_MIN_VALUE_ 0x10000
michael@0: 
michael@0: static const Normalizer2Impl *g_nfcImpl = NULL;
michael@0: 
michael@0: // internal methods -------------------------------------------------
michael@0: 
michael@0: /**
michael@0: * Fast collation element iterator setOffset.
michael@0: * This function does not check for bounds.
michael@0: * @param coleiter collation element iterator
michael@0: * @param offset to set
michael@0: */
michael@0: static
michael@0: inline void setColEIterOffset(UCollationElements *elems,
michael@0:                       int32_t             offset)
michael@0: {
michael@0:     collIterate *ci = &(elems->iteratordata_);
michael@0:     ci->pos         = ci->string + offset;
michael@0:     ci->CEpos       = ci->toReturn = ci->extendCEs ? ci->extendCEs : ci->CEs;
michael@0:     if (ci->flags & UCOL_ITER_INNORMBUF) {
michael@0:         ci->flags = ci->origFlags;
michael@0:     }
michael@0:     ci->fcdPosition = NULL;
michael@0: 
michael@0:     ci->offsetReturn = NULL;
michael@0:     ci->offsetStore  = ci->offsetBuffer;
michael@0:     ci->offsetRepeatCount = ci->offsetRepeatValue = 0;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Getting the mask for collation strength
michael@0: * @param strength collation strength
michael@0: * @return collation element mask
michael@0: */
michael@0: static
michael@0: inline uint32_t getMask(UCollationStrength strength)
michael@0: {
michael@0:     switch (strength)
michael@0:     {
michael@0:     case UCOL_PRIMARY:
michael@0:         return UCOL_PRIMARYORDERMASK;
michael@0:     case UCOL_SECONDARY:
michael@0:         return UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK;
michael@0:     default:
michael@0:         return UCOL_TERTIARYORDERMASK | UCOL_SECONDARYORDERMASK |
michael@0:                UCOL_PRIMARYORDERMASK;
michael@0:     }
michael@0: }
michael@0: 
michael@0: /**
michael@0: * This is to squeeze the 21bit ces into a 256 table
michael@0: * @param ce collation element
michael@0: * @return collapsed version of the collation element
michael@0: */
michael@0: static
michael@0: inline int hash(uint32_t ce)
michael@0: {
michael@0:     // the old value UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_ does not work
michael@0:     // well with the new collation where most of the latin 1 characters
michael@0:     // are of the value xx000xxx. their hashes will most of the time be 0
michael@0:     // to be discussed on the hash algo.
michael@0:     return UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_;
michael@0: }
michael@0: 
michael@0: U_CDECL_BEGIN
michael@0: static UBool U_CALLCONV
michael@0: usearch_cleanup(void) {
michael@0:     g_nfcImpl = NULL;
michael@0:     return TRUE;
michael@0: }
michael@0: U_CDECL_END
michael@0: 
michael@0: /**
michael@0: * Initializing the fcd tables.
michael@0: * Internal method, status assumed to be a success.
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: */
michael@0: static
michael@0: inline void initializeFCD(UErrorCode *status)
michael@0: {
michael@0:     if (g_nfcImpl == NULL) {
michael@0:         g_nfcImpl = Normalizer2Factory::getNFCImpl(*status);
michael@0:         ucln_i18n_registerCleanup(UCLN_I18N_USEARCH, usearch_cleanup);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Gets the fcd value for a character at the argument index.
michael@0: * This method takes into accounts of the supplementary characters.
michael@0: * @param str UTF16 string where character for fcd retrieval resides
michael@0: * @param offset position of the character whose fcd is to be retrieved, to be
michael@0: *               overwritten with the next character position, taking
michael@0: *               surrogate characters into consideration.
michael@0: * @param strlength length of the argument string
michael@0: * @return fcd value
michael@0: */
michael@0: static
michael@0: uint16_t getFCD(const UChar   *str, int32_t *offset,
michael@0:                              int32_t  strlength)
michael@0: {
michael@0:     const UChar *temp = str + *offset;
michael@0:     uint16_t    result = g_nfcImpl->nextFCD16(temp, str + strlength);
michael@0:     *offset = (int32_t)(temp - str);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Getting the modified collation elements taking into account the collation
michael@0: * attributes
michael@0: * @param strsrch string search data
michael@0: * @param sourcece
michael@0: * @return the modified collation element
michael@0: */
michael@0: static
michael@0: inline int32_t getCE(const UStringSearch *strsrch, uint32_t sourcece)
michael@0: {
michael@0:     // note for tertiary we can't use the collator->tertiaryMask, that
michael@0:     // is a preprocessed mask that takes into account case options. since
michael@0:     // we are only concerned with exact matches, we don't need that.
michael@0:     sourcece &= strsrch->ceMask;
michael@0: 
michael@0:     if (strsrch->toShift) {
michael@0:         // alternate handling here, since only the 16 most significant digits
michael@0:         // is only used, we can safely do a compare without masking
michael@0:         // if the ce is a variable, we mask and get only the primary values
michael@0:         // no shifting to quartenary is required since all primary values
michael@0:         // less than variabletop will need to be masked off anyway.
michael@0:         if (strsrch->variableTop > sourcece) {
michael@0:             if (strsrch->strength >= UCOL_QUATERNARY) {
michael@0:                 sourcece &= UCOL_PRIMARYORDERMASK;
michael@0:             }
michael@0:             else {
michael@0:                 sourcece = UCOL_IGNORABLE;
michael@0:             }
michael@0:         }
michael@0:     } else if (strsrch->strength >= UCOL_QUATERNARY && sourcece == UCOL_IGNORABLE) {
michael@0:         sourcece = 0xFFFF;
michael@0:     }
michael@0: 
michael@0:     return sourcece;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Allocate a memory and returns NULL if it failed.
michael@0: * Internal method, status assumed to be a success.
michael@0: * @param size to allocate
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: * @return newly allocated array, NULL otherwise
michael@0: */
michael@0: static
michael@0: inline void * allocateMemory(uint32_t size, UErrorCode *status)
michael@0: {
michael@0:     uint32_t *result = (uint32_t *)uprv_malloc(size);
michael@0:     if (result == NULL) {
michael@0:         *status = U_MEMORY_ALLOCATION_ERROR;
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Adds a uint32_t value to a destination array.
michael@0: * Creates a new array if we run out of space. The caller will have to
michael@0: * manually deallocate the newly allocated array.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method. destination not to be NULL and has at least
michael@0: * size destinationlength.
michael@0: * @param destination target array
michael@0: * @param offset destination offset to add value
michael@0: * @param destinationlength target array size, return value for the new size
michael@0: * @param value to be added
michael@0: * @param increments incremental size expected
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: * @return new destination array, destination if there was no new allocation
michael@0: */
michael@0: static
michael@0: inline int32_t * addTouint32_tArray(int32_t    *destination,
michael@0:                                     uint32_t    offset,
michael@0:                                     uint32_t   *destinationlength,
michael@0:                                     uint32_t    value,
michael@0:                                     uint32_t    increments,
michael@0:                                     UErrorCode *status)
michael@0: {
michael@0:     uint32_t newlength = *destinationlength;
michael@0:     if (offset + 1 == newlength) {
michael@0:         newlength += increments;
michael@0:         int32_t *temp = (int32_t *)allocateMemory(
michael@0:                                          sizeof(int32_t) * newlength, status);
michael@0:         if (U_FAILURE(*status)) {
michael@0:             return NULL;
michael@0:         }
michael@0:         uprv_memcpy(temp, destination, sizeof(int32_t) * offset);
michael@0:         *destinationlength = newlength;
michael@0:         destination        = temp;
michael@0:     }
michael@0:     destination[offset] = value;
michael@0:     return destination;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Adds a uint64_t value to a destination array.
michael@0: * Creates a new array if we run out of space. The caller will have to
michael@0: * manually deallocate the newly allocated array.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method. destination not to be NULL and has at least
michael@0: * size destinationlength.
michael@0: * @param destination target array
michael@0: * @param offset destination offset to add value
michael@0: * @param destinationlength target array size, return value for the new size
michael@0: * @param value to be added
michael@0: * @param increments incremental size expected
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: * @return new destination array, destination if there was no new allocation
michael@0: */
michael@0: static
michael@0: inline int64_t * addTouint64_tArray(int64_t    *destination,
michael@0:                                     uint32_t    offset,
michael@0:                                     uint32_t   *destinationlength,
michael@0:                                     uint64_t    value,
michael@0:                                     uint32_t    increments,
michael@0:                                     UErrorCode *status)
michael@0: {
michael@0:     uint32_t newlength = *destinationlength;
michael@0:     if (offset + 1 == newlength) {
michael@0:         newlength += increments;
michael@0:         int64_t *temp = (int64_t *)allocateMemory(
michael@0:                                          sizeof(int64_t) * newlength, status);
michael@0: 
michael@0:         if (U_FAILURE(*status)) {
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         uprv_memcpy(temp, destination, sizeof(int64_t) * offset);
michael@0:         *destinationlength = newlength;
michael@0:         destination        = temp;
michael@0:     }
michael@0: 
michael@0:     destination[offset] = value;
michael@0: 
michael@0:     return destination;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Initializing the ce table for a pattern.
michael@0: * Stores non-ignorable collation keys.
michael@0: * Table size will be estimated by the size of the pattern text. Table
michael@0: * expansion will be perform as we go along. Adding 1 to ensure that the table
michael@0: * size definitely increases.
michael@0: * Internal method, status assumed to be a success.
michael@0: * @param strsrch string search data
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: * @return total number of expansions
michael@0: */
michael@0: static
michael@0: inline uint16_t initializePatternCETable(UStringSearch *strsrch,
michael@0:                                          UErrorCode    *status)
michael@0: {
michael@0:     UPattern *pattern            = &(strsrch->pattern);
michael@0:     uint32_t  cetablesize        = INITIAL_ARRAY_SIZE_;
michael@0:     int32_t  *cetable            = pattern->CEBuffer;
michael@0:     uint32_t  patternlength      = pattern->textLength;
michael@0:     UCollationElements *coleiter = strsrch->utilIter;
michael@0: 
michael@0:     if (coleiter == NULL) {
michael@0:         coleiter = ucol_openElements(strsrch->collator, pattern->text,
michael@0:                                      patternlength, status);
michael@0:         // status will be checked in ucol_next(..) later and if it is an
michael@0:         // error UCOL_NULLORDER the result of ucol_next(..) and 0 will be
michael@0:         // returned.
michael@0:         strsrch->utilIter = coleiter;
michael@0:     }
michael@0:     else {
michael@0:         uprv_init_collIterate(strsrch->collator, pattern->text,
michael@0:                          pattern->textLength,
michael@0:                          &coleiter->iteratordata_,
michael@0:                          status);
michael@0:     }
michael@0:     if(U_FAILURE(*status)) {
michael@0:         return 0;
michael@0:     }
michael@0: 
michael@0:     if (pattern->CE != cetable && pattern->CE) {
michael@0:         uprv_free(pattern->CE);
michael@0:     }
michael@0: 
michael@0:     uint16_t  offset      = 0;
michael@0:     uint16_t  result      = 0;
michael@0:     int32_t   ce;
michael@0: 
michael@0:     while ((ce = ucol_next(coleiter, status)) != UCOL_NULLORDER &&
michael@0:            U_SUCCESS(*status)) {
michael@0:         uint32_t newce = getCE(strsrch, ce);
michael@0:         if (newce) {
michael@0:             int32_t *temp = addTouint32_tArray(cetable, offset, &cetablesize,
michael@0:                                   newce,
michael@0:                                   patternlength - ucol_getOffset(coleiter) + 1,
michael@0:                                   status);
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return 0;
michael@0:             }
michael@0:             offset ++;
michael@0:             if (cetable != temp && cetable != pattern->CEBuffer) {
michael@0:                 uprv_free(cetable);
michael@0:             }
michael@0:             cetable = temp;
michael@0:         }
michael@0:         result += (uint16_t)(ucol_getMaxExpansion(coleiter, ce) - 1);
michael@0:     }
michael@0: 
michael@0:     cetable[offset]   = 0;
michael@0:     pattern->CE       = cetable;
michael@0:     pattern->CELength = offset;
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Initializing the pce table for a pattern.
michael@0: * Stores non-ignorable collation keys.
michael@0: * Table size will be estimated by the size of the pattern text. Table
michael@0: * expansion will be perform as we go along. Adding 1 to ensure that the table
michael@0: * size definitely increases.
michael@0: * Internal method, status assumed to be a success.
michael@0: * @param strsrch string search data
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: * @return total number of expansions
michael@0: */
michael@0: static
michael@0: inline uint16_t initializePatternPCETable(UStringSearch *strsrch,
michael@0:                                           UErrorCode    *status)
michael@0: {
michael@0:     UPattern *pattern            = &(strsrch->pattern);
michael@0:     uint32_t  pcetablesize       = INITIAL_ARRAY_SIZE_;
michael@0:     int64_t  *pcetable           = pattern->PCEBuffer;
michael@0:     uint32_t  patternlength      = pattern->textLength;
michael@0:     UCollationElements *coleiter = strsrch->utilIter;
michael@0: 
michael@0:     if (coleiter == NULL) {
michael@0:         coleiter = ucol_openElements(strsrch->collator, pattern->text,
michael@0:                                      patternlength, status);
michael@0:         // status will be checked in ucol_next(..) later and if it is an
michael@0:         // error UCOL_NULLORDER the result of ucol_next(..) and 0 will be
michael@0:         // returned.
michael@0:         strsrch->utilIter = coleiter;
michael@0:     } else {
michael@0:         uprv_init_collIterate(strsrch->collator, pattern->text,
michael@0:                               pattern->textLength,
michael@0:                               &coleiter->iteratordata_,
michael@0:                               status);
michael@0:     }
michael@0:     if(U_FAILURE(*status)) {
michael@0:         return 0;
michael@0:     }
michael@0: 
michael@0:     if (pattern->PCE != pcetable && pattern->PCE != NULL) {
michael@0:         uprv_free(pattern->PCE);
michael@0:     }
michael@0: 
michael@0:     uint16_t  offset = 0;
michael@0:     uint16_t  result = 0;
michael@0:     int64_t   pce;
michael@0: 
michael@0:     uprv_init_pce(coleiter);
michael@0: 
michael@0:     // ** Should processed CEs be signed or unsigned?
michael@0:     // ** (the rest of the code in this file seems to play fast-and-loose with
michael@0:     // **  whether a CE is signed or unsigned. For example, look at routine above this one.)
michael@0:     while ((pce = ucol_nextProcessed(coleiter, NULL, NULL, status)) != UCOL_PROCESSED_NULLORDER &&
michael@0:            U_SUCCESS(*status)) {
michael@0:         int64_t *temp = addTouint64_tArray(pcetable, offset, &pcetablesize,
michael@0:                               pce,
michael@0:                               patternlength - ucol_getOffset(coleiter) + 1,
michael@0:                               status);
michael@0: 
michael@0:         if (U_FAILURE(*status)) {
michael@0:             return 0;
michael@0:         }
michael@0: 
michael@0:         offset += 1;
michael@0: 
michael@0:         if (pcetable != temp && pcetable != pattern->PCEBuffer) {
michael@0:             uprv_free(pcetable);
michael@0:         }
michael@0: 
michael@0:         pcetable = temp;
michael@0:         //result += (uint16_t)(ucol_getMaxExpansion(coleiter, ce) - 1);
michael@0:     }
michael@0: 
michael@0:     pcetable[offset]   = 0;
michael@0:     pattern->PCE       = pcetable;
michael@0:     pattern->PCELength = offset;
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Initializes the pattern struct.
michael@0: * Internal method, status assumed to be success.
michael@0: * @param strsrch UStringSearch data storage
michael@0: * @param status output error if any, caller to check status before calling
michael@0: *               method, status assumed to be success when passed in.
michael@0: * @return expansionsize the total expansion size of the pattern
michael@0: */
michael@0: static
michael@0: inline int16_t initializePattern(UStringSearch *strsrch, UErrorCode *status)
michael@0: {
michael@0:           UPattern   *pattern     = &(strsrch->pattern);
michael@0:     const UChar      *patterntext = pattern->text;
michael@0:           int32_t     length      = pattern->textLength;
michael@0:           int32_t index       = 0;
michael@0: 
michael@0:     // Since the strength is primary, accents are ignored in the pattern.
michael@0:     if (strsrch->strength == UCOL_PRIMARY) {
michael@0:         pattern->hasPrefixAccents = 0;
michael@0:         pattern->hasSuffixAccents = 0;
michael@0:     } else {
michael@0:         pattern->hasPrefixAccents = getFCD(patterntext, &index, length) >>
michael@0:                                                          SECOND_LAST_BYTE_SHIFT_;
michael@0:         index = length;
michael@0:         U16_BACK_1(patterntext, 0, index);
michael@0:         pattern->hasSuffixAccents = getFCD(patterntext, &index, length) &
michael@0:                                                                  LAST_BYTE_MASK_;
michael@0:     }
michael@0: 
michael@0:     // ** HACK **
michael@0:     if (strsrch->pattern.PCE != NULL) {
michael@0:         if (strsrch->pattern.PCE != strsrch->pattern.PCEBuffer) {
michael@0:             uprv_free(strsrch->pattern.PCE);
michael@0:         }
michael@0: 
michael@0:         strsrch->pattern.PCE = NULL;
michael@0:     }
michael@0: 
michael@0:     // since intializePattern is an internal method status is a success.
michael@0:     return initializePatternCETable(strsrch, status);
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Initializing shift tables, with the default values.
michael@0: * If a corresponding default value is 0, the shift table is not set.
michael@0: * @param shift table for forwards shift
michael@0: * @param backshift table for backwards shift
michael@0: * @param cetable table containing pattern ce
michael@0: * @param cesize size of the pattern ces
michael@0: * @param expansionsize total size of the expansions
michael@0: * @param defaultforward the default forward value
michael@0: * @param defaultbackward the default backward value
michael@0: */
michael@0: static
michael@0: inline void setShiftTable(int16_t   shift[], int16_t backshift[],
michael@0:                           int32_t  *cetable, int32_t cesize,
michael@0:                           int16_t   expansionsize,
michael@0:                           int16_t   defaultforward,
michael@0:                           int16_t   defaultbackward)
michael@0: {
michael@0:     // estimate the value to shift. to do that we estimate the smallest
michael@0:     // number of characters to give the relevant ces, ie approximately
michael@0:     // the number of ces minus their expansion, since expansions can come
michael@0:     // from a character.
michael@0:     int32_t count;
michael@0:     for (count = 0; count < MAX_TABLE_SIZE_; count ++) {
michael@0:         shift[count] = defaultforward;
michael@0:     }
michael@0:     cesize --; // down to the last index
michael@0:     for (count = 0; count < cesize; count ++) {
michael@0:         // number of ces from right of array to the count
michael@0:         int temp = defaultforward - count - 1;
michael@0:         shift[hash(cetable[count])] = temp > 1 ? temp : 1;
michael@0:     }
michael@0:     shift[hash(cetable[cesize])] = 1;
michael@0:     // for ignorables we just shift by one. see test examples.
michael@0:     shift[hash(0)] = 1;
michael@0: 
michael@0:     for (count = 0; count < MAX_TABLE_SIZE_; count ++) {
michael@0:         backshift[count] = defaultbackward;
michael@0:     }
michael@0:     for (count = cesize; count > 0; count --) {
michael@0:         // the original value count does not seem to work
michael@0:         backshift[hash(cetable[count])] = count > expansionsize ?
michael@0:                                           (int16_t)(count - expansionsize) : 1;
michael@0:     }
michael@0:     backshift[hash(cetable[0])] = 1;
michael@0:     backshift[hash(0)] = 1;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Building of the pattern collation element list and the boyer moore strsrch
michael@0: * table.
michael@0: * The canonical match will only be performed after the default match fails.
michael@0: * For both cases we need to remember the size of the composed and decomposed
michael@0: * versions of the string. Since the Boyer-Moore shift calculations shifts by
michael@0: * a number of characters in the text and tries to match the pattern from that
michael@0: * offset, the shift value can not be too large in case we miss some
michael@0: * characters. To choose a right shift size, we estimate the NFC form of the
michael@0: * and use its size as a shift guide. The NFC form should be the small
michael@0: * possible representation of the pattern. Anyways, we'll err on the smaller
michael@0: * shift size. Hence the calculation for minlength.
michael@0: * Canonical match will be performed slightly differently. We'll split the
michael@0: * pattern into 3 parts, the prefix accents (PA), the middle string bounded by
michael@0: * the first and last base character (MS), the ending accents (EA). Matches
michael@0: * will be done on MS first, and only when we match MS then some processing
michael@0: * will be required for the prefix and end accents in order to determine if
michael@0: * they match PA and EA. Hence the default shift values
michael@0: * for the canonical match will take the size of either end's accent into
michael@0: * consideration. Forwards search will take the end accents into consideration
michael@0: * for the default shift values and the backwards search will take the prefix
michael@0: * accents into consideration.
michael@0: * If pattern has no non-ignorable ce, we return a illegal argument error.
michael@0: * Internal method, status assumed to be success.
michael@0: * @param strsrch UStringSearch data storage
michael@0: * @param status  for output errors if it occurs, status is assumed to be a
michael@0: *                success when it is passed in.
michael@0: */
michael@0: static
michael@0: inline void initialize(UStringSearch *strsrch, UErrorCode *status)
michael@0: {
michael@0:     int16_t expandlength  = initializePattern(strsrch, status);
michael@0:     if (U_SUCCESS(*status) && strsrch->pattern.CELength > 0) {
michael@0:         UPattern *pattern = &strsrch->pattern;
michael@0:         int32_t   cesize  = pattern->CELength;
michael@0: 
michael@0:         int16_t minlength = cesize > expandlength
michael@0:                             ? (int16_t)cesize - expandlength : 1;
michael@0:         pattern->defaultShiftSize    = minlength;
michael@0:         setShiftTable(pattern->shift, pattern->backShift, pattern->CE,
michael@0:                       cesize, expandlength, minlength, minlength);
michael@0:         return;
michael@0:     }
michael@0:     strsrch->pattern.defaultShiftSize = 0;
michael@0: }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0: /**
michael@0: * Check to make sure that the match length is at the end of the character by
michael@0: * using the breakiterator.
michael@0: * @param strsrch string search data
michael@0: * @param start target text start offset
michael@0: * @param end target text end offset
michael@0: */
michael@0: static
michael@0: void checkBreakBoundary(const UStringSearch *strsrch, int32_t * /*start*/,
michael@0:                                int32_t *end)
michael@0: {
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:     UBreakIterator *breakiterator = strsrch->search->internalBreakIter;
michael@0:     if (breakiterator) {
michael@0:         int32_t matchend = *end;
michael@0:         //int32_t matchstart = *start;
michael@0: 
michael@0:         if (!ubrk_isBoundary(breakiterator, matchend)) {
michael@0:             *end = ubrk_following(breakiterator, matchend);
michael@0:         }
michael@0: 
michael@0:         /* Check the start of the matched text to make sure it doesn't have any accents
michael@0:          * before it.  This code may not be necessary and so it is commented out */
michael@0:         /*if (!ubrk_isBoundary(breakiterator, matchstart) && !ubrk_isBoundary(breakiterator, matchstart-1)) {
michael@0:             *start = ubrk_preceding(breakiterator, matchstart);
michael@0:         }*/
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Determine whether the target text in UStringSearch bounded by the offset
michael@0: * start and end is one or more whole units of text as
michael@0: * determined by the breakiterator in UStringSearch.
michael@0: * @param strsrch string search data
michael@0: * @param start target text start offset
michael@0: * @param end target text end offset
michael@0: */
michael@0: static
michael@0: UBool isBreakUnit(const UStringSearch *strsrch, int32_t start,
michael@0:                                int32_t    end)
michael@0: {
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:     UBreakIterator *breakiterator = strsrch->search->breakIter;
michael@0:     //TODO: Add here.
michael@0:     if (breakiterator) {
michael@0:         int32_t startindex = ubrk_first(breakiterator);
michael@0:         int32_t endindex   = ubrk_last(breakiterator);
michael@0: 
michael@0:         // out-of-range indexes are never boundary positions
michael@0:         if (start < startindex || start > endindex ||
michael@0:             end < startindex || end > endindex) {
michael@0:             return FALSE;
michael@0:         }
michael@0:         // otherwise, we can use following() on the position before the
michael@0:         // specified one and return true of the position we get back is the
michael@0:         // one the user specified
michael@0:         UBool result = (start == startindex ||
michael@0:                 ubrk_following(breakiterator, start - 1) == start) &&
michael@0:                (end == endindex ||
michael@0:                 ubrk_following(breakiterator, end - 1) == end);
michael@0:         if (result) {
michael@0:             // iterates the individual ces
michael@0:                   UCollationElements *coleiter  = strsrch->utilIter;
michael@0:             const UChar              *text      = strsrch->search->text +
michael@0:                                                                       start;
michael@0:                   UErrorCode          status    = U_ZERO_ERROR;
michael@0:             ucol_setText(coleiter, text, end - start, &status);
michael@0:             for (int32_t count = 0; count < strsrch->pattern.CELength;
michael@0:                  count ++) {
michael@0:                 int32_t ce = getCE(strsrch, ucol_next(coleiter, &status));
michael@0:                 if (ce == UCOL_IGNORABLE) {
michael@0:                     count --;
michael@0:                     continue;
michael@0:                 }
michael@0:                 if (U_FAILURE(status) || ce != strsrch->pattern.CE[count]) {
michael@0:                     return FALSE;
michael@0:                 }
michael@0:             }
michael@0:             int32_t nextce = ucol_next(coleiter, &status);
michael@0:             while (ucol_getOffset(coleiter) == (end - start)
michael@0:                    && getCE(strsrch, nextce) == UCOL_IGNORABLE) {
michael@0:                 nextce = ucol_next(coleiter, &status);
michael@0:             }
michael@0:             if (ucol_getOffset(coleiter) == (end - start)
michael@0:                 && nextce != UCOL_NULLORDER) {
michael@0:                 // extra collation elements at the end of the match
michael@0:                 return FALSE;
michael@0:             }
michael@0:         }
michael@0:         return result;
michael@0:     }
michael@0: #endif
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Getting the next base character offset if current offset is an accent,
michael@0: * or the current offset if the current character contains a base character.
michael@0: * accents the following base character will be returned
michael@0: * @param text string
michael@0: * @param textoffset current offset
michael@0: * @param textlength length of text string
michael@0: * @return the next base character or the current offset
michael@0: *         if the current character is contains a base character.
michael@0: */
michael@0: static
michael@0: inline int32_t getNextBaseOffset(const UChar       *text,
michael@0:                                            int32_t  textoffset,
michael@0:                                            int32_t      textlength)
michael@0: {
michael@0:     if (textoffset < textlength) {
michael@0:         int32_t temp = textoffset;
michael@0:         if (getFCD(text, &temp, textlength) >> SECOND_LAST_BYTE_SHIFT_) {
michael@0:             while (temp < textlength) {
michael@0:                 int32_t result = temp;
michael@0:                 if ((getFCD(text, &temp, textlength) >>
michael@0:                      SECOND_LAST_BYTE_SHIFT_) == 0) {
michael@0:                     return result;
michael@0:                 }
michael@0:             }
michael@0:             return textlength;
michael@0:         }
michael@0:     }
michael@0:     return textoffset;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Gets the next base character offset depending on the string search pattern
michael@0: * data
michael@0: * @param strsrch string search data
michael@0: * @param textoffset current offset, one offset away from the last character
michael@0: *                   to search for.
michael@0: * @return start index of the next base character or the current offset
michael@0: *         if the current character is contains a base character.
michael@0: */
michael@0: static
michael@0: inline int32_t getNextUStringSearchBaseOffset(UStringSearch *strsrch,
michael@0:                                                   int32_t    textoffset)
michael@0: {
michael@0:     int32_t textlength = strsrch->search->textLength;
michael@0:     if (strsrch->pattern.hasSuffixAccents &&
michael@0:         textoffset < textlength) {
michael@0:               int32_t  temp       = textoffset;
michael@0:         const UChar       *text       = strsrch->search->text;
michael@0:         U16_BACK_1(text, 0, temp);
michael@0:         if (getFCD(text, &temp, textlength) & LAST_BYTE_MASK_) {
michael@0:             return getNextBaseOffset(text, textoffset, textlength);
michael@0:         }
michael@0:     }
michael@0:     return textoffset;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Shifting the collation element iterator position forward to prepare for
michael@0: * a following match. If the last character is a unsafe character, we'll only
michael@0: * shift by 1 to capture contractions, normalization etc.
michael@0: * Internal method, status assumed to be success.
michael@0: * @param text strsrch string search data
michael@0: * @param textoffset start text position to do search
michael@0: * @param ce the text ce which failed the match.
michael@0: * @param patternceindex index of the ce within the pattern ce buffer which
michael@0: *        failed the match
michael@0: * @return final offset
michael@0: */
michael@0: static
michael@0: inline int32_t shiftForward(UStringSearch *strsrch,
michael@0:                                 int32_t    textoffset,
michael@0:                                 int32_t       ce,
michael@0:                                 int32_t        patternceindex)
michael@0: {
michael@0:     UPattern *pattern = &(strsrch->pattern);
michael@0:     if (ce != UCOL_NULLORDER) {
michael@0:         int32_t shift = pattern->shift[hash(ce)];
michael@0:         // this is to adjust for characters in the middle of the
michael@0:         // substring for matching that failed.
michael@0:         int32_t adjust = pattern->CELength - patternceindex;
michael@0:         if (adjust > 1 && shift >= adjust) {
michael@0:             shift -= adjust - 1;
michael@0:         }
michael@0:         textoffset += shift;
michael@0:     }
michael@0:     else {
michael@0:         textoffset += pattern->defaultShiftSize;
michael@0:     }
michael@0: 
michael@0:     textoffset = getNextUStringSearchBaseOffset(strsrch, textoffset);
michael@0:     // check for unsafe characters
michael@0:     // * if it is the start or middle of a contraction: to be done after
michael@0:     //   a initial match is found
michael@0:     // * thai or lao base consonant character: similar to contraction
michael@0:     // * high surrogate character: similar to contraction
michael@0:     // * next character is a accent: shift to the next base character
michael@0:     return textoffset;
michael@0: }
michael@0: #endif // #if BOYER_MOORE
michael@0: 
michael@0: /**
michael@0: * sets match not found
michael@0: * @param strsrch string search data
michael@0: */
michael@0: static
michael@0: inline void setMatchNotFound(UStringSearch *strsrch)
michael@0: {
michael@0:     // this method resets the match result regardless of the error status.
michael@0:     strsrch->search->matchedIndex = USEARCH_DONE;
michael@0:     strsrch->search->matchedLength = 0;
michael@0:     if (strsrch->search->isForwardSearching) {
michael@0:         setColEIterOffset(strsrch->textIter, strsrch->search->textLength);
michael@0:     }
michael@0:     else {
michael@0:         setColEIterOffset(strsrch->textIter, 0);
michael@0:     }
michael@0: }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0: /**
michael@0: * Gets the offset to the next safe point in text.
michael@0: * ie. not the middle of a contraction, swappable characters or supplementary
michael@0: * characters.
michael@0: * @param collator collation sata
michael@0: * @param text string to work with
michael@0: * @param textoffset offset in string
michael@0: * @param textlength length of text string
michael@0: * @return offset to the next safe character
michael@0: */
michael@0: static
michael@0: inline int32_t getNextSafeOffset(const UCollator   *collator,
michael@0:                                      const UChar       *text,
michael@0:                                            int32_t  textoffset,
michael@0:                                            int32_t      textlength)
michael@0: {
michael@0:     int32_t result = textoffset; // first contraction character
michael@0:     while (result != textlength && ucol_unsafeCP(text[result], collator)) {
michael@0:         result ++;
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * This checks for accents in the potential match started with a .
michael@0: * composite character.
michael@0: * This is really painful... we have to check that composite character do not
michael@0: * have any extra accents. We have to normalize the potential match and find
michael@0: * the immediate decomposed character before the match.
michael@0: * The first composite character would have been taken care of by the fcd
michael@0: * checks in checkForwardExactMatch.
michael@0: * This is the slow path after the fcd of the first character and
michael@0: * the last character has been checked by checkForwardExactMatch and we
michael@0: * determine that the potential match has extra non-ignorable preceding
michael@0: * ces.
michael@0: * E.g. looking for \u0301 acute in \u01FA A ring above and acute,
michael@0: * checkExtraMatchAccent should fail since there is a middle ring in \u01FA
michael@0: * Note here that accents checking are slow and cautioned in the API docs.
michael@0: * Internal method, status assumed to be a success, caller should check status
michael@0: * before calling this method
michael@0: * @param strsrch string search data
michael@0: * @param start index of the potential unfriendly composite character
michael@0: * @param end index of the potential unfriendly composite character
michael@0: * @param status output error status if any.
michael@0: * @return TRUE if there is non-ignorable accents before at the beginning
michael@0: *              of the match, FALSE otherwise.
michael@0: */
michael@0: 
michael@0: static
michael@0: UBool checkExtraMatchAccents(const UStringSearch *strsrch, int32_t start,
michael@0:                                    int32_t    end,
michael@0:                                    UErrorCode    *status)
michael@0: {
michael@0:     UBool result = FALSE;
michael@0:     if (strsrch->pattern.hasPrefixAccents) {
michael@0:               int32_t  length = end - start;
michael@0:               int32_t  offset = 0;
michael@0:         const UChar       *text   = strsrch->search->text + start;
michael@0: 
michael@0:         U16_FWD_1(text, offset, length);
michael@0:         // we are only concerned with the first composite character
michael@0:         if (unorm_quickCheck(text, offset, UNORM_NFD, status) == UNORM_NO) {
michael@0:             int32_t safeoffset = getNextSafeOffset(strsrch->collator,
michael@0:                                                        text, 0, length);
michael@0:             if (safeoffset != length) {
michael@0:                 safeoffset ++;
michael@0:             }
michael@0:             UChar   *norm = NULL;
michael@0:             UChar    buffer[INITIAL_ARRAY_SIZE_];
michael@0:             int32_t  size = unorm_normalize(text, safeoffset, UNORM_NFD, 0,
michael@0:                                             buffer, INITIAL_ARRAY_SIZE_,
michael@0:                                             status);
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return FALSE;
michael@0:             }
michael@0:             if (size >= INITIAL_ARRAY_SIZE_) {
michael@0:                 norm = (UChar *)allocateMemory((size + 1) * sizeof(UChar),
michael@0:                                                status);
michael@0:                 // if allocation failed, status will be set to
michael@0:                 // U_MEMORY_ALLOCATION_ERROR and unorm_normalize internally
michael@0:                 // checks for it.
michael@0:                 size = unorm_normalize(text, safeoffset, UNORM_NFD, 0, norm,
michael@0:                                        size, status);
michael@0:                 if (U_FAILURE(*status) && norm != NULL) {
michael@0:                     uprv_free(norm);
michael@0:                     return FALSE;
michael@0:                 }
michael@0:             }
michael@0:             else {
michael@0:                 norm = buffer;
michael@0:             }
michael@0: 
michael@0:             UCollationElements *coleiter  = strsrch->utilIter;
michael@0:             ucol_setText(coleiter, norm, size, status);
michael@0:             uint32_t            firstce   = strsrch->pattern.CE[0];
michael@0:             UBool               ignorable = TRUE;
michael@0:             uint32_t            ce        = UCOL_IGNORABLE;
michael@0:             while (U_SUCCESS(*status) && ce != firstce && ce != (uint32_t)UCOL_NULLORDER) {
michael@0:                 offset = ucol_getOffset(coleiter);
michael@0:                 if (ce != firstce && ce != UCOL_IGNORABLE) {
michael@0:                     ignorable = FALSE;
michael@0:                 }
michael@0:                 ce = ucol_next(coleiter, status);
michael@0:             }
michael@0:             UChar32 codepoint;
michael@0:             U16_PREV(norm, 0, offset, codepoint);
michael@0:             result = !ignorable && (u_getCombiningClass(codepoint) != 0);
michael@0: 
michael@0:             if (norm != buffer) {
michael@0:                 uprv_free(norm);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Used by exact matches, checks if there are accents before the match.
michael@0: * This is really painful... we have to check that composite characters at
michael@0: * the start of the matches have to not have any extra accents.
michael@0: * We check the FCD of the character first, if it starts with an accent and
michael@0: * the first pattern ce does not match the first ce of the character, we bail.
michael@0: * Otherwise we try normalizing the first composite
michael@0: * character and find the immediate decomposed character before the match to
michael@0: * see if it is an non-ignorable accent.
michael@0: * Now normalizing the first composite character is enough because we ensure
michael@0: * that when the match is passed in here with extra beginning ces, the
michael@0: * first or last ce that match has to occur within the first character.
michael@0: * E.g. looking for \u0301 acute in \u01FA A ring above and acute,
michael@0: * checkExtraMatchAccent should fail since there is a middle ring in \u01FA
michael@0: * Note here that accents checking are slow and cautioned in the API docs.
michael@0: * @param strsrch string search data
michael@0: * @param start offset
michael@0: * @param end offset
michael@0: * @return TRUE if there are accents on either side of the match,
michael@0: *         FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool hasAccentsBeforeMatch(const UStringSearch *strsrch, int32_t start,
michael@0:                                   int32_t    end)
michael@0: {
michael@0:     if (strsrch->pattern.hasPrefixAccents) {
michael@0:         UCollationElements *coleiter  = strsrch->textIter;
michael@0:         UErrorCode          status    = U_ZERO_ERROR;
michael@0:         // we have been iterating forwards previously
michael@0:         uint32_t            ignorable = TRUE;
michael@0:         int32_t             firstce   = strsrch->pattern.CE[0];
michael@0: 
michael@0:         setColEIterOffset(coleiter, start);
michael@0:         int32_t ce  = getCE(strsrch, ucol_next(coleiter, &status));
michael@0:         if (U_FAILURE(status)) {
michael@0:             return TRUE;
michael@0:         }
michael@0:         while (ce != firstce) {
michael@0:             if (ce != UCOL_IGNORABLE) {
michael@0:                 ignorable = FALSE;
michael@0:             }
michael@0:             ce = getCE(strsrch, ucol_next(coleiter, &status));
michael@0:             if (U_FAILURE(status) || ce == UCOL_NULLORDER) {
michael@0:                 return TRUE;
michael@0:             }
michael@0:         }
michael@0:         if (!ignorable && inNormBuf(coleiter)) {
michael@0:             // within normalization buffer, discontiguous handled here
michael@0:             return TRUE;
michael@0:         }
michael@0: 
michael@0:         // within text
michael@0:         int32_t temp = start;
michael@0:         // original code
michael@0:         // accent = (getFCD(strsrch->search->text, &temp,
michael@0:         //                  strsrch->search->textLength)
michael@0:         //            >> SECOND_LAST_BYTE_SHIFT_);
michael@0:         // however this code does not work well with VC7 .net in release mode.
michael@0:         // maybe the inlines for getFCD combined with shifting has bugs in
michael@0:         // VC7. anyways this is a work around.
michael@0:         UBool accent = getFCD(strsrch->search->text, &temp,
michael@0:                               strsrch->search->textLength) > 0xFF;
michael@0:         if (!accent) {
michael@0:             return checkExtraMatchAccents(strsrch, start, end, &status);
michael@0:         }
michael@0:         if (!ignorable) {
michael@0:             return TRUE;
michael@0:         }
michael@0:         if (start > 0) {
michael@0:             temp = start;
michael@0:             U16_BACK_1(strsrch->search->text, 0, temp);
michael@0:             if (getFCD(strsrch->search->text, &temp,
michael@0:                        strsrch->search->textLength) & LAST_BYTE_MASK_) {
michael@0:                 setColEIterOffset(coleiter, start);
michael@0:                 ce = ucol_previous(coleiter, &status);
michael@0:                 if (U_FAILURE(status) ||
michael@0:                     (ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE)) {
michael@0:                     return TRUE;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return FALSE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Used by exact matches, checks if there are accents bounding the match.
michael@0: * Note this is the initial boundary check. If the potential match
michael@0: * starts or ends with composite characters, the accents in those
michael@0: * characters will be determined later.
michael@0: * Not doing backwards iteration here, since discontiguos contraction for
michael@0: * backwards collation element iterator, use up too many characters.
michael@0: * E.g. looking for \u030A ring in \u01FA A ring above and acute,
michael@0: * should fail since there is a acute at the end of \u01FA
michael@0: * Note here that accents checking are slow and cautioned in the API docs.
michael@0: * @param strsrch string search data
michael@0: * @param start offset of match
michael@0: * @param end end offset of the match
michael@0: * @return TRUE if there are accents on either side of the match,
michael@0: *         FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool hasAccentsAfterMatch(const UStringSearch *strsrch, int32_t start,
michael@0:                                  int32_t    end)
michael@0: {
michael@0:     if (strsrch->pattern.hasSuffixAccents) {
michael@0:         const UChar       *text       = strsrch->search->text;
michael@0:               int32_t  temp       = end;
michael@0:               int32_t      textlength = strsrch->search->textLength;
michael@0:         U16_BACK_1(text, 0, temp);
michael@0:         if (getFCD(text, &temp, textlength) & LAST_BYTE_MASK_) {
michael@0:             int32_t             firstce  = strsrch->pattern.CE[0];
michael@0:             UCollationElements *coleiter = strsrch->textIter;
michael@0:             UErrorCode          status   = U_ZERO_ERROR;
michael@0:             int32_t ce;
michael@0:             setColEIterOffset(coleiter, start);
michael@0:             while ((ce = getCE(strsrch, ucol_next(coleiter, &status))) != firstce) {
michael@0:                 if (U_FAILURE(status) || ce == UCOL_NULLORDER) {
michael@0:                     return TRUE;
michael@0:                 }
michael@0:             }
michael@0:             int32_t count = 1;
michael@0:             while (count < strsrch->pattern.CELength) {
michael@0:                 if (getCE(strsrch, ucol_next(coleiter, &status))
michael@0:                     == UCOL_IGNORABLE) {
michael@0:                     // Thai can give an ignorable here.
michael@0:                     count --;
michael@0:                 }
michael@0:                 if (U_FAILURE(status)) {
michael@0:                     return TRUE;
michael@0:                 }
michael@0:                 count ++;
michael@0:             }
michael@0: 
michael@0:             ce = ucol_next(coleiter, &status);
michael@0:             if (U_FAILURE(status)) {
michael@0:                 return TRUE;
michael@0:             }
michael@0:             if (ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE) {
michael@0:                 ce = getCE(strsrch, ce);
michael@0:             }
michael@0:             if (ce != UCOL_NULLORDER && ce != UCOL_IGNORABLE) {
michael@0:                 if (ucol_getOffset(coleiter) <= end) {
michael@0:                     return TRUE;
michael@0:                 }
michael@0:                 if (getFCD(text, &end, textlength) >> SECOND_LAST_BYTE_SHIFT_) {
michael@0:                     return TRUE;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return FALSE;
michael@0: }
michael@0: #endif // #if BOYER_MOORE
michael@0: 
michael@0: /**
michael@0: * Checks if the offset runs out of the text string
michael@0: * @param offset
michael@0: * @param textlength of the text string
michael@0: * @return TRUE if offset is out of bounds, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool isOutOfBounds(int32_t textlength, int32_t offset)
michael@0: {
michael@0:     return offset < 0 || offset > textlength;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks for identical match
michael@0: * @param strsrch string search data
michael@0: * @param start offset of possible match
michael@0: * @param end offset of possible match
michael@0: * @return TRUE if identical match is found
michael@0: */
michael@0: static
michael@0: inline UBool checkIdentical(const UStringSearch *strsrch, int32_t start,
michael@0:                                   int32_t    end)
michael@0: {
michael@0:     if (strsrch->strength != UCOL_IDENTICAL) {
michael@0:         return TRUE;
michael@0:     }
michael@0: 
michael@0:     // Note: We could use Normalizer::compare() or similar, but for short strings
michael@0:     // which may not be in FCD it might be faster to just NFD them.
michael@0:     UErrorCode status = U_ZERO_ERROR;
michael@0:     UnicodeString t2, p2;
michael@0:     strsrch->nfd->normalize(
michael@0:         UnicodeString(FALSE, strsrch->search->text + start, end - start), t2, status);
michael@0:     strsrch->nfd->normalize(
michael@0:         UnicodeString(FALSE, strsrch->pattern.text, strsrch->pattern.textLength), p2, status);
michael@0:     // return FALSE if NFD failed
michael@0:     return U_SUCCESS(status) && t2 == p2;
michael@0: }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0: /**
michael@0: * Checks to see if the match is repeated
michael@0: * @param strsrch string search data
michael@0: * @param start new match start index
michael@0: * @param end new match end index
michael@0: * @return TRUE if the the match is repeated, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool checkRepeatedMatch(UStringSearch *strsrch,
michael@0:                                 int32_t    start,
michael@0:                                 int32_t    end)
michael@0: {
michael@0:     int32_t lastmatchindex = strsrch->search->matchedIndex;
michael@0:     UBool       result;
michael@0:     if (lastmatchindex == USEARCH_DONE) {
michael@0:         return FALSE;
michael@0:     }
michael@0:     if (strsrch->search->isForwardSearching) {
michael@0:         result = start <= lastmatchindex;
michael@0:     }
michael@0:     else {
michael@0:         result = start >= lastmatchindex;
michael@0:     }
michael@0:     if (!result && !strsrch->search->isOverlap) {
michael@0:         if (strsrch->search->isForwardSearching) {
michael@0:             result = start < lastmatchindex + strsrch->search->matchedLength;
michael@0:         }
michael@0:         else {
michael@0:             result = end > lastmatchindex;
michael@0:         }
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Gets the collation element iterator's current offset.
michael@0: * @param coleiter collation element iterator
michael@0: * @param forwards flag TRUE if we are moving in th forwards direction
michael@0: * @return current offset
michael@0: */
michael@0: static
michael@0: inline int32_t getColElemIterOffset(const UCollationElements *coleiter,
michael@0:                                               UBool               forwards)
michael@0: {
michael@0:     int32_t result = ucol_getOffset(coleiter);
michael@0:     // intricacies of the the backwards collation element iterator
michael@0:     if (FALSE && !forwards && inNormBuf(coleiter) && !isFCDPointerNull(coleiter)) {
michael@0:         result ++;
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks match for contraction.
michael@0: * If the match ends with a partial contraction we fail.
michael@0: * If the match starts too far off (because of backwards iteration) we try to
michael@0: * chip off the extra characters depending on whether a breakiterator has
michael@0: * been used.
michael@0: * Internal method, error assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param start offset of potential match, to be modified if necessary
michael@0: * @param end offset of potential match, to be modified if necessary
michael@0: * @param status output error status if any
michael@0: * @return TRUE if match passes the contraction test, FALSE otherwise
michael@0: */
michael@0: 
michael@0: static
michael@0: UBool checkNextExactContractionMatch(UStringSearch *strsrch,
michael@0:                                      int32_t   *start,
michael@0:                                      int32_t   *end, UErrorCode  *status)
michael@0: {
michael@0:           UCollationElements *coleiter   = strsrch->textIter;
michael@0:           int32_t             textlength = strsrch->search->textLength;
michael@0:           int32_t             temp       = *start;
michael@0:     const UCollator          *collator   = strsrch->collator;
michael@0:     const UChar              *text       = strsrch->search->text;
michael@0:     // This part checks if either ends of the match contains potential
michael@0:     // contraction. If so we'll have to iterate through them
michael@0:     // The start contraction needs to be checked since ucol_previous dumps
michael@0:     // all characters till the first safe character into the buffer.
michael@0:     // *start + 1 is used to test for the unsafe characters instead of *start
michael@0:     // because ucol_prev takes all unsafe characters till the first safe
michael@0:     // character ie *start. so by testing *start + 1, we can estimate if
michael@0:     // excess prefix characters has been included in the potential search
michael@0:     // results.
michael@0:     if ((*end < textlength && ucol_unsafeCP(text[*end], collator)) ||
michael@0:         (*start + 1 < textlength
michael@0:          && ucol_unsafeCP(text[*start + 1], collator))) {
michael@0:         int32_t expansion  = getExpansionPrefix(coleiter);
michael@0:         UBool   expandflag = expansion > 0;
michael@0:         setColEIterOffset(coleiter, *start);
michael@0:         while (expansion > 0) {
michael@0:             // getting rid of the redundant ce, caused by setOffset.
michael@0:             // since backward contraction/expansion may have extra ces if we
michael@0:             // are in the normalization buffer, hasAccentsBeforeMatch would
michael@0:             // have taken care of it.
michael@0:             // E.g. the character \u01FA will have an expansion of 3, but if
michael@0:             // we are only looking for acute and ring \u030A and \u0301, we'll
michael@0:             // have to skip the first ce in the expansion buffer.
michael@0:             ucol_next(coleiter, status);
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return FALSE;
michael@0:             }
michael@0:             if (ucol_getOffset(coleiter) != temp) {
michael@0:                 *start = temp;
michael@0:                 temp  = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             expansion --;
michael@0:         }
michael@0: 
michael@0:         int32_t  *patternce       = strsrch->pattern.CE;
michael@0:         int32_t   patterncelength = strsrch->pattern.CELength;
michael@0:         int32_t   count           = 0;
michael@0:         while (count < patterncelength) {
michael@0:             int32_t ce = getCE(strsrch, ucol_next(coleiter, status));
michael@0:             if (ce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (expandflag && count == 0 && ucol_getOffset(coleiter) != temp) {
michael@0:                 *start = temp;
michael@0:                 temp   = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             if (U_FAILURE(*status) || ce != patternce[count]) {
michael@0:                 (*end) ++;
michael@0:                 *end = getNextUStringSearchBaseOffset(strsrch, *end);
michael@0:                 return FALSE;
michael@0:             }
michael@0:             count ++;
michael@0:         }
michael@0:     }
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks and sets the match information if found.
michael@0: * Checks
michael@0: * <ul>
michael@0: * <li> the potential match does not repeat the previous match
michael@0: * <li> boundaries are correct
michael@0: * <li> exact matches has no extra accents
michael@0: * <li> identical matchesb
michael@0: * <li> potential match does not end in the middle of a contraction
michael@0: * <\ul>
michael@0: * Otherwise the offset will be shifted to the next character.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset offset in the collation element text. the returned value
michael@0: *        will be the truncated end offset of the match or the new start
michael@0: *        search offset.
michael@0: * @param status output error status if any
michael@0: * @return TRUE if the match is valid, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool checkNextExactMatch(UStringSearch *strsrch,
michael@0:                                  int32_t   *textoffset, UErrorCode *status)
michael@0: {
michael@0:     UCollationElements *coleiter = strsrch->textIter;
michael@0:     int32_t         start    = getColElemIterOffset(coleiter, FALSE);
michael@0: 
michael@0:     if (!checkNextExactContractionMatch(strsrch, &start, textoffset, status)) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     // this totally matches, however we need to check if it is repeating
michael@0:     if (!isBreakUnit(strsrch, start, *textoffset) ||
michael@0:         checkRepeatedMatch(strsrch, start, *textoffset) ||
michael@0:         hasAccentsBeforeMatch(strsrch, start, *textoffset) ||
michael@0:         !checkIdentical(strsrch, start, *textoffset) ||
michael@0:         hasAccentsAfterMatch(strsrch, start, *textoffset)) {
michael@0: 
michael@0:         (*textoffset) ++;
michael@0:         *textoffset = getNextUStringSearchBaseOffset(strsrch, *textoffset);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     //Add breakiterator boundary check for primary strength search.
michael@0:     if (!strsrch->search->breakIter && strsrch->strength == UCOL_PRIMARY) {
michael@0:         checkBreakBoundary(strsrch, &start, textoffset);
michael@0:     }
michael@0: 
michael@0:     // totally match, we will get rid of the ending ignorables.
michael@0:     strsrch->search->matchedIndex  = start;
michael@0:     strsrch->search->matchedLength = *textoffset - start;
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Getting the previous base character offset, or the current offset if the
michael@0: * current character is a base character
michael@0: * @param text string
michael@0: * @param textoffset one offset after the current character
michael@0: * @return the offset of the next character after the base character or the first
michael@0: *         composed character with accents
michael@0: */
michael@0: static
michael@0: inline int32_t getPreviousBaseOffset(const UChar       *text,
michael@0:                                                int32_t  textoffset)
michael@0: {
michael@0:     if (textoffset > 0) {
michael@0:         for (;;) {
michael@0:             int32_t result = textoffset;
michael@0:             U16_BACK_1(text, 0, textoffset);
michael@0:             int32_t temp = textoffset;
michael@0:             uint16_t fcd = getFCD(text, &temp, result);
michael@0:             if ((fcd >> SECOND_LAST_BYTE_SHIFT_) == 0) {
michael@0:                 if (fcd & LAST_BYTE_MASK_) {
michael@0:                     return textoffset;
michael@0:                 }
michael@0:                 return result;
michael@0:             }
michael@0:             if (textoffset == 0) {
michael@0:                 return 0;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return textoffset;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Getting the indexes of the accents that are not blocked in the argument
michael@0: * accent array
michael@0: * @param accents array of accents in nfd terminated by a 0.
michael@0: * @param accentsindex array of indexes of the accents that are not blocked
michael@0: */
michael@0: static
michael@0: inline int getUnblockedAccentIndex(UChar *accents, int32_t *accentsindex)
michael@0: {
michael@0:     int32_t index     = 0;
michael@0:     int32_t     length    = u_strlen(accents);
michael@0:     UChar32     codepoint = 0;
michael@0:     int         cclass    = 0;
michael@0:     int         result    = 0;
michael@0:     int32_t temp;
michael@0:     while (index < length) {
michael@0:         temp = index;
michael@0:         U16_NEXT(accents, index, length, codepoint);
michael@0:         if (u_getCombiningClass(codepoint) != cclass) {
michael@0:             cclass        = u_getCombiningClass(codepoint);
michael@0:             accentsindex[result] = temp;
michael@0:             result ++;
michael@0:         }
michael@0:     }
michael@0:     accentsindex[result] = length;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Appends 3 UChar arrays to a destination array.
michael@0: * Creates a new array if we run out of space. The caller will have to
michael@0: * manually deallocate the newly allocated array.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method. destination not to be NULL and has at least
michael@0: * size destinationlength.
michael@0: * @param destination target array
michael@0: * @param destinationlength target array size, returning the appended length
michael@0: * @param source1 null-terminated first array
michael@0: * @param source2 second array
michael@0: * @param source2length length of seond array
michael@0: * @param source3 null-terminated third array
michael@0: * @param status error status if any
michael@0: * @return new destination array, destination if there was no new allocation
michael@0: */
michael@0: static
michael@0: inline UChar * addToUCharArray(      UChar      *destination,
michael@0:                                      int32_t    *destinationlength,
michael@0:                                const UChar      *source1,
michael@0:                                const UChar      *source2,
michael@0:                                      int32_t     source2length,
michael@0:                                const UChar      *source3,
michael@0:                                      UErrorCode *status)
michael@0: {
michael@0:     int32_t source1length = source1 ? u_strlen(source1) : 0;
michael@0:     int32_t source3length = source3 ? u_strlen(source3) : 0;
michael@0:     if (*destinationlength < source1length + source2length + source3length +
michael@0:                                                                            1)
michael@0:     {
michael@0:         destination = (UChar *)allocateMemory(
michael@0:           (source1length + source2length + source3length + 1) * sizeof(UChar),
michael@0:           status);
michael@0:         // if error allocating memory, status will be
michael@0:         // U_MEMORY_ALLOCATION_ERROR
michael@0:         if (U_FAILURE(*status)) {
michael@0:             *destinationlength = 0;
michael@0:             return NULL;
michael@0:         }
michael@0:     }
michael@0:     if (source1length != 0) {
michael@0:         uprv_memcpy(destination, source1, sizeof(UChar) * source1length);
michael@0:     }
michael@0:     if (source2length != 0) {
michael@0:         uprv_memcpy(destination + source1length, source2,
michael@0:                     sizeof(UChar) * source2length);
michael@0:     }
michael@0:     if (source3length != 0) {
michael@0:         uprv_memcpy(destination + source1length + source2length, source3,
michael@0:                     sizeof(UChar) * source3length);
michael@0:     }
michael@0:     *destinationlength = source1length + source2length + source3length;
michael@0:     return destination;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Running through a collation element iterator to see if the contents matches
michael@0: * pattern in string search data
michael@0: * @param strsrch string search data
michael@0: * @param coleiter collation element iterator
michael@0: * @return TRUE if a match if found, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool checkCollationMatch(const UStringSearch      *strsrch,
michael@0:                                        UCollationElements *coleiter)
michael@0: {
michael@0:     int         patternceindex = strsrch->pattern.CELength;
michael@0:     int32_t    *patternce      = strsrch->pattern.CE;
michael@0:     UErrorCode  status = U_ZERO_ERROR;
michael@0:     while (patternceindex > 0) {
michael@0:         int32_t ce = getCE(strsrch, ucol_next(coleiter, &status));
michael@0:         if (ce == UCOL_IGNORABLE) {
michael@0:             continue;
michael@0:         }
michael@0:         if (U_FAILURE(status) || ce != *patternce) {
michael@0:             return FALSE;
michael@0:         }
michael@0:         patternce ++;
michael@0:         patternceindex --;
michael@0:     }
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Rearranges the front accents to try matching.
michael@0: * Prefix accents in the text will be grouped according to their combining
michael@0: * class and the groups will be mixed and matched to try find the perfect
michael@0: * match with the pattern.
michael@0: * So for instance looking for "\u0301" in "\u030A\u0301\u0325"
michael@0: * step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
michael@0: *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
michael@0: *         "\u0301\u0325".
michael@0: * step 2: check if any of the generated substrings matches the pattern.
michael@0: * Internal method, status is assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search match
michael@0: * @param start first offset of the accents to start searching
michael@0: * @param end start of the last accent set
michael@0: * @param status output error status if any
michael@0: * @return USEARCH_DONE if a match is not found, otherwise return the starting
michael@0: *         offset of the match. Note this start includes all preceding accents.
michael@0: */
michael@0: static
michael@0: int32_t doNextCanonicalPrefixMatch(UStringSearch *strsrch,
michael@0:                                        int32_t    start,
michael@0:                                        int32_t    end,
michael@0:                                        UErrorCode    *status)
michael@0: {
michael@0:     const UChar       *text       = strsrch->search->text;
michael@0:           int32_t      textlength = strsrch->search->textLength;
michael@0:           int32_t  tempstart  = start;
michael@0: 
michael@0:     if ((getFCD(text, &tempstart, textlength) & LAST_BYTE_MASK_) == 0) {
michael@0:         // die... failed at a base character
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0: 
michael@0:     int32_t offset = getNextBaseOffset(text, tempstart, textlength);
michael@0:     start = getPreviousBaseOffset(text, tempstart);
michael@0: 
michael@0:     UChar       accents[INITIAL_ARRAY_SIZE_];
michael@0:     // normalizing the offensive string
michael@0:     unorm_normalize(text + start, offset - start, UNORM_NFD, 0, accents,
michael@0:                     INITIAL_ARRAY_SIZE_, status);
michael@0:     if (U_FAILURE(*status)) {
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0: 
michael@0:     int32_t         accentsindex[INITIAL_ARRAY_SIZE_];
michael@0:     int32_t         accentsize = getUnblockedAccentIndex(accents,
michael@0:                                                                  accentsindex);
michael@0:     int32_t         count      = (2 << (accentsize - 1)) - 1;
michael@0:     UChar               buffer[INITIAL_ARRAY_SIZE_];
michael@0:     UCollationElements *coleiter   = strsrch->utilIter;
michael@0:     while (U_SUCCESS(*status) && count > 0) {
michael@0:         UChar *rearrange = strsrch->canonicalPrefixAccents;
michael@0:         // copy the base characters
michael@0:         for (int k = 0; k < accentsindex[0]; k ++) {
michael@0:             *rearrange ++ = accents[k];
michael@0:         }
michael@0:         // forming all possible canonical rearrangement by dropping
michael@0:         // sets of accents
michael@0:         for (int i = 0; i <= accentsize - 1; i ++) {
michael@0:             int32_t mask = 1 << (accentsize - i - 1);
michael@0:             if (count & mask) {
michael@0:                 for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
michael@0:                     *rearrange ++ = accents[j];
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         *rearrange = 0;
michael@0:         int32_t  matchsize = INITIAL_ARRAY_SIZE_;
michael@0:         UChar   *match     = addToUCharArray(buffer, &matchsize,
michael@0:                                            strsrch->canonicalPrefixAccents,
michael@0:                                            strsrch->search->text + offset,
michael@0:                                            end - offset,
michael@0:                                            strsrch->canonicalSuffixAccents,
michael@0:                                            status);
michael@0: 
michael@0:         // if status is a failure, ucol_setText does nothing.
michael@0:         // run the collator iterator through this match
michael@0:         ucol_setText(coleiter, match, matchsize, status);
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             if (checkCollationMatch(strsrch, coleiter)) {
michael@0:                 if (match != buffer) {
michael@0:                     uprv_free(match);
michael@0:                 }
michael@0:                 return start;
michael@0:             }
michael@0:         }
michael@0:         count --;
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Gets the offset to the safe point in text before textoffset.
michael@0: * ie. not the middle of a contraction, swappable characters or supplementary
michael@0: * characters.
michael@0: * @param collator collation sata
michael@0: * @param text string to work with
michael@0: * @param textoffset offset in string
michael@0: * @param textlength length of text string
michael@0: * @return offset to the previous safe character
michael@0: */
michael@0: static
michael@0: inline uint32_t getPreviousSafeOffset(const UCollator   *collator,
michael@0:                                       const UChar       *text,
michael@0:                                             int32_t  textoffset)
michael@0: {
michael@0:     int32_t result = textoffset; // first contraction character
michael@0:     while (result != 0 && ucol_unsafeCP(text[result - 1], collator)) {
michael@0:         result --;
michael@0:     }
michael@0:     if (result != 0) {
michael@0:         // the first contraction character is consider unsafe here
michael@0:         result --;
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Cleaning up after we passed the safe zone
michael@0: * @param strsrch string search data
michael@0: * @param safetext safe text array
michael@0: * @param safebuffer safe text buffer
michael@0: * @param coleiter collation element iterator for safe text
michael@0: */
michael@0: static
michael@0: inline void cleanUpSafeText(const UStringSearch *strsrch, UChar *safetext,
michael@0:                                   UChar         *safebuffer)
michael@0: {
michael@0:     if (safetext != safebuffer && safetext != strsrch->canonicalSuffixAccents)
michael@0:     {
michael@0:        uprv_free(safetext);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Take the rearranged end accents and tries matching. If match failed at
michael@0: * a seperate preceding set of accents (seperated from the rearranged on by
michael@0: * at least a base character) then we rearrange the preceding accents and
michael@0: * tries matching again.
michael@0: * We allow skipping of the ends of the accent set if the ces do not match.
michael@0: * However if the failure is found before the accent set, it fails.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset of the start of the rearranged accent
michael@0: * @param status output error status if any
michael@0: * @return USEARCH_DONE if a match is not found, otherwise return the starting
michael@0: *         offset of the match. Note this start includes all preceding accents.
michael@0: */
michael@0: static
michael@0: int32_t doNextCanonicalSuffixMatch(UStringSearch *strsrch,
michael@0:                                        int32_t    textoffset,
michael@0:                                        UErrorCode    *status)
michael@0: {
michael@0:     const UChar              *text           = strsrch->search->text;
michael@0:     const UCollator          *collator       = strsrch->collator;
michael@0:           int32_t             safelength     = 0;
michael@0:           UChar              *safetext;
michael@0:           int32_t             safetextlength;
michael@0:           UChar               safebuffer[INITIAL_ARRAY_SIZE_];
michael@0:           UCollationElements *coleiter       = strsrch->utilIter;
michael@0:           int32_t         safeoffset     = textoffset;
michael@0: 
michael@0:     if (textoffset != 0 && ucol_unsafeCP(strsrch->canonicalSuffixAccents[0],
michael@0:                                          collator)) {
michael@0:         safeoffset     = getPreviousSafeOffset(collator, text, textoffset);
michael@0:         safelength     = textoffset - safeoffset;
michael@0:         safetextlength = INITIAL_ARRAY_SIZE_;
michael@0:         safetext       = addToUCharArray(safebuffer, &safetextlength, NULL,
michael@0:                                          text + safeoffset, safelength,
michael@0:                                          strsrch->canonicalSuffixAccents,
michael@0:                                          status);
michael@0:     }
michael@0:     else {
michael@0:         safetextlength = u_strlen(strsrch->canonicalSuffixAccents);
michael@0:         safetext       = strsrch->canonicalSuffixAccents;
michael@0:     }
michael@0: 
michael@0:     // if status is a failure, ucol_setText does nothing
michael@0:     ucol_setText(coleiter, safetext, safetextlength, status);
michael@0:     // status checked in loop below
michael@0: 
michael@0:     int32_t  *ce        = strsrch->pattern.CE;
michael@0:     int32_t   celength  = strsrch->pattern.CELength;
michael@0:     int       ceindex   = celength - 1;
michael@0:     UBool     isSafe    = TRUE; // indication flag for position in safe zone
michael@0: 
michael@0:     while (ceindex >= 0) {
michael@0:         int32_t textce = ucol_previous(coleiter, status);
michael@0:         if (U_FAILURE(*status)) {
michael@0:             if (isSafe) {
michael@0:                 cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:             }
michael@0:             return USEARCH_DONE;
michael@0:         }
michael@0:         if (textce == UCOL_NULLORDER) {
michael@0:             // check if we have passed the safe buffer
michael@0:             if (coleiter == strsrch->textIter) {
michael@0:                 cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0:             cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:             safetext = safebuffer;
michael@0:             coleiter = strsrch->textIter;
michael@0:             setColEIterOffset(coleiter, safeoffset);
michael@0:             // status checked at the start of the loop
michael@0:             isSafe = FALSE;
michael@0:             continue;
michael@0:         }
michael@0:         textce = getCE(strsrch, textce);
michael@0:         if (textce != UCOL_IGNORABLE && textce != ce[ceindex]) {
michael@0:             // do the beginning stuff
michael@0:             int32_t failedoffset = getColElemIterOffset(coleiter, FALSE);
michael@0:             if (isSafe && failedoffset >= safelength) {
michael@0:                 // alas... no hope. failed at rearranged accent set
michael@0:                 cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0:             else {
michael@0:                 if (isSafe) {
michael@0:                     failedoffset += safeoffset;
michael@0:                     cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:                 }
michael@0: 
michael@0:                 // try rearranging the front accents
michael@0:                 int32_t result = doNextCanonicalPrefixMatch(strsrch,
michael@0:                                         failedoffset, textoffset, status);
michael@0:                 if (result != USEARCH_DONE) {
michael@0:                     // if status is a failure, ucol_setOffset does nothing
michael@0:                     setColEIterOffset(strsrch->textIter, result);
michael@0:                 }
michael@0:                 if (U_FAILURE(*status)) {
michael@0:                     return USEARCH_DONE;
michael@0:                 }
michael@0:                 return result;
michael@0:             }
michael@0:         }
michael@0:         if (textce == ce[ceindex]) {
michael@0:             ceindex --;
michael@0:         }
michael@0:     }
michael@0:     // set offset here
michael@0:     if (isSafe) {
michael@0:         int32_t result     = getColElemIterOffset(coleiter, FALSE);
michael@0:         // sets the text iterator here with the correct expansion and offset
michael@0:         int32_t    leftoverces = getExpansionPrefix(coleiter);
michael@0:         cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:         if (result >= safelength) {
michael@0:             result = textoffset;
michael@0:         }
michael@0:         else {
michael@0:             result += safeoffset;
michael@0:         }
michael@0:         setColEIterOffset(strsrch->textIter, result);
michael@0:         strsrch->textIter->iteratordata_.toReturn =
michael@0:                        setExpansionPrefix(strsrch->textIter, leftoverces);
michael@0:         return result;
michael@0:     }
michael@0: 
michael@0:     return ucol_getOffset(coleiter);
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Trying out the substring and sees if it can be a canonical match.
michael@0: * This will try normalizing the end accents and arranging them into canonical
michael@0: * equivalents and check their corresponding ces with the pattern ce.
michael@0: * Suffix accents in the text will be grouped according to their combining
michael@0: * class and the groups will be mixed and matched to try find the perfect
michael@0: * match with the pattern.
michael@0: * So for instance looking for "\u0301" in "\u030A\u0301\u0325"
michael@0: * step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
michael@0: *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
michael@0: *         "\u0301\u0325".
michael@0: * step 2: check if any of the generated substrings matches the pattern.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset end offset in the collation element text that ends with
michael@0: *                   the accents to be rearranged
michael@0: * @param status error status if any
michael@0: * @return TRUE if the match is valid, FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool doNextCanonicalMatch(UStringSearch *strsrch,
michael@0:                            int32_t    textoffset,
michael@0:                            UErrorCode    *status)
michael@0: {
michael@0:     const UChar       *text = strsrch->search->text;
michael@0:           int32_t  temp = textoffset;
michael@0:     U16_BACK_1(text, 0, temp);
michael@0:     if ((getFCD(text, &temp, textoffset) & LAST_BYTE_MASK_) == 0) {
michael@0:         UCollationElements *coleiter = strsrch->textIter;
michael@0:         int32_t         offset   = getColElemIterOffset(coleiter, FALSE);
michael@0:         if (strsrch->pattern.hasPrefixAccents) {
michael@0:             offset = doNextCanonicalPrefixMatch(strsrch, offset, textoffset,
michael@0:                                                 status);
michael@0:             if (U_SUCCESS(*status) && offset != USEARCH_DONE) {
michael@0:                 setColEIterOffset(coleiter, offset);
michael@0:                 return TRUE;
michael@0:             }
michael@0:         }
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     if (!strsrch->pattern.hasSuffixAccents) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     UChar       accents[INITIAL_ARRAY_SIZE_];
michael@0:     // offset to the last base character in substring to search
michael@0:     int32_t baseoffset = getPreviousBaseOffset(text, textoffset);
michael@0:     // normalizing the offensive string
michael@0:     unorm_normalize(text + baseoffset, textoffset - baseoffset, UNORM_NFD,
michael@0:                                0, accents, INITIAL_ARRAY_SIZE_, status);
michael@0:     // status checked in loop below
michael@0: 
michael@0:     int32_t accentsindex[INITIAL_ARRAY_SIZE_];
michael@0:     int32_t size = getUnblockedAccentIndex(accents, accentsindex);
michael@0: 
michael@0:     // 2 power n - 1 plus the full set of accents
michael@0:     int32_t  count = (2 << (size - 1)) - 1;
michael@0:     while (U_SUCCESS(*status) && count > 0) {
michael@0:         UChar *rearrange = strsrch->canonicalSuffixAccents;
michael@0:         // copy the base characters
michael@0:         for (int k = 0; k < accentsindex[0]; k ++) {
michael@0:             *rearrange ++ = accents[k];
michael@0:         }
michael@0:         // forming all possible canonical rearrangement by dropping
michael@0:         // sets of accents
michael@0:         for (int i = 0; i <= size - 1; i ++) {
michael@0:             int32_t mask = 1 << (size - i - 1);
michael@0:             if (count & mask) {
michael@0:                 for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
michael@0:                     *rearrange ++ = accents[j];
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         *rearrange = 0;
michael@0:         int32_t offset = doNextCanonicalSuffixMatch(strsrch, baseoffset,
michael@0:                                                         status);
michael@0:         if (offset != USEARCH_DONE) {
michael@0:             return TRUE; // match found
michael@0:         }
michael@0:         count --;
michael@0:     }
michael@0:     return FALSE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Gets the previous base character offset depending on the string search
michael@0: * pattern data
michael@0: * @param strsrch string search data
michael@0: * @param textoffset current offset, current character
michael@0: * @return the offset of the next character after this base character or itself
michael@0: *         if it is a composed character with accents
michael@0: */
michael@0: static
michael@0: inline int32_t getPreviousUStringSearchBaseOffset(UStringSearch *strsrch,
michael@0:                                                       int32_t textoffset)
michael@0: {
michael@0:     if (strsrch->pattern.hasPrefixAccents && textoffset > 0) {
michael@0:         const UChar       *text = strsrch->search->text;
michael@0:               int32_t  offset = textoffset;
michael@0:         if (getFCD(text, &offset, strsrch->search->textLength) >>
michael@0:                                                    SECOND_LAST_BYTE_SHIFT_) {
michael@0:             return getPreviousBaseOffset(text, textoffset);
michael@0:         }
michael@0:     }
michael@0:     return textoffset;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks match for contraction.
michael@0: * If the match ends with a partial contraction we fail.
michael@0: * If the match starts too far off (because of backwards iteration) we try to
michael@0: * chip off the extra characters
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param start offset of potential match, to be modified if necessary
michael@0: * @param end offset of potential match, to be modified if necessary
michael@0: * @param status output error status if any
michael@0: * @return TRUE if match passes the contraction test, FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool checkNextCanonicalContractionMatch(UStringSearch *strsrch,
michael@0:                                          int32_t   *start,
michael@0:                                          int32_t   *end,
michael@0:                                          UErrorCode    *status)
michael@0: {
michael@0:           UCollationElements *coleiter   = strsrch->textIter;
michael@0:           int32_t             textlength = strsrch->search->textLength;
michael@0:           int32_t         temp       = *start;
michael@0:     const UCollator          *collator   = strsrch->collator;
michael@0:     const UChar              *text       = strsrch->search->text;
michael@0:     // This part checks if either ends of the match contains potential
michael@0:     // contraction. If so we'll have to iterate through them
michael@0:     if ((*end < textlength && ucol_unsafeCP(text[*end], collator)) ||
michael@0:         (*start + 1 < textlength
michael@0:          && ucol_unsafeCP(text[*start + 1], collator))) {
michael@0:         int32_t expansion  = getExpansionPrefix(coleiter);
michael@0:         UBool   expandflag = expansion > 0;
michael@0:         setColEIterOffset(coleiter, *start);
michael@0:         while (expansion > 0) {
michael@0:             // getting rid of the redundant ce, caused by setOffset.
michael@0:             // since backward contraction/expansion may have extra ces if we
michael@0:             // are in the normalization buffer, hasAccentsBeforeMatch would
michael@0:             // have taken care of it.
michael@0:             // E.g. the character \u01FA will have an expansion of 3, but if
michael@0:             // we are only looking for acute and ring \u030A and \u0301, we'll
michael@0:             // have to skip the first ce in the expansion buffer.
michael@0:             ucol_next(coleiter, status);
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return FALSE;
michael@0:             }
michael@0:             if (ucol_getOffset(coleiter) != temp) {
michael@0:                 *start = temp;
michael@0:                 temp  = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             expansion --;
michael@0:         }
michael@0: 
michael@0:         int32_t  *patternce       = strsrch->pattern.CE;
michael@0:         int32_t   patterncelength = strsrch->pattern.CELength;
michael@0:         int32_t   count           = 0;
michael@0:         int32_t   textlength      = strsrch->search->textLength;
michael@0:         while (count < patterncelength) {
michael@0:             int32_t ce = getCE(strsrch, ucol_next(coleiter, status));
michael@0:             // status checked below, note that if status is a failure
michael@0:             // ucol_next returns UCOL_NULLORDER
michael@0:             if (ce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (expandflag && count == 0 && ucol_getOffset(coleiter) != temp) {
michael@0:                 *start = temp;
michael@0:                 temp   = ucol_getOffset(coleiter);
michael@0:             }
michael@0: 
michael@0:             if (count == 0 && ce != patternce[0]) {
michael@0:                 // accents may have extra starting ces, this occurs when a
michael@0:                 // pure accent pattern is matched without rearrangement
michael@0:                 // text \u0325\u0300 and looking for \u0300
michael@0:                 int32_t expected = patternce[0];
michael@0:                 if (getFCD(text, start, textlength) & LAST_BYTE_MASK_) {
michael@0:                     ce = getCE(strsrch, ucol_next(coleiter, status));
michael@0:                     while (U_SUCCESS(*status) && ce != expected &&
michael@0:                            ce != UCOL_NULLORDER &&
michael@0:                            ucol_getOffset(coleiter) <= *end) {
michael@0:                         ce = getCE(strsrch, ucol_next(coleiter, status));
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             if (U_FAILURE(*status) || ce != patternce[count]) {
michael@0:                 (*end) ++;
michael@0:                 *end = getNextUStringSearchBaseOffset(strsrch, *end);
michael@0:                 return FALSE;
michael@0:             }
michael@0:             count ++;
michael@0:         }
michael@0:     }
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks and sets the match information if found.
michael@0: * Checks
michael@0: * <ul>
michael@0: * <li> the potential match does not repeat the previous match
michael@0: * <li> boundaries are correct
michael@0: * <li> potential match does not end in the middle of a contraction
michael@0: * <li> identical matches
michael@0: * <\ul>
michael@0: * Otherwise the offset will be shifted to the next character.
michael@0: * Internal method, status assumed to be success, caller has to check the
michael@0: * status before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset offset in the collation element text. the returned value
michael@0: *        will be the truncated end offset of the match or the new start
michael@0: *        search offset.
michael@0: * @param status output error status if any
michael@0: * @return TRUE if the match is valid, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool checkNextCanonicalMatch(UStringSearch *strsrch,
michael@0:                                      int32_t   *textoffset,
michael@0:                                      UErrorCode    *status)
michael@0: {
michael@0:     // to ensure that the start and ends are not composite characters
michael@0:     UCollationElements *coleiter = strsrch->textIter;
michael@0:     // if we have a canonical accent match
michael@0:     if ((strsrch->pattern.hasSuffixAccents &&
michael@0:         strsrch->canonicalSuffixAccents[0]) ||
michael@0:         (strsrch->pattern.hasPrefixAccents &&
michael@0:         strsrch->canonicalPrefixAccents[0])) {
michael@0:         strsrch->search->matchedIndex  = getPreviousUStringSearchBaseOffset(
michael@0:                                                     strsrch,
michael@0:                                                     ucol_getOffset(coleiter));
michael@0:         strsrch->search->matchedLength = *textoffset -
michael@0:                                                 strsrch->search->matchedIndex;
michael@0:         return TRUE;
michael@0:     }
michael@0: 
michael@0:     int32_t start = getColElemIterOffset(coleiter, FALSE);
michael@0:     if (!checkNextCanonicalContractionMatch(strsrch, &start, textoffset,
michael@0:                                             status) || U_FAILURE(*status)) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     start = getPreviousUStringSearchBaseOffset(strsrch, start);
michael@0:     // this totally matches, however we need to check if it is repeating
michael@0:     if (checkRepeatedMatch(strsrch, start, *textoffset) ||
michael@0:         !isBreakUnit(strsrch, start, *textoffset) ||
michael@0:         !checkIdentical(strsrch, start, *textoffset)) {
michael@0:         (*textoffset) ++;
michael@0:         *textoffset = getNextBaseOffset(strsrch->search->text, *textoffset,
michael@0:                                         strsrch->search->textLength);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     strsrch->search->matchedIndex  = start;
michael@0:     strsrch->search->matchedLength = *textoffset - start;
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Shifting the collation element iterator position forward to prepare for
michael@0: * a preceding match. If the first character is a unsafe character, we'll only
michael@0: * shift by 1 to capture contractions, normalization etc.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param text strsrch string search data
michael@0: * @param textoffset start text position to do search
michael@0: * @param ce the text ce which failed the match.
michael@0: * @param patternceindex index of the ce within the pattern ce buffer which
michael@0: *        failed the match
michael@0: * @return final offset
michael@0: */
michael@0: static
michael@0: inline int32_t reverseShift(UStringSearch *strsrch,
michael@0:                                 int32_t    textoffset,
michael@0:                                 int32_t       ce,
michael@0:                                 int32_t        patternceindex)
michael@0: {
michael@0:     if (strsrch->search->isOverlap) {
michael@0:         if (textoffset != strsrch->search->textLength) {
michael@0:             textoffset --;
michael@0:         }
michael@0:         else {
michael@0:             textoffset -= strsrch->pattern.defaultShiftSize;
michael@0:         }
michael@0:     }
michael@0:     else {
michael@0:         if (ce != UCOL_NULLORDER) {
michael@0:             int32_t shift = strsrch->pattern.backShift[hash(ce)];
michael@0: 
michael@0:             // this is to adjust for characters in the middle of the substring
michael@0:             // for matching that failed.
michael@0:             int32_t adjust = patternceindex;
michael@0:             if (adjust > 1 && shift > adjust) {
michael@0:                 shift -= adjust - 1;
michael@0:             }
michael@0:             textoffset -= shift;
michael@0:         }
michael@0:         else {
michael@0:             textoffset -= strsrch->pattern.defaultShiftSize;
michael@0:         }
michael@0:     }
michael@0:     textoffset = getPreviousUStringSearchBaseOffset(strsrch, textoffset);
michael@0:     return textoffset;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks match for contraction.
michael@0: * If the match starts with a partial contraction we fail.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param start offset of potential match, to be modified if necessary
michael@0: * @param end offset of potential match, to be modified if necessary
michael@0: * @param status output error status if any
michael@0: * @return TRUE if match passes the contraction test, FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool checkPreviousExactContractionMatch(UStringSearch *strsrch,
michael@0:                                      int32_t   *start,
michael@0:                                      int32_t   *end, UErrorCode  *status)
michael@0: {
michael@0:           UCollationElements *coleiter   = strsrch->textIter;
michael@0:           int32_t             textlength = strsrch->search->textLength;
michael@0:           int32_t             temp       = *end;
michael@0:     const UCollator          *collator   = strsrch->collator;
michael@0:     const UChar              *text       = strsrch->search->text;
michael@0:     // This part checks if either if the start of the match contains potential
michael@0:     // contraction. If so we'll have to iterate through them
michael@0:     // Since we used ucol_next while previously looking for the potential
michael@0:     // match, this guarantees that our end will not be a partial contraction,
michael@0:     // or a partial supplementary character.
michael@0:     if (*start < textlength && ucol_unsafeCP(text[*start], collator)) {
michael@0:         int32_t expansion  = getExpansionSuffix(coleiter);
michael@0:         UBool   expandflag = expansion > 0;
michael@0:         setColEIterOffset(coleiter, *end);
michael@0:         while (U_SUCCESS(*status) && expansion > 0) {
michael@0:             // getting rid of the redundant ce
michael@0:             // since forward contraction/expansion may have extra ces
michael@0:             // if we are in the normalization buffer, hasAccentsBeforeMatch
michael@0:             // would have taken care of it.
michael@0:             // E.g. the character \u01FA will have an expansion of 3, but if
michael@0:             // we are only looking for A ring A\u030A, we'll have to skip the
michael@0:             // last ce in the expansion buffer
michael@0:             ucol_previous(coleiter, status);
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return FALSE;
michael@0:             }
michael@0:             if (ucol_getOffset(coleiter) != temp) {
michael@0:                 *end = temp;
michael@0:                 temp  = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             expansion --;
michael@0:         }
michael@0: 
michael@0:         int32_t  *patternce       = strsrch->pattern.CE;
michael@0:         int32_t   patterncelength = strsrch->pattern.CELength;
michael@0:         int32_t   count           = patterncelength;
michael@0:         while (count > 0) {
michael@0:             int32_t ce = getCE(strsrch, ucol_previous(coleiter, status));
michael@0:             // status checked below, note that if status is a failure
michael@0:             // ucol_previous returns UCOL_NULLORDER
michael@0:             if (ce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (expandflag && count == 0 &&
michael@0:                 getColElemIterOffset(coleiter, FALSE) != temp) {
michael@0:                 *end = temp;
michael@0:                 temp  = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             if (U_FAILURE(*status) || ce != patternce[count - 1]) {
michael@0:                 (*start) --;
michael@0:                 *start = getPreviousBaseOffset(text, *start);
michael@0:                 return FALSE;
michael@0:             }
michael@0:             count --;
michael@0:         }
michael@0:     }
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks and sets the match information if found.
michael@0: * Checks
michael@0: * <ul>
michael@0: * <li> the current match does not repeat the last match
michael@0: * <li> boundaries are correct
michael@0: * <li> exact matches has no extra accents
michael@0: * <li> identical matches
michael@0: * <\ul>
michael@0: * Otherwise the offset will be shifted to the preceding character.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param collator
michael@0: * @param coleiter collation element iterator
michael@0: * @param text string
michael@0: * @param textoffset offset in the collation element text. the returned value
michael@0: *        will be the truncated start offset of the match or the new start
michael@0: *        search offset.
michael@0: * @param status output error status if any
michael@0: * @return TRUE if the match is valid, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool checkPreviousExactMatch(UStringSearch *strsrch,
michael@0:                                      int32_t   *textoffset,
michael@0:                                      UErrorCode    *status)
michael@0: {
michael@0:     // to ensure that the start and ends are not composite characters
michael@0:     int32_t end = ucol_getOffset(strsrch->textIter);
michael@0:     if (!checkPreviousExactContractionMatch(strsrch, textoffset, &end, status)
michael@0:         || U_FAILURE(*status)) {
michael@0:             return FALSE;
michael@0:     }
michael@0: 
michael@0:     // this totally matches, however we need to check if it is repeating
michael@0:     // the old match
michael@0:     if (checkRepeatedMatch(strsrch, *textoffset, end) ||
michael@0:         !isBreakUnit(strsrch, *textoffset, end) ||
michael@0:         hasAccentsBeforeMatch(strsrch, *textoffset, end) ||
michael@0:         !checkIdentical(strsrch, *textoffset, end) ||
michael@0:         hasAccentsAfterMatch(strsrch, *textoffset, end)) {
michael@0:         (*textoffset) --;
michael@0:         *textoffset = getPreviousBaseOffset(strsrch->search->text,
michael@0:                                             *textoffset);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     //Add breakiterator boundary check for primary strength search.
michael@0:     if (!strsrch->search->breakIter && strsrch->strength == UCOL_PRIMARY) {
michael@0:         checkBreakBoundary(strsrch, textoffset, &end);
michael@0:     }
michael@0: 
michael@0:     strsrch->search->matchedIndex = *textoffset;
michael@0:     strsrch->search->matchedLength = end - *textoffset;
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Rearranges the end accents to try matching.
michael@0: * Suffix accents in the text will be grouped according to their combining
michael@0: * class and the groups will be mixed and matched to try find the perfect
michael@0: * match with the pattern.
michael@0: * So for instance looking for "\u0301" in "\u030A\u0301\u0325"
michael@0: * step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
michael@0: *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
michael@0: *         "\u0301\u0325".
michael@0: * step 2: check if any of the generated substrings matches the pattern.
michael@0: * Internal method, status assumed to be success, user has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search match
michael@0: * @param start offset of the first base character
michael@0: * @param end start of the last accent set
michael@0: * @param status only error status if any
michael@0: * @return USEARCH_DONE if a match is not found, otherwise return the ending
michael@0: *         offset of the match. Note this start includes all following accents.
michael@0: */
michael@0: static
michael@0: int32_t doPreviousCanonicalSuffixMatch(UStringSearch *strsrch,
michael@0:                                            int32_t    start,
michael@0:                                            int32_t    end,
michael@0:                                            UErrorCode    *status)
michael@0: {
michael@0:     const UChar       *text       = strsrch->search->text;
michael@0:           int32_t  tempend    = end;
michael@0: 
michael@0:     U16_BACK_1(text, 0, tempend);
michael@0:     if (!(getFCD(text, &tempend, strsrch->search->textLength) &
michael@0:                                                            LAST_BYTE_MASK_)) {
michael@0:         // die... failed at a base character
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0:     end = getNextBaseOffset(text, end, strsrch->search->textLength);
michael@0: 
michael@0:     if (U_SUCCESS(*status)) {
michael@0:         UChar       accents[INITIAL_ARRAY_SIZE_];
michael@0:         int32_t offset = getPreviousBaseOffset(text, end);
michael@0:         // normalizing the offensive string
michael@0:         unorm_normalize(text + offset, end - offset, UNORM_NFD, 0, accents,
michael@0:                         INITIAL_ARRAY_SIZE_, status);
michael@0: 
michael@0:         int32_t         accentsindex[INITIAL_ARRAY_SIZE_];
michael@0:         int32_t         accentsize = getUnblockedAccentIndex(accents,
michael@0:                                                          accentsindex);
michael@0:         int32_t         count      = (2 << (accentsize - 1)) - 1;
michael@0:         UChar               buffer[INITIAL_ARRAY_SIZE_];
michael@0:         UCollationElements *coleiter = strsrch->utilIter;
michael@0:         while (U_SUCCESS(*status) && count > 0) {
michael@0:             UChar *rearrange = strsrch->canonicalSuffixAccents;
michael@0:             // copy the base characters
michael@0:             for (int k = 0; k < accentsindex[0]; k ++) {
michael@0:                 *rearrange ++ = accents[k];
michael@0:             }
michael@0:             // forming all possible canonical rearrangement by dropping
michael@0:             // sets of accents
michael@0:             for (int i = 0; i <= accentsize - 1; i ++) {
michael@0:                 int32_t mask = 1 << (accentsize - i - 1);
michael@0:                 if (count & mask) {
michael@0:                     for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
michael@0:                         *rearrange ++ = accents[j];
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             *rearrange = 0;
michael@0:             int32_t  matchsize = INITIAL_ARRAY_SIZE_;
michael@0:             UChar   *match     = addToUCharArray(buffer, &matchsize,
michael@0:                                            strsrch->canonicalPrefixAccents,
michael@0:                                            strsrch->search->text + start,
michael@0:                                            offset - start,
michael@0:                                            strsrch->canonicalSuffixAccents,
michael@0:                                            status);
michael@0: 
michael@0:             // run the collator iterator through this match
michael@0:             // if status is a failure ucol_setText does nothing
michael@0:             ucol_setText(coleiter, match, matchsize, status);
michael@0:             if (U_SUCCESS(*status)) {
michael@0:                 if (checkCollationMatch(strsrch, coleiter)) {
michael@0:                     if (match != buffer) {
michael@0:                         uprv_free(match);
michael@0:                     }
michael@0:                     return end;
michael@0:                 }
michael@0:             }
michael@0:             count --;
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Take the rearranged start accents and tries matching. If match failed at
michael@0: * a seperate following set of accents (seperated from the rearranged on by
michael@0: * at least a base character) then we rearrange the preceding accents and
michael@0: * tries matching again.
michael@0: * We allow skipping of the ends of the accent set if the ces do not match.
michael@0: * However if the failure is found before the accent set, it fails.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset of the ends of the rearranged accent
michael@0: * @param status output error status if any
michael@0: * @return USEARCH_DONE if a match is not found, otherwise return the ending
michael@0: *         offset of the match. Note this start includes all following accents.
michael@0: */
michael@0: static
michael@0: int32_t doPreviousCanonicalPrefixMatch(UStringSearch *strsrch,
michael@0:                                            int32_t    textoffset,
michael@0:                                            UErrorCode    *status)
michael@0: {
michael@0:     const UChar       *text       = strsrch->search->text;
michael@0:     const UCollator   *collator   = strsrch->collator;
michael@0:           int32_t      safelength = 0;
michael@0:           UChar       *safetext;
michael@0:           int32_t      safetextlength;
michael@0:           UChar        safebuffer[INITIAL_ARRAY_SIZE_];
michael@0:           int32_t  safeoffset = textoffset;
michael@0: 
michael@0:     if (textoffset &&
michael@0:         ucol_unsafeCP(strsrch->canonicalPrefixAccents[
michael@0:                                  u_strlen(strsrch->canonicalPrefixAccents) - 1
michael@0:                                          ], collator)) {
michael@0:         safeoffset     = getNextSafeOffset(collator, text, textoffset,
michael@0:                                            strsrch->search->textLength);
michael@0:         safelength     = safeoffset - textoffset;
michael@0:         safetextlength = INITIAL_ARRAY_SIZE_;
michael@0:         safetext       = addToUCharArray(safebuffer, &safetextlength,
michael@0:                                          strsrch->canonicalPrefixAccents,
michael@0:                                          text + textoffset, safelength,
michael@0:                                          NULL, status);
michael@0:     }
michael@0:     else {
michael@0:         safetextlength = u_strlen(strsrch->canonicalPrefixAccents);
michael@0:         safetext       = strsrch->canonicalPrefixAccents;
michael@0:     }
michael@0: 
michael@0:     UCollationElements *coleiter = strsrch->utilIter;
michael@0:      // if status is a failure, ucol_setText does nothing
michael@0:     ucol_setText(coleiter, safetext, safetextlength, status);
michael@0:     // status checked in loop below
michael@0: 
michael@0:     int32_t  *ce           = strsrch->pattern.CE;
michael@0:     int32_t   celength     = strsrch->pattern.CELength;
michael@0:     int       ceindex      = 0;
michael@0:     UBool     isSafe       = TRUE; // safe zone indication flag for position
michael@0:     int32_t   prefixlength = u_strlen(strsrch->canonicalPrefixAccents);
michael@0: 
michael@0:     while (ceindex < celength) {
michael@0:         int32_t textce = ucol_next(coleiter, status);
michael@0:         if (U_FAILURE(*status)) {
michael@0:             if (isSafe) {
michael@0:                 cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:             }
michael@0:             return USEARCH_DONE;
michael@0:         }
michael@0:         if (textce == UCOL_NULLORDER) {
michael@0:             // check if we have passed the safe buffer
michael@0:             if (coleiter == strsrch->textIter) {
michael@0:                 cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0:             cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:             safetext = safebuffer;
michael@0:             coleiter = strsrch->textIter;
michael@0:             setColEIterOffset(coleiter, safeoffset);
michael@0:             // status checked at the start of the loop
michael@0:             isSafe = FALSE;
michael@0:             continue;
michael@0:         }
michael@0:         textce = getCE(strsrch, textce);
michael@0:         if (textce != UCOL_IGNORABLE && textce != ce[ceindex]) {
michael@0:             // do the beginning stuff
michael@0:             int32_t failedoffset = ucol_getOffset(coleiter);
michael@0:             if (isSafe && failedoffset <= prefixlength) {
michael@0:                 // alas... no hope. failed at rearranged accent set
michael@0:                 cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0:             else {
michael@0:                 if (isSafe) {
michael@0:                     failedoffset = safeoffset - failedoffset;
michael@0:                     cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:                 }
michael@0: 
michael@0:                 // try rearranging the end accents
michael@0:                 int32_t result = doPreviousCanonicalSuffixMatch(strsrch,
michael@0:                                         textoffset, failedoffset, status);
michael@0:                 if (result != USEARCH_DONE) {
michael@0:                     // if status is a failure, ucol_setOffset does nothing
michael@0:                     setColEIterOffset(strsrch->textIter, result);
michael@0:                 }
michael@0:                 if (U_FAILURE(*status)) {
michael@0:                     return USEARCH_DONE;
michael@0:                 }
michael@0:                 return result;
michael@0:             }
michael@0:         }
michael@0:         if (textce == ce[ceindex]) {
michael@0:             ceindex ++;
michael@0:         }
michael@0:     }
michael@0:     // set offset here
michael@0:     if (isSafe) {
michael@0:         int32_t result      = ucol_getOffset(coleiter);
michael@0:         // sets the text iterator here with the correct expansion and offset
michael@0:         int32_t     leftoverces = getExpansionSuffix(coleiter);
michael@0:         cleanUpSafeText(strsrch, safetext, safebuffer);
michael@0:         if (result <= prefixlength) {
michael@0:             result = textoffset;
michael@0:         }
michael@0:         else {
michael@0:             result = textoffset + (safeoffset - result);
michael@0:         }
michael@0:         setColEIterOffset(strsrch->textIter, result);
michael@0:         setExpansionSuffix(strsrch->textIter, leftoverces);
michael@0:         return result;
michael@0:     }
michael@0: 
michael@0:     return ucol_getOffset(coleiter);
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Trying out the substring and sees if it can be a canonical match.
michael@0: * This will try normalizing the starting accents and arranging them into
michael@0: * canonical equivalents and check their corresponding ces with the pattern ce.
michael@0: * Prefix accents in the text will be grouped according to their combining
michael@0: * class and the groups will be mixed and matched to try find the perfect
michael@0: * match with the pattern.
michael@0: * So for instance looking for "\u0301" in "\u030A\u0301\u0325"
michael@0: * step 1: split "\u030A\u0301" into 6 other type of potential accent substrings
michael@0: *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325",
michael@0: *         "\u0301\u0325".
michael@0: * step 2: check if any of the generated substrings matches the pattern.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset start offset in the collation element text that starts
michael@0: *                   with the accents to be rearranged
michael@0: * @param status output error status if any
michael@0: * @return TRUE if the match is valid, FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool doPreviousCanonicalMatch(UStringSearch *strsrch,
michael@0:                                int32_t    textoffset,
michael@0:                                UErrorCode    *status)
michael@0: {
michael@0:     const UChar       *text       = strsrch->search->text;
michael@0:           int32_t  temp       = textoffset;
michael@0:           int32_t      textlength = strsrch->search->textLength;
michael@0:     if ((getFCD(text, &temp, textlength) >> SECOND_LAST_BYTE_SHIFT_) == 0) {
michael@0:         UCollationElements *coleiter = strsrch->textIter;
michael@0:         int32_t         offset   = ucol_getOffset(coleiter);
michael@0:         if (strsrch->pattern.hasSuffixAccents) {
michael@0:             offset = doPreviousCanonicalSuffixMatch(strsrch, textoffset,
michael@0:                                                     offset, status);
michael@0:             if (U_SUCCESS(*status) && offset != USEARCH_DONE) {
michael@0:                 setColEIterOffset(coleiter, offset);
michael@0:                 return TRUE;
michael@0:             }
michael@0:         }
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     if (!strsrch->pattern.hasPrefixAccents) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     UChar       accents[INITIAL_ARRAY_SIZE_];
michael@0:     // offset to the last base character in substring to search
michael@0:     int32_t baseoffset = getNextBaseOffset(text, textoffset, textlength);
michael@0:     // normalizing the offensive string
michael@0:     unorm_normalize(text + textoffset, baseoffset - textoffset, UNORM_NFD,
michael@0:                                0, accents, INITIAL_ARRAY_SIZE_, status);
michael@0:     // status checked in loop
michael@0: 
michael@0:     int32_t accentsindex[INITIAL_ARRAY_SIZE_];
michael@0:     int32_t size = getUnblockedAccentIndex(accents, accentsindex);
michael@0: 
michael@0:     // 2 power n - 1 plus the full set of accents
michael@0:     int32_t  count = (2 << (size - 1)) - 1;
michael@0:     while (U_SUCCESS(*status) && count > 0) {
michael@0:         UChar *rearrange = strsrch->canonicalPrefixAccents;
michael@0:         // copy the base characters
michael@0:         for (int k = 0; k < accentsindex[0]; k ++) {
michael@0:             *rearrange ++ = accents[k];
michael@0:         }
michael@0:         // forming all possible canonical rearrangement by dropping
michael@0:         // sets of accents
michael@0:         for (int i = 0; i <= size - 1; i ++) {
michael@0:             int32_t mask = 1 << (size - i - 1);
michael@0:             if (count & mask) {
michael@0:                 for (int j = accentsindex[i]; j < accentsindex[i + 1]; j ++) {
michael@0:                     *rearrange ++ = accents[j];
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         *rearrange = 0;
michael@0:         int32_t offset = doPreviousCanonicalPrefixMatch(strsrch,
michael@0:                                                           baseoffset, status);
michael@0:         if (offset != USEARCH_DONE) {
michael@0:             return TRUE; // match found
michael@0:         }
michael@0:         count --;
michael@0:     }
michael@0:     return FALSE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks match for contraction.
michael@0: * If the match starts with a partial contraction we fail.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param start offset of potential match, to be modified if necessary
michael@0: * @param end offset of potential match, to be modified if necessary
michael@0: * @param status only error status if any
michael@0: * @return TRUE if match passes the contraction test, FALSE otherwise
michael@0: */
michael@0: static
michael@0: UBool checkPreviousCanonicalContractionMatch(UStringSearch *strsrch,
michael@0:                                      int32_t   *start,
michael@0:                                      int32_t   *end, UErrorCode  *status)
michael@0: {
michael@0:           UCollationElements *coleiter   = strsrch->textIter;
michael@0:           int32_t             textlength = strsrch->search->textLength;
michael@0:           int32_t         temp       = *end;
michael@0:     const UCollator          *collator   = strsrch->collator;
michael@0:     const UChar              *text       = strsrch->search->text;
michael@0:     // This part checks if either if the start of the match contains potential
michael@0:     // contraction. If so we'll have to iterate through them
michael@0:     // Since we used ucol_next while previously looking for the potential
michael@0:     // match, this guarantees that our end will not be a partial contraction,
michael@0:     // or a partial supplementary character.
michael@0:     if (*start < textlength && ucol_unsafeCP(text[*start], collator)) {
michael@0:         int32_t expansion  = getExpansionSuffix(coleiter);
michael@0:         UBool   expandflag = expansion > 0;
michael@0:         setColEIterOffset(coleiter, *end);
michael@0:         while (expansion > 0) {
michael@0:             // getting rid of the redundant ce
michael@0:             // since forward contraction/expansion may have extra ces
michael@0:             // if we are in the normalization buffer, hasAccentsBeforeMatch
michael@0:             // would have taken care of it.
michael@0:             // E.g. the character \u01FA will have an expansion of 3, but if
michael@0:             // we are only looking for A ring A\u030A, we'll have to skip the
michael@0:             // last ce in the expansion buffer
michael@0:             ucol_previous(coleiter, status);
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return FALSE;
michael@0:             }
michael@0:             if (ucol_getOffset(coleiter) != temp) {
michael@0:                 *end = temp;
michael@0:                 temp  = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             expansion --;
michael@0:         }
michael@0: 
michael@0:         int32_t  *patternce       = strsrch->pattern.CE;
michael@0:         int32_t   patterncelength = strsrch->pattern.CELength;
michael@0:         int32_t   count           = patterncelength;
michael@0:         while (count > 0) {
michael@0:             int32_t ce = getCE(strsrch, ucol_previous(coleiter, status));
michael@0:             // status checked below, note that if status is a failure
michael@0:             // ucol_previous returns UCOL_NULLORDER
michael@0:             if (ce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (expandflag && count == 0 &&
michael@0:                 getColElemIterOffset(coleiter, FALSE) != temp) {
michael@0:                 *end = temp;
michael@0:                 temp  = ucol_getOffset(coleiter);
michael@0:             }
michael@0:             if (count == patterncelength &&
michael@0:                 ce != patternce[patterncelength - 1]) {
michael@0:                 // accents may have extra starting ces, this occurs when a
michael@0:                 // pure accent pattern is matched without rearrangement
michael@0:                 int32_t    expected = patternce[patterncelength - 1];
michael@0:                 U16_BACK_1(text, 0, *end);
michael@0:                 if (getFCD(text, end, textlength) & LAST_BYTE_MASK_) {
michael@0:                     ce = getCE(strsrch, ucol_previous(coleiter, status));
michael@0:                     while (U_SUCCESS(*status) && ce != expected &&
michael@0:                            ce != UCOL_NULLORDER &&
michael@0:                            ucol_getOffset(coleiter) <= *start) {
michael@0:                         ce = getCE(strsrch, ucol_previous(coleiter, status));
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             if (U_FAILURE(*status) || ce != patternce[count - 1]) {
michael@0:                 (*start) --;
michael@0:                 *start = getPreviousBaseOffset(text, *start);
michael@0:                 return FALSE;
michael@0:             }
michael@0:             count --;
michael@0:         }
michael@0:     }
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * Checks and sets the match information if found.
michael@0: * Checks
michael@0: * <ul>
michael@0: * <li> the potential match does not repeat the previous match
michael@0: * <li> boundaries are correct
michael@0: * <li> potential match does not end in the middle of a contraction
michael@0: * <li> identical matches
michael@0: * <\ul>
michael@0: * Otherwise the offset will be shifted to the next character.
michael@0: * Internal method, status assumed to be success, caller has to check status
michael@0: * before calling this method.
michael@0: * @param strsrch string search data
michael@0: * @param textoffset offset in the collation element text. the returned value
michael@0: *        will be the truncated start offset of the match or the new start
michael@0: *        search offset.
michael@0: * @param status only error status if any
michael@0: * @return TRUE if the match is valid, FALSE otherwise
michael@0: */
michael@0: static
michael@0: inline UBool checkPreviousCanonicalMatch(UStringSearch *strsrch,
michael@0:                                          int32_t   *textoffset,
michael@0:                                          UErrorCode    *status)
michael@0: {
michael@0:     // to ensure that the start and ends are not composite characters
michael@0:     UCollationElements *coleiter = strsrch->textIter;
michael@0:     // if we have a canonical accent match
michael@0:     if ((strsrch->pattern.hasSuffixAccents &&
michael@0:         strsrch->canonicalSuffixAccents[0]) ||
michael@0:         (strsrch->pattern.hasPrefixAccents &&
michael@0:         strsrch->canonicalPrefixAccents[0])) {
michael@0:         strsrch->search->matchedIndex  = *textoffset;
michael@0:         strsrch->search->matchedLength =
michael@0:             getNextUStringSearchBaseOffset(strsrch,
michael@0:                                       getColElemIterOffset(coleiter, FALSE))
michael@0:             - *textoffset;
michael@0:         return TRUE;
michael@0:     }
michael@0: 
michael@0:     int32_t end = ucol_getOffset(coleiter);
michael@0:     if (!checkPreviousCanonicalContractionMatch(strsrch, textoffset, &end,
michael@0:                                                 status) ||
michael@0:          U_FAILURE(*status)) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     end = getNextUStringSearchBaseOffset(strsrch, end);
michael@0:     // this totally matches, however we need to check if it is repeating
michael@0:     if (checkRepeatedMatch(strsrch, *textoffset, end) ||
michael@0:         !isBreakUnit(strsrch, *textoffset, end) ||
michael@0:         !checkIdentical(strsrch, *textoffset, end)) {
michael@0:         (*textoffset) --;
michael@0:         *textoffset = getPreviousBaseOffset(strsrch->search->text,
michael@0:                                             *textoffset);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     strsrch->search->matchedIndex  = *textoffset;
michael@0:     strsrch->search->matchedLength = end - *textoffset;
michael@0:     return TRUE;
michael@0: }
michael@0: #endif // #if BOYER_MOORE
michael@0: 
michael@0: // constructors and destructor -------------------------------------------
michael@0: 
michael@0: U_CAPI UStringSearch * U_EXPORT2 usearch_open(const UChar *pattern,
michael@0:                                           int32_t         patternlength,
michael@0:                                     const UChar          *text,
michael@0:                                           int32_t         textlength,
michael@0:                                     const char           *locale,
michael@0:                                           UBreakIterator *breakiter,
michael@0:                                           UErrorCode     *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         return NULL;
michael@0:     }
michael@0: #if UCONFIG_NO_BREAK_ITERATION
michael@0:     if (breakiter != NULL) {
michael@0:         *status = U_UNSUPPORTED_ERROR;
michael@0:         return NULL;
michael@0:     }
michael@0: #endif
michael@0:     if (locale) {
michael@0:         // ucol_open internally checks for status
michael@0:         UCollator     *collator = ucol_open(locale, status);
michael@0:         // pattern, text checks are done in usearch_openFromCollator
michael@0:         UStringSearch *result   = usearch_openFromCollator(pattern,
michael@0:                                               patternlength, text, textlength,
michael@0:                                               collator, breakiter, status);
michael@0: 
michael@0:         if (result == NULL || U_FAILURE(*status)) {
michael@0:             if (collator) {
michael@0:                 ucol_close(collator);
michael@0:             }
michael@0:             return NULL;
michael@0:         }
michael@0:         else {
michael@0:             result->ownCollator = TRUE;
michael@0:         }
michael@0:         return result;
michael@0:     }
michael@0:     *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: U_CAPI UStringSearch * U_EXPORT2 usearch_openFromCollator(
michael@0:                                   const UChar          *pattern,
michael@0:                                         int32_t         patternlength,
michael@0:                                   const UChar          *text,
michael@0:                                         int32_t         textlength,
michael@0:                                   const UCollator      *collator,
michael@0:                                         UBreakIterator *breakiter,
michael@0:                                         UErrorCode     *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         return NULL;
michael@0:     }
michael@0: #if UCONFIG_NO_BREAK_ITERATION
michael@0:     if (breakiter != NULL) {
michael@0:         *status = U_UNSUPPORTED_ERROR;
michael@0:         return NULL;
michael@0:     }
michael@0: #endif
michael@0:     if (pattern == NULL || text == NULL || collator == NULL) {
michael@0:         *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     // string search does not really work when numeric collation is turned on
michael@0:     if(ucol_getAttribute(collator, UCOL_NUMERIC_COLLATION, status) == UCOL_ON) {
michael@0:         *status = U_UNSUPPORTED_ERROR;
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     if (U_SUCCESS(*status)) {
michael@0:         initializeFCD(status);
michael@0:         if (U_FAILURE(*status)) {
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         UStringSearch *result;
michael@0:         if (textlength == -1) {
michael@0:             textlength = u_strlen(text);
michael@0:         }
michael@0:         if (patternlength == -1) {
michael@0:             patternlength = u_strlen(pattern);
michael@0:         }
michael@0:         if (textlength <= 0 || patternlength <= 0) {
michael@0:             *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         result = (UStringSearch *)uprv_malloc(sizeof(UStringSearch));
michael@0:         if (result == NULL) {
michael@0:             *status = U_MEMORY_ALLOCATION_ERROR;
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         result->collator    = collator;
michael@0:         result->strength    = ucol_getStrength(collator);
michael@0:         result->ceMask      = getMask(result->strength);
michael@0:         result->toShift     =
michael@0:              ucol_getAttribute(collator, UCOL_ALTERNATE_HANDLING, status) ==
michael@0:                                                             UCOL_SHIFTED;
michael@0:         result->variableTop = ucol_getVariableTop(collator, status);
michael@0: 
michael@0:         result->nfd         = Normalizer2Factory::getNFDInstance(*status);
michael@0: 
michael@0:         if (U_FAILURE(*status)) {
michael@0:             uprv_free(result);
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         result->search             = (USearch *)uprv_malloc(sizeof(USearch));
michael@0:         if (result->search == NULL) {
michael@0:             *status = U_MEMORY_ALLOCATION_ERROR;
michael@0:             uprv_free(result);
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         result->search->text       = text;
michael@0:         result->search->textLength = textlength;
michael@0: 
michael@0:         result->pattern.text       = pattern;
michael@0:         result->pattern.textLength = patternlength;
michael@0:         result->pattern.CE         = NULL;
michael@0:         result->pattern.PCE        = NULL;
michael@0: 
michael@0:         result->search->breakIter  = breakiter;
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:         result->search->internalBreakIter = ubrk_open(UBRK_CHARACTER, ucol_getLocaleByType(result->collator, ULOC_VALID_LOCALE, status), text, textlength, status);
michael@0:         if (breakiter) {
michael@0:             ubrk_setText(breakiter, text, textlength, status);
michael@0:         }
michael@0: #endif
michael@0: 
michael@0:         result->ownCollator           = FALSE;
michael@0:         result->search->matchedLength = 0;
michael@0:         result->search->matchedIndex  = USEARCH_DONE;
michael@0:         result->utilIter              = NULL;
michael@0:         result->textIter              = ucol_openElements(collator, text,
michael@0:                                                           textlength, status);
michael@0:         if (U_FAILURE(*status)) {
michael@0:             usearch_close(result);
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         result->search->isOverlap          = FALSE;
michael@0:         result->search->isCanonicalMatch   = FALSE;
michael@0:         result->search->elementComparisonType = 0;
michael@0:         result->search->isForwardSearching = TRUE;
michael@0:         result->search->reset              = TRUE;
michael@0: 
michael@0:         initialize(result, status);
michael@0: 
michael@0:         if (U_FAILURE(*status)) {
michael@0:             usearch_close(result);
michael@0:             return NULL;
michael@0:         }
michael@0: 
michael@0:         return result;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_close(UStringSearch *strsrch)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         if (strsrch->pattern.CE != strsrch->pattern.CEBuffer &&
michael@0:             strsrch->pattern.CE) {
michael@0:             uprv_free(strsrch->pattern.CE);
michael@0:         }
michael@0: 
michael@0:         if (strsrch->pattern.PCE != NULL &&
michael@0:             strsrch->pattern.PCE != strsrch->pattern.PCEBuffer) {
michael@0:             uprv_free(strsrch->pattern.PCE);
michael@0:         }
michael@0: 
michael@0:         ucol_closeElements(strsrch->textIter);
michael@0:         ucol_closeElements(strsrch->utilIter);
michael@0: 
michael@0:         if (strsrch->ownCollator && strsrch->collator) {
michael@0:             ucol_close((UCollator *)strsrch->collator);
michael@0:         }
michael@0: 
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:         if (strsrch->search->internalBreakIter) {
michael@0:             ubrk_close(strsrch->search->internalBreakIter);
michael@0:         }
michael@0: #endif
michael@0: 
michael@0:         uprv_free(strsrch->search);
michael@0:         uprv_free(strsrch);
michael@0:     }
michael@0: }
michael@0: 
michael@0: // set and get methods --------------------------------------------------
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_setOffset(UStringSearch *strsrch,
michael@0:                                         int32_t    position,
michael@0:                                         UErrorCode    *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status) && strsrch) {
michael@0:         if (isOutOfBounds(strsrch->search->textLength, position)) {
michael@0:             *status = U_INDEX_OUTOFBOUNDS_ERROR;
michael@0:         }
michael@0:         else {
michael@0:             setColEIterOffset(strsrch->textIter, position);
michael@0:         }
michael@0:         strsrch->search->matchedIndex  = USEARCH_DONE;
michael@0:         strsrch->search->matchedLength = 0;
michael@0:         strsrch->search->reset         = FALSE;
michael@0:     }
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_getOffset(const UStringSearch *strsrch)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         int32_t result = ucol_getOffset(strsrch->textIter);
michael@0:         if (isOutOfBounds(strsrch->search->textLength, result)) {
michael@0:             return USEARCH_DONE;
michael@0:         }
michael@0:         return result;
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_setAttribute(UStringSearch *strsrch,
michael@0:                                  USearchAttribute attribute,
michael@0:                                  USearchAttributeValue value,
michael@0:                                  UErrorCode *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status) && strsrch) {
michael@0:         switch (attribute)
michael@0:         {
michael@0:         case USEARCH_OVERLAP :
michael@0:             strsrch->search->isOverlap = (value == USEARCH_ON ? TRUE : FALSE);
michael@0:             break;
michael@0:         case USEARCH_CANONICAL_MATCH :
michael@0:             strsrch->search->isCanonicalMatch = (value == USEARCH_ON ? TRUE :
michael@0:                                                                       FALSE);
michael@0:             break;
michael@0:         case USEARCH_ELEMENT_COMPARISON :
michael@0:             if (value == USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD || value == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD) {
michael@0:                 strsrch->search->elementComparisonType = (int16_t)value;
michael@0:             } else {
michael@0:                 strsrch->search->elementComparisonType = 0;
michael@0:             }
michael@0:             break;
michael@0:         case USEARCH_ATTRIBUTE_COUNT :
michael@0:         default:
michael@0:             *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:         }
michael@0:     }
michael@0:     if (value == USEARCH_ATTRIBUTE_VALUE_COUNT) {
michael@0:         *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:     }
michael@0: }
michael@0: 
michael@0: U_CAPI USearchAttributeValue U_EXPORT2 usearch_getAttribute(
michael@0:                                                 const UStringSearch *strsrch,
michael@0:                                                 USearchAttribute attribute)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         switch (attribute) {
michael@0:         case USEARCH_OVERLAP :
michael@0:             return (strsrch->search->isOverlap == TRUE ? USEARCH_ON :
michael@0:                                                         USEARCH_OFF);
michael@0:         case USEARCH_CANONICAL_MATCH :
michael@0:             return (strsrch->search->isCanonicalMatch == TRUE ? USEARCH_ON :
michael@0:                                                                USEARCH_OFF);
michael@0:         case USEARCH_ELEMENT_COMPARISON :
michael@0:             {
michael@0:                 int16_t value = strsrch->search->elementComparisonType;
michael@0:                 if (value == USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD || value == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD) {
michael@0:                     return (USearchAttributeValue)value;
michael@0:                 } else {
michael@0:                     return USEARCH_STANDARD_ELEMENT_COMPARISON;
michael@0:                 }
michael@0:             }
michael@0:         case USEARCH_ATTRIBUTE_COUNT :
michael@0:             return USEARCH_DEFAULT;
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DEFAULT;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_getMatchedStart(
michael@0:                                                 const UStringSearch *strsrch)
michael@0: {
michael@0:     if (strsrch == NULL) {
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0:     return strsrch->search->matchedIndex;
michael@0: }
michael@0: 
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_getMatchedText(const UStringSearch *strsrch,
michael@0:                                             UChar         *result,
michael@0:                                             int32_t        resultCapacity,
michael@0:                                             UErrorCode    *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0:     if (strsrch == NULL || resultCapacity < 0 || (resultCapacity > 0 &&
michael@0:         result == NULL)) {
michael@0:         *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0: 
michael@0:     int32_t     copylength = strsrch->search->matchedLength;
michael@0:     int32_t copyindex  = strsrch->search->matchedIndex;
michael@0:     if (copyindex == USEARCH_DONE) {
michael@0:         u_terminateUChars(result, resultCapacity, 0, status);
michael@0:         return USEARCH_DONE;
michael@0:     }
michael@0: 
michael@0:     if (resultCapacity < copylength) {
michael@0:         copylength = resultCapacity;
michael@0:     }
michael@0:     if (copylength > 0) {
michael@0:         uprv_memcpy(result, strsrch->search->text + copyindex,
michael@0:                     copylength * sizeof(UChar));
michael@0:     }
michael@0:     return u_terminateUChars(result, resultCapacity,
michael@0:                              strsrch->search->matchedLength, status);
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_getMatchedLength(
michael@0:                                               const UStringSearch *strsrch)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         return strsrch->search->matchedLength;
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_setBreakIterator(UStringSearch  *strsrch,
michael@0:                                                UBreakIterator *breakiter,
michael@0:                                                UErrorCode     *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status) && strsrch) {
michael@0:         strsrch->search->breakIter = breakiter;
michael@0:         if (breakiter) {
michael@0:             ubrk_setText(breakiter, strsrch->search->text,
michael@0:                          strsrch->search->textLength, status);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: U_CAPI const UBreakIterator* U_EXPORT2
michael@0: usearch_getBreakIterator(const UStringSearch *strsrch)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         return strsrch->search->breakIter;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: #endif
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_setText(      UStringSearch *strsrch,
michael@0:                                       const UChar         *text,
michael@0:                                             int32_t        textlength,
michael@0:                                             UErrorCode    *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status)) {
michael@0:         if (strsrch == NULL || text == NULL || textlength < -1 ||
michael@0:             textlength == 0) {
michael@0:             *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:         }
michael@0:         else {
michael@0:             if (textlength == -1) {
michael@0:                 textlength = u_strlen(text);
michael@0:             }
michael@0:             strsrch->search->text       = text;
michael@0:             strsrch->search->textLength = textlength;
michael@0:             ucol_setText(strsrch->textIter, text, textlength, status);
michael@0:             strsrch->search->matchedIndex  = USEARCH_DONE;
michael@0:             strsrch->search->matchedLength = 0;
michael@0:             strsrch->search->reset         = TRUE;
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:             if (strsrch->search->breakIter != NULL) {
michael@0:                 ubrk_setText(strsrch->search->breakIter, text,
michael@0:                              textlength, status);
michael@0:             }
michael@0:             ubrk_setText(strsrch->search->internalBreakIter, text, textlength, status);
michael@0: #endif
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: U_CAPI const UChar * U_EXPORT2 usearch_getText(const UStringSearch *strsrch,
michael@0:                                                      int32_t       *length)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         *length = strsrch->search->textLength;
michael@0:         return strsrch->search->text;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_setCollator(      UStringSearch *strsrch,
michael@0:                                           const UCollator     *collator,
michael@0:                                                 UErrorCode    *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status)) {
michael@0:         if (collator == NULL) {
michael@0:             *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:             return;
michael@0:         }
michael@0: 
michael@0:         if (strsrch) {
michael@0:             if (strsrch->ownCollator && (strsrch->collator != collator)) {
michael@0:                 ucol_close((UCollator *)strsrch->collator);
michael@0:                 strsrch->ownCollator = FALSE;
michael@0:             }
michael@0:             strsrch->collator    = collator;
michael@0:             strsrch->strength    = ucol_getStrength(collator);
michael@0:             strsrch->ceMask      = getMask(strsrch->strength);
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:             ubrk_close(strsrch->search->internalBreakIter);
michael@0:             strsrch->search->internalBreakIter = ubrk_open(UBRK_CHARACTER, ucol_getLocaleByType(collator, ULOC_VALID_LOCALE, status),
michael@0:                                                      strsrch->search->text, strsrch->search->textLength, status);
michael@0: #endif
michael@0:             // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT
michael@0:             strsrch->toShift     =
michael@0:                ucol_getAttribute(collator, UCOL_ALTERNATE_HANDLING, status) ==
michael@0:                                                                 UCOL_SHIFTED;
michael@0:             // if status is a failure, ucol_getVariableTop returns 0
michael@0:             strsrch->variableTop = ucol_getVariableTop(collator, status);
michael@0:             if (U_SUCCESS(*status)) {
michael@0:                 initialize(strsrch, status);
michael@0:                 if (U_SUCCESS(*status)) {
michael@0:                     /* free offset buffer to avoid memory leak before initializing. */
michael@0:                     ucol_freeOffsetBuffer(&(strsrch->textIter->iteratordata_));
michael@0:                     uprv_init_collIterate(collator, strsrch->search->text,
michael@0:                                           strsrch->search->textLength,
michael@0:                                           &(strsrch->textIter->iteratordata_),
michael@0:                                           status);
michael@0:                     strsrch->utilIter->iteratordata_.coll = collator;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // **** are these calls needed?
michael@0:         // **** we call uprv_init_pce in initializePatternPCETable
michael@0:         // **** and the CEBuffer constructor...
michael@0: #if 0
michael@0:         uprv_init_pce(strsrch->textIter);
michael@0:         uprv_init_pce(strsrch->utilIter);
michael@0: #endif
michael@0:     }
michael@0: }
michael@0: 
michael@0: U_CAPI UCollator * U_EXPORT2 usearch_getCollator(const UStringSearch *strsrch)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         return (UCollator *)strsrch->collator;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_setPattern(      UStringSearch *strsrch,
michael@0:                                          const UChar         *pattern,
michael@0:                                                int32_t        patternlength,
michael@0:                                                UErrorCode    *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status)) {
michael@0:         if (strsrch == NULL || pattern == NULL) {
michael@0:             *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:         }
michael@0:         else {
michael@0:             if (patternlength == -1) {
michael@0:                 patternlength = u_strlen(pattern);
michael@0:             }
michael@0:             if (patternlength == 0) {
michael@0:                 *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:                 return;
michael@0:             }
michael@0:             strsrch->pattern.text       = pattern;
michael@0:             strsrch->pattern.textLength = patternlength;
michael@0:             initialize(strsrch, status);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: U_CAPI const UChar* U_EXPORT2
michael@0: usearch_getPattern(const UStringSearch *strsrch,
michael@0:                    int32_t       *length)
michael@0: {
michael@0:     if (strsrch) {
michael@0:         *length = strsrch->pattern.textLength;
michael@0:         return strsrch->pattern.text;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: // miscellanous methods --------------------------------------------------
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_first(UStringSearch *strsrch,
michael@0:                                            UErrorCode    *status)
michael@0: {
michael@0:     if (strsrch && U_SUCCESS(*status)) {
michael@0:         strsrch->search->isForwardSearching = TRUE;
michael@0:         usearch_setOffset(strsrch, 0, status);
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             return usearch_next(strsrch, status);
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_following(UStringSearch *strsrch,
michael@0:                                                int32_t    position,
michael@0:                                                UErrorCode    *status)
michael@0: {
michael@0:     if (strsrch && U_SUCCESS(*status)) {
michael@0:         strsrch->search->isForwardSearching = TRUE;
michael@0:         // position checked in usearch_setOffset
michael@0:         usearch_setOffset(strsrch, position, status);
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             return usearch_next(strsrch, status);
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_last(UStringSearch *strsrch,
michael@0:                                           UErrorCode    *status)
michael@0: {
michael@0:     if (strsrch && U_SUCCESS(*status)) {
michael@0:         strsrch->search->isForwardSearching = FALSE;
michael@0:         usearch_setOffset(strsrch, strsrch->search->textLength, status);
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             return usearch_previous(strsrch, status);
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_preceding(UStringSearch *strsrch,
michael@0:                                                int32_t    position,
michael@0:                                                UErrorCode    *status)
michael@0: {
michael@0:     if (strsrch && U_SUCCESS(*status)) {
michael@0:         strsrch->search->isForwardSearching = FALSE;
michael@0:         // position checked in usearch_setOffset
michael@0:         usearch_setOffset(strsrch, position, status);
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             return usearch_previous(strsrch, status);
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: /**
michael@0: * If a direction switch is required, we'll count the number of ces till the
michael@0: * beginning of the collation element iterator and iterate forwards that
michael@0: * number of times. This is so that we get to the correct point within the
michael@0: * string to continue the search in. Imagine when we are in the middle of the
michael@0: * normalization buffer when the change in direction is request. arrrgghh....
michael@0: * After searching the offset within the collation element iterator will be
michael@0: * shifted to the start of the match. If a match is not found, the offset would
michael@0: * have been set to the end of the text string in the collation element
michael@0: * iterator.
michael@0: * Okay, here's my take on normalization buffer. The only time when there can
michael@0: * be 2 matches within the same normalization is when the pattern is consists
michael@0: * of all accents. But since the offset returned is from the text string, we
michael@0: * should not confuse the caller by returning the second match within the
michael@0: * same normalization buffer. If we do, the 2 results will have the same match
michael@0: * offsets, and that'll be confusing. I'll return the next match that doesn't
michael@0: * fall within the same normalization buffer. Note this does not affect the
michael@0: * results of matches spanning the text and the normalization buffer.
michael@0: * The position to start searching is taken from the collation element
michael@0: * iterator. Callers of this API would have to set the offset in the collation
michael@0: * element iterator before using this method.
michael@0: */
michael@0: U_CAPI int32_t U_EXPORT2 usearch_next(UStringSearch *strsrch,
michael@0:                                           UErrorCode    *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status) && strsrch) {
michael@0:         // note offset is either equivalent to the start of the previous match
michael@0:         // or is set by the user
michael@0:         int32_t      offset       = usearch_getOffset(strsrch);
michael@0:         USearch     *search       = strsrch->search;
michael@0:         search->reset             = FALSE;
michael@0:         int32_t      textlength   = search->textLength;
michael@0:         if (search->isForwardSearching) {
michael@0: #if BOYER_MOORE
michael@0:             if (offset == textlength
michael@0:                 || (!search->isOverlap &&
michael@0:                     (offset + strsrch->pattern.defaultShiftSize > textlength ||
michael@0:                     (search->matchedIndex != USEARCH_DONE &&
michael@0:                      offset + search->matchedLength >= textlength)))) {
michael@0:                 // not enough characters to match
michael@0:                 setMatchNotFound(strsrch);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0: #else
michael@0:             if (offset == textlength ||
michael@0:                 (! search->isOverlap &&
michael@0:                 (search->matchedIndex != USEARCH_DONE &&
michael@0:                 offset + search->matchedLength > textlength))) {
michael@0:                     // not enough characters to match
michael@0:                     setMatchNotFound(strsrch);
michael@0:                     return USEARCH_DONE;
michael@0:             }
michael@0: #endif
michael@0:         }
michael@0:         else {
michael@0:             // switching direction.
michael@0:             // if matchedIndex == USEARCH_DONE, it means that either a
michael@0:             // setOffset has been called or that previous ran off the text
michael@0:             // string. the iterator would have been set to offset 0 if a
michael@0:             // match is not found.
michael@0:             search->isForwardSearching = TRUE;
michael@0:             if (search->matchedIndex != USEARCH_DONE) {
michael@0:                 // there's no need to set the collation element iterator
michael@0:                 // the next call to next will set the offset.
michael@0:                 return search->matchedIndex;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             if (strsrch->pattern.CELength == 0) {
michael@0:                 if (search->matchedIndex == USEARCH_DONE) {
michael@0:                     search->matchedIndex = offset;
michael@0:                 }
michael@0:                 else { // moves by codepoints
michael@0:                     U16_FWD_1(search->text, search->matchedIndex, textlength);
michael@0:                 }
michael@0: 
michael@0:                 search->matchedLength = 0;
michael@0:                 setColEIterOffset(strsrch->textIter, search->matchedIndex);
michael@0:                 // status checked below
michael@0:                 if (search->matchedIndex == textlength) {
michael@0:                     search->matchedIndex = USEARCH_DONE;
michael@0:                 }
michael@0:             }
michael@0:             else {
michael@0:                 if (search->matchedLength > 0) {
michael@0:                     // if matchlength is 0 we are at the start of the iteration
michael@0:                     if (search->isOverlap) {
michael@0:                         ucol_setOffset(strsrch->textIter, offset + 1, status);
michael@0:                     }
michael@0:                     else {
michael@0:                         ucol_setOffset(strsrch->textIter,
michael@0:                                        offset + search->matchedLength, status);
michael@0:                     }
michael@0:                 }
michael@0:                 else {
michael@0:                     // for boundary check purposes. this will ensure that the
michael@0:                     // next match will not preceed the current offset
michael@0:                     // note search->matchedIndex will always be set to something
michael@0:                     // in the code
michael@0:                     search->matchedIndex = offset - 1;
michael@0:                 }
michael@0: 
michael@0:                 if (search->isCanonicalMatch) {
michael@0:                     // can't use exact here since extra accents are allowed.
michael@0:                     usearch_handleNextCanonical(strsrch, status);
michael@0:                 }
michael@0:                 else {
michael@0:                     usearch_handleNextExact(strsrch, status);
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0: 
michael@0: #if !BOYER_MOORE
michael@0:             if (search->matchedIndex == USEARCH_DONE) {
michael@0:                 ucol_setOffset(strsrch->textIter, search->textLength, status);
michael@0:             } else {
michael@0:                 ucol_setOffset(strsrch->textIter, search->matchedIndex, status);
michael@0:             }
michael@0: #endif
michael@0: 
michael@0:             return search->matchedIndex;
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: U_CAPI int32_t U_EXPORT2 usearch_previous(UStringSearch *strsrch,
michael@0:                                               UErrorCode *status)
michael@0: {
michael@0:     if (U_SUCCESS(*status) && strsrch) {
michael@0:         int32_t offset;
michael@0:         USearch *search = strsrch->search;
michael@0:         if (search->reset) {
michael@0:             offset                     = search->textLength;
michael@0:             search->isForwardSearching = FALSE;
michael@0:             search->reset              = FALSE;
michael@0:             setColEIterOffset(strsrch->textIter, offset);
michael@0:         }
michael@0:         else {
michael@0:             offset = usearch_getOffset(strsrch);
michael@0:         }
michael@0: 
michael@0:         int32_t matchedindex = search->matchedIndex;
michael@0:         if (search->isForwardSearching == TRUE) {
michael@0:             // switching direction.
michael@0:             // if matchedIndex == USEARCH_DONE, it means that either a
michael@0:             // setOffset has been called or that next ran off the text
michael@0:             // string. the iterator would have been set to offset textLength if
michael@0:             // a match is not found.
michael@0:             search->isForwardSearching = FALSE;
michael@0:             if (matchedindex != USEARCH_DONE) {
michael@0:                 return matchedindex;
michael@0:             }
michael@0:         }
michael@0:         else {
michael@0: #if BOYER_MOORE
michael@0:             if (offset == 0 || matchedindex == 0 ||
michael@0:                 (!search->isOverlap &&
michael@0:                     (offset < strsrch->pattern.defaultShiftSize ||
michael@0:                     (matchedindex != USEARCH_DONE &&
michael@0:                     matchedindex < strsrch->pattern.defaultShiftSize)))) {
michael@0:                 // not enough characters to match
michael@0:                 setMatchNotFound(strsrch);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0: #else
michael@0:             // Could check pattern length, but the
michael@0:             // linear search will do the right thing
michael@0:             if (offset == 0 || matchedindex == 0) {
michael@0:                 setMatchNotFound(strsrch);
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0: #endif
michael@0:         }
michael@0: 
michael@0:         if (U_SUCCESS(*status)) {
michael@0:             if (strsrch->pattern.CELength == 0) {
michael@0:                 search->matchedIndex =
michael@0:                       (matchedindex == USEARCH_DONE ? offset : matchedindex);
michael@0:                 if (search->matchedIndex == 0) {
michael@0:                     setMatchNotFound(strsrch);
michael@0:                     // status checked below
michael@0:                 }
michael@0:                 else { // move by codepoints
michael@0:                     U16_BACK_1(search->text, 0, search->matchedIndex);
michael@0:                     setColEIterOffset(strsrch->textIter, search->matchedIndex);
michael@0:                     // status checked below
michael@0:                     search->matchedLength = 0;
michael@0:                 }
michael@0:             }
michael@0:             else {
michael@0:                 if (strsrch->search->isCanonicalMatch) {
michael@0:                     // can't use exact here since extra accents are allowed.
michael@0:                     usearch_handlePreviousCanonical(strsrch, status);
michael@0:                     // status checked below
michael@0:                 }
michael@0:                 else {
michael@0:                     usearch_handlePreviousExact(strsrch, status);
michael@0:                     // status checked below
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 return USEARCH_DONE;
michael@0:             }
michael@0: 
michael@0:             return search->matchedIndex;
michael@0:         }
michael@0:     }
michael@0:     return USEARCH_DONE;
michael@0: }
michael@0: 
michael@0: 
michael@0: 
michael@0: U_CAPI void U_EXPORT2 usearch_reset(UStringSearch *strsrch)
michael@0: {
michael@0:     /*
michael@0:     reset is setting the attributes that are already in
michael@0:     string search, hence all attributes in the collator should
michael@0:     be retrieved without any problems
michael@0:     */
michael@0:     if (strsrch) {
michael@0:         UErrorCode status            = U_ZERO_ERROR;
michael@0:         UBool      sameCollAttribute = TRUE;
michael@0:         uint32_t   ceMask;
michael@0:         UBool      shift;
michael@0:         uint32_t   varTop;
michael@0: 
michael@0:         // **** hack to deal w/ how processed CEs encode quaternary ****
michael@0:         UCollationStrength newStrength = ucol_getStrength(strsrch->collator);
michael@0:         if ((strsrch->strength < UCOL_QUATERNARY && newStrength >= UCOL_QUATERNARY) ||
michael@0:             (strsrch->strength >= UCOL_QUATERNARY && newStrength < UCOL_QUATERNARY)) {
michael@0:                 sameCollAttribute = FALSE;
michael@0:         }
michael@0: 
michael@0:         strsrch->strength    = ucol_getStrength(strsrch->collator);
michael@0:         ceMask = getMask(strsrch->strength);
michael@0:         if (strsrch->ceMask != ceMask) {
michael@0:             strsrch->ceMask = ceMask;
michael@0:             sameCollAttribute = FALSE;
michael@0:         }
michael@0: 
michael@0:         // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT
michael@0:         shift = ucol_getAttribute(strsrch->collator, UCOL_ALTERNATE_HANDLING,
michael@0:                                   &status) == UCOL_SHIFTED;
michael@0:         if (strsrch->toShift != shift) {
michael@0:             strsrch->toShift  = shift;
michael@0:             sameCollAttribute = FALSE;
michael@0:         }
michael@0: 
michael@0:         // if status is a failure, ucol_getVariableTop returns 0
michael@0:         varTop = ucol_getVariableTop(strsrch->collator, &status);
michael@0:         if (strsrch->variableTop != varTop) {
michael@0:             strsrch->variableTop = varTop;
michael@0:             sameCollAttribute    = FALSE;
michael@0:         }
michael@0:         if (!sameCollAttribute) {
michael@0:             initialize(strsrch, &status);
michael@0:         }
michael@0:         /* free offset buffer to avoid memory leak before initializing. */
michael@0:         ucol_freeOffsetBuffer(&(strsrch->textIter->iteratordata_));
michael@0:         uprv_init_collIterate(strsrch->collator, strsrch->search->text,
michael@0:                               strsrch->search->textLength,
michael@0:                               &(strsrch->textIter->iteratordata_),
michael@0:                               &status);
michael@0:         strsrch->search->matchedLength      = 0;
michael@0:         strsrch->search->matchedIndex       = USEARCH_DONE;
michael@0:         strsrch->search->isOverlap          = FALSE;
michael@0:         strsrch->search->isCanonicalMatch   = FALSE;
michael@0:         strsrch->search->elementComparisonType = 0;
michael@0:         strsrch->search->isForwardSearching = TRUE;
michael@0:         strsrch->search->reset              = TRUE;
michael@0:     }
michael@0: }
michael@0: 
michael@0: //
michael@0: //  CEI  Collation Element + source text index.
michael@0: //       These structs are kept in the circular buffer.
michael@0: //
michael@0: struct  CEI {
michael@0:     int64_t ce;
michael@0:     int32_t lowIndex;
michael@0:     int32_t highIndex;
michael@0: };
michael@0: 
michael@0: U_NAMESPACE_BEGIN
michael@0: 
michael@0: 
michael@0: //
michael@0: //  CEBuffer   A circular buffer of CEs from the text being searched.
michael@0: //
michael@0: #define   DEFAULT_CEBUFFER_SIZE 96
michael@0: #define   CEBUFFER_EXTRA 32
michael@0: // Some typical max values to make buffer size more reasonable for asymmetric search.
michael@0: // #8694 is for a better long-term solution to allocation of this buffer.
michael@0: #define   MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L 8
michael@0: #define   MAX_TARGET_IGNORABLES_PER_PAT_OTHER 3
michael@0: #define   MIGHT_BE_JAMO_L(c) ((c >= 0x1100 && c <= 0x115E) || (c >= 0x3131 && c <= 0x314E) || (c >= 0x3165 && c <= 0x3186))
michael@0: struct CEBuffer {
michael@0:     CEI                  defBuf[DEFAULT_CEBUFFER_SIZE];
michael@0:     CEI                 *buf;
michael@0:     int32_t              bufSize;
michael@0:     int32_t              firstIx;
michael@0:     int32_t              limitIx;
michael@0:     UCollationElements  *ceIter;
michael@0:     UStringSearch       *strSearch;
michael@0: 
michael@0: 
michael@0: 
michael@0:                CEBuffer(UStringSearch *ss, UErrorCode *status);
michael@0:                ~CEBuffer();
michael@0:    const CEI   *get(int32_t index);
michael@0:    const CEI   *getPrevious(int32_t index);
michael@0: };
michael@0: 
michael@0: 
michael@0: CEBuffer::CEBuffer(UStringSearch *ss, UErrorCode *status) {
michael@0:     buf = defBuf;
michael@0:     strSearch = ss;
michael@0:     bufSize = ss->pattern.PCELength + CEBUFFER_EXTRA;
michael@0:     if (ss->search->elementComparisonType != 0) {
michael@0:         const UChar * patText = ss->pattern.text;
michael@0:         if (patText) {
michael@0:             const UChar * patTextLimit = patText + ss->pattern.textLength;
michael@0:             while ( patText < patTextLimit ) {
michael@0:                 UChar c = *patText++;
michael@0:                 if (MIGHT_BE_JAMO_L(c)) {
michael@0:                     bufSize += MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L;
michael@0:                 } else {
michael@0:                     // No check for surrogates, we might allocate slightly more buffer than necessary.
michael@0:                     bufSize += MAX_TARGET_IGNORABLES_PER_PAT_OTHER;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     ceIter    = ss->textIter;
michael@0:     firstIx = 0;
michael@0:     limitIx = 0;
michael@0: 
michael@0:     uprv_init_pce(ceIter);
michael@0: 
michael@0:     if (bufSize>DEFAULT_CEBUFFER_SIZE) {
michael@0:         buf = (CEI *)uprv_malloc(bufSize * sizeof(CEI));
michael@0:         if (buf == NULL) {
michael@0:             *status = U_MEMORY_ALLOCATION_ERROR;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: // TODO: add a reset or init function so that allocated
michael@0: //       buffers can be retained & reused.
michael@0: 
michael@0: CEBuffer::~CEBuffer() {
michael@0:     if (buf != defBuf) {
michael@0:         uprv_free(buf);
michael@0:     }
michael@0: }
michael@0: 
michael@0: 
michael@0: // Get the CE with the specified index.
michael@0: //   Index must be in the range
michael@0: //          n-history_size < index < n+1
michael@0: //   where n is the largest index to have been fetched by some previous call to this function.
michael@0: //   The CE value will be UCOL__PROCESSED_NULLORDER at end of input.
michael@0: //
michael@0: const CEI *CEBuffer::get(int32_t index) {
michael@0:     int i = index % bufSize;
michael@0: 
michael@0:     if (index>=firstIx && index<limitIx) {
michael@0:         // The request was for an entry already in our buffer.
michael@0:         //  Just return it.
michael@0:         return &buf[i];
michael@0:     }
michael@0: 
michael@0:     // Caller is requesting a new, never accessed before, CE.
michael@0:     //   Verify that it is the next one in sequence, which is all
michael@0:     //   that is allowed.
michael@0:     if (index != limitIx) {
michael@0:         U_ASSERT(FALSE);
michael@0: 
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     // Manage the circular CE buffer indexing
michael@0:     limitIx++;
michael@0: 
michael@0:     if (limitIx - firstIx >= bufSize) {
michael@0:         // The buffer is full, knock out the lowest-indexed entry.
michael@0:         firstIx++;
michael@0:     }
michael@0: 
michael@0:     UErrorCode status = U_ZERO_ERROR;
michael@0: 
michael@0:     buf[i].ce = ucol_nextProcessed(ceIter, &buf[i].lowIndex, &buf[i].highIndex, &status);
michael@0: 
michael@0:     return &buf[i];
michael@0: }
michael@0: 
michael@0: // Get the CE with the specified index.
michael@0: //   Index must be in the range
michael@0: //          n-history_size < index < n+1
michael@0: //   where n is the largest index to have been fetched by some previous call to this function.
michael@0: //   The CE value will be UCOL__PROCESSED_NULLORDER at end of input.
michael@0: //
michael@0: const CEI *CEBuffer::getPrevious(int32_t index) {
michael@0:     int i = index % bufSize;
michael@0: 
michael@0:     if (index>=firstIx && index<limitIx) {
michael@0:         // The request was for an entry already in our buffer.
michael@0:         //  Just return it.
michael@0:         return &buf[i];
michael@0:     }
michael@0: 
michael@0:     // Caller is requesting a new, never accessed before, CE.
michael@0:     //   Verify that it is the next one in sequence, which is all
michael@0:     //   that is allowed.
michael@0:     if (index != limitIx) {
michael@0:         U_ASSERT(FALSE);
michael@0: 
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     // Manage the circular CE buffer indexing
michael@0:     limitIx++;
michael@0: 
michael@0:     if (limitIx - firstIx >= bufSize) {
michael@0:         // The buffer is full, knock out the lowest-indexed entry.
michael@0:         firstIx++;
michael@0:     }
michael@0: 
michael@0:     UErrorCode status = U_ZERO_ERROR;
michael@0: 
michael@0:     buf[i].ce = ucol_previousProcessed(ceIter, &buf[i].lowIndex, &buf[i].highIndex, &status);
michael@0: 
michael@0:     return &buf[i];
michael@0: }
michael@0: 
michael@0: U_NAMESPACE_END
michael@0: 
michael@0: 
michael@0: // #define USEARCH_DEBUG
michael@0: 
michael@0: #ifdef USEARCH_DEBUG
michael@0: #include <stdio.h>
michael@0: #include <stdlib.h>
michael@0: #endif
michael@0: 
michael@0: /*
michael@0:  * Find the next break boundary after startIndex. If the UStringSearch object
michael@0:  * has an external break iterator, use that. Otherwise use the internal character
michael@0:  * break iterator.
michael@0:  */
michael@0: static int32_t nextBoundaryAfter(UStringSearch *strsrch, int32_t startIndex) {
michael@0: #if 0
michael@0:     const UChar *text = strsrch->search->text;
michael@0:     int32_t textLen   = strsrch->search->textLength;
michael@0: 
michael@0:     U_ASSERT(startIndex>=0);
michael@0:     U_ASSERT(startIndex<=textLen);
michael@0: 
michael@0:     if (startIndex >= textLen) {
michael@0:         return startIndex;
michael@0:     }
michael@0: 
michael@0:     UChar32  c;
michael@0:     int32_t  i = startIndex;
michael@0:     U16_NEXT(text, i, textLen, c);
michael@0: 
michael@0:     // If we are on a control character, stop without looking for combining marks.
michael@0:     //    Control characters do not combine.
michael@0:     int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
michael@0:     if (gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR) {
michael@0:         return i;
michael@0:     }
michael@0: 
michael@0:     // The initial character was not a control, and can thus accept trailing
michael@0:     //   combining characters.  Advance over however many of them there are.
michael@0:     int32_t  indexOfLastCharChecked;
michael@0:     for (;;) {
michael@0:         indexOfLastCharChecked = i;
michael@0:         if (i>=textLen) {
michael@0:             break;
michael@0:         }
michael@0:         U16_NEXT(text, i, textLen, c);
michael@0:         gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
michael@0:         if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     return indexOfLastCharChecked;
michael@0: #elif !UCONFIG_NO_BREAK_ITERATION
michael@0:     UBreakIterator *breakiterator = strsrch->search->breakIter;
michael@0: 
michael@0:     if (breakiterator == NULL) {
michael@0:         breakiterator = strsrch->search->internalBreakIter;
michael@0:     }
michael@0: 
michael@0:     if (breakiterator != NULL) {
michael@0:         return ubrk_following(breakiterator, startIndex);
michael@0:     }
michael@0: 
michael@0:     return startIndex;
michael@0: #else
michael@0:     // **** or should we use the original code? ****
michael@0:     return startIndex;
michael@0: #endif
michael@0: 
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Returns TRUE if index is on a break boundary. If the UStringSearch
michael@0:  * has an external break iterator, test using that, otherwise test
michael@0:  * using the internal character break iterator.
michael@0:  */
michael@0: static UBool isBreakBoundary(UStringSearch *strsrch, int32_t index) {
michael@0: #if 0
michael@0:     const UChar *text = strsrch->search->text;
michael@0:     int32_t textLen   = strsrch->search->textLength;
michael@0: 
michael@0:     U_ASSERT(index>=0);
michael@0:     U_ASSERT(index<=textLen);
michael@0: 
michael@0:     if (index>=textLen || index<=0) {
michael@0:         return TRUE;
michael@0:     }
michael@0: 
michael@0:     // If the character at the current index is not a GRAPHEME_EXTEND
michael@0:     //    then we can not be within a combining sequence.
michael@0:     UChar32  c;
michael@0:     U16_GET(text, 0, index, textLen, c);
michael@0:     int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
michael@0:     if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) {
michael@0:         return TRUE;
michael@0:     }
michael@0: 
michael@0:     // We are at a combining mark.  If the preceding character is anything
michael@0:     //   except a CONTROL, CR or LF, we are in a combining sequence.
michael@0:     U16_PREV(text, 0, index, c);
michael@0:     gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
michael@0:     UBool combining =  !(gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR);
michael@0:     return !combining;
michael@0: #elif !UCONFIG_NO_BREAK_ITERATION
michael@0:     UBreakIterator *breakiterator = strsrch->search->breakIter;
michael@0: 
michael@0:     if (breakiterator == NULL) {
michael@0:         breakiterator = strsrch->search->internalBreakIter;
michael@0:     }
michael@0: 
michael@0:     return (breakiterator != NULL && ubrk_isBoundary(breakiterator, index));
michael@0: #else
michael@0:     // **** or use the original code? ****
michael@0:     return TRUE;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: #if 0
michael@0: static UBool onBreakBoundaries(const UStringSearch *strsrch, int32_t start, int32_t end)
michael@0: {
michael@0: #if !UCONFIG_NO_BREAK_ITERATION
michael@0:     UBreakIterator *breakiterator = strsrch->search->breakIter;
michael@0: 
michael@0:     if (breakiterator != NULL) {
michael@0:         int32_t startindex = ubrk_first(breakiterator);
michael@0:         int32_t endindex   = ubrk_last(breakiterator);
michael@0: 
michael@0:         // out-of-range indexes are never boundary positions
michael@0:         if (start < startindex || start > endindex ||
michael@0:             end < startindex || end > endindex) {
michael@0:             return FALSE;
michael@0:         }
michael@0: 
michael@0:         return ubrk_isBoundary(breakiterator, start) &&
michael@0:                ubrk_isBoundary(breakiterator, end);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: typedef enum {
michael@0:     U_CE_MATCH = -1,
michael@0:     U_CE_NO_MATCH = 0,
michael@0:     U_CE_SKIP_TARG,
michael@0:     U_CE_SKIP_PATN
michael@0: } UCompareCEsResult;
michael@0: #define U_CE_LEVEL2_BASE 0x00000005
michael@0: #define U_CE_LEVEL3_BASE 0x00050000
michael@0: 
michael@0: static UCompareCEsResult compareCE64s(int64_t targCE, int64_t patCE, int16_t compareType) {
michael@0:     if (targCE == patCE) {
michael@0:         return U_CE_MATCH;
michael@0:     }
michael@0:     if (compareType == 0) {
michael@0:         return U_CE_NO_MATCH;
michael@0:     }
michael@0:     
michael@0:     int64_t targCEshifted = targCE >> 32;
michael@0:     int64_t patCEshifted = patCE >> 32;
michael@0:     int64_t mask;
michael@0: 
michael@0:     mask = 0xFFFF0000;
michael@0:     int32_t targLev1 = (int32_t)(targCEshifted & mask);
michael@0:     int32_t patLev1 = (int32_t)(patCEshifted & mask);
michael@0:     if ( targLev1 != patLev1 ) {
michael@0:         if ( targLev1 == 0 ) {
michael@0:             return U_CE_SKIP_TARG;
michael@0:         }
michael@0:         if ( patLev1 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) {
michael@0:             return U_CE_SKIP_PATN;
michael@0:         }
michael@0:         return U_CE_NO_MATCH;
michael@0:     }
michael@0: 
michael@0:     mask = 0x0000FFFF;
michael@0:     int32_t targLev2 = (int32_t)(targCEshifted & mask);
michael@0:     int32_t patLev2 = (int32_t)(patCEshifted & mask);
michael@0:     if ( targLev2 != patLev2 ) {
michael@0:         if ( targLev2 == 0 ) {
michael@0:             return U_CE_SKIP_TARG;
michael@0:         }
michael@0:         if ( patLev2 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) {
michael@0:             return U_CE_SKIP_PATN;
michael@0:         }
michael@0:         return (patLev2 == U_CE_LEVEL2_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev2 == U_CE_LEVEL2_BASE) )?
michael@0:             U_CE_MATCH: U_CE_NO_MATCH;
michael@0:     }
michael@0:     
michael@0:     mask = 0xFFFF0000;
michael@0:     int32_t targLev3 = (int32_t)(targCE & mask);
michael@0:     int32_t patLev3 = (int32_t)(patCE & mask);
michael@0:     if ( targLev3 != patLev3 ) {
michael@0:         return (patLev3 == U_CE_LEVEL3_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev3 == U_CE_LEVEL3_BASE) )?
michael@0:             U_CE_MATCH: U_CE_NO_MATCH;
michael@0:    }
michael@0: 
michael@0:     return U_CE_MATCH;
michael@0: }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0: // TODO: #if BOYER_MOORE, need 32-bit version of compareCE64s
michael@0: #endif
michael@0: 
michael@0: U_CAPI UBool U_EXPORT2 usearch_search(UStringSearch  *strsrch,
michael@0:                                        int32_t        startIdx,
michael@0:                                        int32_t        *matchStart,
michael@0:                                        int32_t        *matchLimit,
michael@0:                                        UErrorCode     *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     // TODO:  reject search patterns beginning with a combining char.
michael@0: 
michael@0: #ifdef USEARCH_DEBUG
michael@0:     if (getenv("USEARCH_DEBUG") != NULL) {
michael@0:         printf("Pattern CEs\n");
michael@0:         for (int ii=0; ii<strsrch->pattern.CELength; ii++) {
michael@0:             printf(" %8x", strsrch->pattern.CE[ii]);
michael@0:         }
michael@0:         printf("\n");
michael@0:     }
michael@0: 
michael@0: #endif
michael@0:     // Input parameter sanity check.
michael@0:     //  TODO:  should input indicies clip to the text length
michael@0:     //         in the same way that UText does.
michael@0:     if(strsrch->pattern.CELength == 0         ||
michael@0:        startIdx < 0                           ||
michael@0:        startIdx > strsrch->search->textLength ||
michael@0:        strsrch->pattern.CE == NULL) {
michael@0:            *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:            return FALSE;
michael@0:     }
michael@0: 
michael@0:     if (strsrch->pattern.PCE == NULL) {
michael@0:         initializePatternPCETable(strsrch, status);
michael@0:     }
michael@0: 
michael@0:     ucol_setOffset(strsrch->textIter, startIdx, status);
michael@0:     CEBuffer ceb(strsrch, status);
michael@0: 
michael@0: 
michael@0:     int32_t    targetIx = 0;
michael@0:     const CEI *targetCEI = NULL;
michael@0:     int32_t    patIx;
michael@0:     UBool      found;
michael@0: 
michael@0:     int32_t  mStart = -1;
michael@0:     int32_t  mLimit = -1;
michael@0:     int32_t  minLimit;
michael@0:     int32_t  maxLimit;
michael@0: 
michael@0: 
michael@0: 
michael@0:     // Outer loop moves over match starting positions in the
michael@0:     //      target CE space.
michael@0:     // Here we see the target as a sequence of collation elements, resulting from the following:
michael@0:     // 1. Target characters were decomposed, and (if appropriate) other compressions and expansions are applied
michael@0:     //    (for example, digraphs such as IJ may be broken into two characters).
michael@0:     // 2. An int64_t CE weight is determined for each resulting unit (high 16 bits are primary strength, next
michael@0:     //    16 bits are secondary, next 16 (the high 16 bits of the low 32-bit half) are tertiary. Any of these
michael@0:     //    fields that are for strengths below that of the collator are set to 0. If this makes the int64_t
michael@0:     //    CE weight 0 (as for a combining diacritic with secondary weight when the collator strentgh is primary),
michael@0:     //    then the CE is deleted, so the following code sees only CEs that are relevant.
michael@0:     // For each CE, the lowIndex and highIndex correspond to where this CE begins and ends in the original text.
michael@0:     // If lowIndex==highIndex, either the CE resulted from an expansion/decomposition of one of the original text
michael@0:     // characters, or the CE marks the limit of the target text (in which case the CE weight is UCOL_PROCESSED_NULLORDER).
michael@0:     //
michael@0:     for(targetIx=0; ; targetIx++)
michael@0:     {
michael@0:         found = TRUE;
michael@0:         //  Inner loop checks for a match beginning at each
michael@0:         //  position from the outer loop.
michael@0:         int32_t targetIxOffset = 0;
michael@0:         int64_t patCE = 0;
michael@0:         // For targetIx > 0, this ceb.get gets a CE that is as far back in the ring buffer
michael@0:         // (compared to the last CE fetched for the previous targetIx value) as we need to go
michael@0:         // for this targetIx value, so if it is non-NULL then other ceb.get calls should be OK.
michael@0:         const CEI *firstCEI = ceb.get(targetIx);
michael@0:         if (firstCEI == NULL) {
michael@0:             *status = U_INTERNAL_PROGRAM_ERROR;
michael@0:             found = FALSE;
michael@0:             break;
michael@0:         }
michael@0:         
michael@0:         for (patIx=0; patIx<strsrch->pattern.PCELength; patIx++) {
michael@0:             patCE = strsrch->pattern.PCE[patIx];
michael@0:             targetCEI = ceb.get(targetIx+patIx+targetIxOffset);
michael@0:             //  Compare CE from target string with CE from the pattern.
michael@0:             //    Note that the target CE will be UCOL_PROCESSED_NULLORDER if we reach the end of input,
michael@0:             //    which will fail the compare, below.
michael@0:             UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType);
michael@0:             if ( ceMatch == U_CE_NO_MATCH ) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             } else if ( ceMatch > U_CE_NO_MATCH ) {
michael@0:                 if ( ceMatch == U_CE_SKIP_TARG ) {
michael@0:                     // redo with same patCE, next targCE
michael@0:                     patIx--;
michael@0:                     targetIxOffset++;
michael@0:                 } else { // ceMatch == U_CE_SKIP_PATN
michael@0:                     // redo with same targCE, next patCE
michael@0:                     targetIxOffset--;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         targetIxOffset += strsrch->pattern.PCELength; // this is now the offset in target CE space to end of the match so far
michael@0: 
michael@0:         if (!found && ((targetCEI == NULL) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) {
michael@0:             // No match at this targetIx.  Try again at the next.
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (!found) {
michael@0:             // No match at all, we have run off the end of the target text.
michael@0:             break;
michael@0:         }
michael@0: 
michael@0: 
michael@0:         // We have found a match in CE space.
michael@0:         // Now determine the bounds in string index space.
michael@0:         //  There still is a chance of match failure if the CE range not correspond to
michael@0:         //     an acceptable character range.
michael@0:         //
michael@0:         const CEI *lastCEI  = ceb.get(targetIx + targetIxOffset - 1);
michael@0: 
michael@0:         mStart   = firstCEI->lowIndex;
michael@0:         minLimit = lastCEI->lowIndex;
michael@0: 
michael@0:         // Look at the CE following the match.  If it is UCOL_NULLORDER the match
michael@0:         //   extended to the end of input, and the match is good.
michael@0: 
michael@0:         // Look at the high and low indices of the CE following the match. If
michael@0:         // they are the same it means one of two things:
michael@0:         //    1. The match extended to the last CE from the target text, which is OK, or
michael@0:         //    2. The last CE that was part of the match is in an expansion that extends
michael@0:         //       to the first CE after the match. In this case, we reject the match.
michael@0:         const CEI *nextCEI = 0;
michael@0:         if (strsrch->search->elementComparisonType == 0) {
michael@0:             nextCEI  = ceb.get(targetIx + targetIxOffset);
michael@0:             maxLimit = nextCEI->lowIndex;
michael@0:             if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:             }
michael@0:         } else {
michael@0:             for ( ; ; ++targetIxOffset ) {
michael@0:                 nextCEI = ceb.get(targetIx + targetIxOffset);
michael@0:                 maxLimit = nextCEI->lowIndex;
michael@0:                 // If we are at the end of the target too, match succeeds
michael@0:                 if (  nextCEI->ce == UCOL_PROCESSED_NULLORDER ) {
michael@0:                     break;
michael@0:                 }
michael@0:                 // As long as the next CE has primary weight of 0,
michael@0:                 // it is part of the last target element matched by the pattern;
michael@0:                 // make sure it can be part of a match with the last patCE
michael@0:                 if ( (((nextCEI->ce) >> 32) & 0xFFFF0000UL) == 0 ) {
michael@0:                     UCompareCEsResult ceMatch = compareCE64s(nextCEI->ce, patCE, strsrch->search->elementComparisonType);
michael@0:                     if ( ceMatch == U_CE_NO_MATCH || ceMatch == U_CE_SKIP_PATN ) {
michael@0:                         found = FALSE;
michael@0:                         break;
michael@0:                     }
michael@0:                 // If lowIndex == highIndex, this target CE is part of an expansion of the last matched
michael@0:                 // target element, but it has non-zero primary weight => match fails
michael@0:                 } else if ( nextCEI->lowIndex == nextCEI->highIndex ) {
michael@0:                     found = false;
michael@0:                     break;
michael@0:                 // Else the target CE is not part of an expansion of the last matched element, match succeeds
michael@0:                 } else {
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0: 
michael@0:         // Check for the start of the match being within a combining sequence.
michael@0:         //   This can happen if the pattern itself begins with a combining char, and
michael@0:         //   the match found combining marks in the target text that were attached
michael@0:         //    to something else.
michael@0:         //   This type of match should be rejected for not completely consuming a
michael@0:         //   combining sequence.
michael@0:         if (!isBreakBoundary(strsrch, mStart)) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         // Check for the start of the match being within an Collation Element Expansion,
michael@0:         //   meaning that the first char of the match is only partially matched.
michael@0:         //   With exapnsions, the first CE will report the index of the source
michael@0:         //   character, and all subsequent (expansions) CEs will report the source index of the
michael@0:         //    _following_ character.
michael@0:         int32_t secondIx = firstCEI->highIndex;
michael@0:         if (mStart == secondIx) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         //  Advance the match end position to the first acceptable match boundary.
michael@0:         //    This advances the index over any combining charcters.
michael@0:         mLimit = maxLimit;
michael@0:         if (minLimit < maxLimit) {
michael@0:             // When the last CE's low index is same with its high index, the CE is likely
michael@0:             // a part of expansion. In this case, the index is located just after the
michael@0:             // character corresponding to the CEs compared above. If the index is right
michael@0:             // at the break boundary, move the position to the next boundary will result
michael@0:             // incorrect match length when there are ignorable characters exist between
michael@0:             // the position and the next character produces CE(s). See ticket#8482.
michael@0:             if (minLimit == lastCEI->highIndex && isBreakBoundary(strsrch, minLimit)) {
michael@0:                 mLimit = minLimit;
michael@0:             } else {
michael@0:                 int32_t nba = nextBoundaryAfter(strsrch, minLimit);
michael@0:                 if (nba >= lastCEI->highIndex) {
michael@0:                     mLimit = nba;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:     #ifdef USEARCH_DEBUG
michael@0:         if (getenv("USEARCH_DEBUG") != NULL) {
michael@0:             printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
michael@0:         }
michael@0:     #endif
michael@0: 
michael@0:         // If advancing to the end of a combining sequence in character indexing space
michael@0:         //   advanced us beyond the end of the match in CE space, reject this match.
michael@0:         if (mLimit > maxLimit) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         if (!isBreakBoundary(strsrch, mLimit)) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         if (! checkIdentical(strsrch, mStart, mLimit)) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         if (found) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     #ifdef USEARCH_DEBUG
michael@0:     if (getenv("USEARCH_DEBUG") != NULL) {
michael@0:         printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx);
michael@0:         int32_t  lastToPrint = ceb.limitIx+2;
michael@0:         for (int ii=ceb.firstIx; ii<lastToPrint; ii++) {
michael@0:             printf("%8x@%d ", ceb.get(ii)->ce, ceb.get(ii)->srcIndex);
michael@0:         }
michael@0:         printf("\n%s\n", found? "match found" : "no match");
michael@0:     }
michael@0:     #endif
michael@0: 
michael@0:     // All Done.  Store back the match bounds to the caller.
michael@0:     //
michael@0:     if (found==FALSE) {
michael@0:         mLimit = -1;
michael@0:         mStart = -1;
michael@0:     }
michael@0: 
michael@0:     if (matchStart != NULL) {
michael@0:         *matchStart= mStart;
michael@0:     }
michael@0: 
michael@0:     if (matchLimit != NULL) {
michael@0:         *matchLimit = mLimit;
michael@0:     }
michael@0: 
michael@0:     return found;
michael@0: }
michael@0: 
michael@0: U_CAPI UBool U_EXPORT2 usearch_searchBackwards(UStringSearch  *strsrch,
michael@0:                                                 int32_t        startIdx,
michael@0:                                                 int32_t        *matchStart,
michael@0:                                                 int32_t        *matchLimit,
michael@0:                                                 UErrorCode     *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0:     // TODO:  reject search patterns beginning with a combining char.
michael@0: 
michael@0: #ifdef USEARCH_DEBUG
michael@0:     if (getenv("USEARCH_DEBUG") != NULL) {
michael@0:         printf("Pattern CEs\n");
michael@0:         for (int ii=0; ii<strsrch->pattern.CELength; ii++) {
michael@0:             printf(" %8x", strsrch->pattern.CE[ii]);
michael@0:         }
michael@0:         printf("\n");
michael@0:     }
michael@0: 
michael@0: #endif
michael@0:     // Input parameter sanity check.
michael@0:     //  TODO:  should input indicies clip to the text length
michael@0:     //         in the same way that UText does.
michael@0:     if(strsrch->pattern.CELength == 0         ||
michael@0:        startIdx < 0                           ||
michael@0:        startIdx > strsrch->search->textLength ||
michael@0:        strsrch->pattern.CE == NULL) {
michael@0:            *status = U_ILLEGAL_ARGUMENT_ERROR;
michael@0:            return FALSE;
michael@0:     }
michael@0: 
michael@0:     if (strsrch->pattern.PCE == NULL) {
michael@0:         initializePatternPCETable(strsrch, status);
michael@0:     }
michael@0: 
michael@0:     CEBuffer ceb(strsrch, status);
michael@0:     int32_t    targetIx = 0;
michael@0: 
michael@0:     /*
michael@0:      * Pre-load the buffer with the CE's for the grapheme
michael@0:      * after our starting position so that we're sure that
michael@0:      * we can look at the CE following the match when we
michael@0:      * check the match boundaries.
michael@0:      *
michael@0:      * This will also pre-fetch the first CE that we'll
michael@0:      * consider for the match.
michael@0:      */
michael@0:     if (startIdx < strsrch->search->textLength) {
michael@0:         UBreakIterator *bi = strsrch->search->internalBreakIter;
michael@0:         int32_t next = ubrk_following(bi, startIdx);
michael@0: 
michael@0:         ucol_setOffset(strsrch->textIter, next, status);
michael@0: 
michael@0:         for (targetIx = 0; ; targetIx += 1) {
michael@0:             if (ceb.getPrevious(targetIx)->lowIndex < startIdx) {
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     } else {
michael@0:         ucol_setOffset(strsrch->textIter, startIdx, status);
michael@0:     }
michael@0: 
michael@0: 
michael@0:     const CEI *targetCEI = NULL;
michael@0:     int32_t    patIx;
michael@0:     UBool      found;
michael@0: 
michael@0:     int32_t  limitIx = targetIx;
michael@0:     int32_t  mStart = -1;
michael@0:     int32_t  mLimit = -1;
michael@0:     int32_t  minLimit;
michael@0:     int32_t  maxLimit;
michael@0: 
michael@0: 
michael@0: 
michael@0:     // Outer loop moves over match starting positions in the
michael@0:     //      target CE space.
michael@0:     // Here, targetIx values increase toward the beginning of the base text (i.e. we get the text CEs in reverse order).
michael@0:     // But  patIx is 0 at the beginning of the pattern and increases toward the end.
michael@0:     // So this loop performs a comparison starting with the end of pattern, and prcessd toward the beginning of the pattern
michael@0:     // and the beginning of the base text.
michael@0:     for(targetIx = limitIx; ; targetIx += 1)
michael@0:     {
michael@0:         found = TRUE;
michael@0:         // For targetIx > limitIx, this ceb.getPrevious gets a CE that is as far back in the ring buffer
michael@0:         // (compared to the last CE fetched for the previous targetIx value) as we need to go
michael@0:         // for this targetIx value, so if it is non-NULL then other ceb.getPrevious calls should be OK.
michael@0:         const CEI *lastCEI  = ceb.getPrevious(targetIx);
michael@0:         if (lastCEI == NULL) {
michael@0:             *status = U_INTERNAL_PROGRAM_ERROR;
michael@0:             found = FALSE;
michael@0:              break;
michael@0:         }
michael@0:         //  Inner loop checks for a match beginning at each
michael@0:         //  position from the outer loop.
michael@0:         int32_t targetIxOffset = 0;
michael@0:         for (patIx = strsrch->pattern.PCELength - 1; patIx >= 0; patIx -= 1) {
michael@0:             int64_t patCE = strsrch->pattern.PCE[patIx];
michael@0: 
michael@0:             targetCEI = ceb.getPrevious(targetIx + strsrch->pattern.PCELength - 1 - patIx + targetIxOffset);
michael@0:             //  Compare CE from target string with CE from the pattern.
michael@0:             //    Note that the target CE will be UCOL_NULLORDER if we reach the end of input,
michael@0:             //    which will fail the compare, below.
michael@0:             UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType);
michael@0:             if ( ceMatch == U_CE_NO_MATCH ) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             } else if ( ceMatch > U_CE_NO_MATCH ) {
michael@0:                 if ( ceMatch == U_CE_SKIP_TARG ) {
michael@0:                     // redo with same patCE, next targCE
michael@0:                     patIx++;
michael@0:                     targetIxOffset++;
michael@0:                 } else { // ceMatch == U_CE_SKIP_PATN
michael@0:                     // redo with same targCE, next patCE
michael@0:                     targetIxOffset--;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (!found && ((targetCEI == NULL) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) {
michael@0:             // No match at this targetIx.  Try again at the next.
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (!found) {
michael@0:             // No match at all, we have run off the end of the target text.
michael@0:             break;
michael@0:         }
michael@0: 
michael@0: 
michael@0:         // We have found a match in CE space.
michael@0:         // Now determine the bounds in string index space.
michael@0:         //  There still is a chance of match failure if the CE range not correspond to
michael@0:         //     an acceptable character range.
michael@0:         //
michael@0:         const CEI *firstCEI = ceb.getPrevious(targetIx + strsrch->pattern.PCELength - 1 + targetIxOffset);
michael@0:         mStart   = firstCEI->lowIndex;
michael@0: 
michael@0:         // Check for the start of the match being within a combining sequence.
michael@0:         //   This can happen if the pattern itself begins with a combining char, and
michael@0:         //   the match found combining marks in the target text that were attached
michael@0:         //    to something else.
michael@0:         //   This type of match should be rejected for not completely consuming a
michael@0:         //   combining sequence.
michael@0:         if (!isBreakBoundary(strsrch, mStart)) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         // Look at the high index of the first CE in the match. If it's the same as the
michael@0:         // low index, the first CE in the match is in the middle of an expansion.
michael@0:         if (mStart == firstCEI->highIndex) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0: 
michael@0:         minLimit = lastCEI->lowIndex;
michael@0: 
michael@0:         if (targetIx > 0) {
michael@0:             // Look at the CE following the match.  If it is UCOL_NULLORDER the match
michael@0:             //   extended to the end of input, and the match is good.
michael@0: 
michael@0:             // Look at the high and low indices of the CE following the match. If
michael@0:             // they are the same it means one of two things:
michael@0:             //    1. The match extended to the last CE from the target text, which is OK, or
michael@0:             //    2. The last CE that was part of the match is in an expansion that extends
michael@0:             //       to the first CE after the match. In this case, we reject the match.
michael@0:             const CEI *nextCEI  = ceb.getPrevious(targetIx - 1);
michael@0: 
michael@0:             if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:             }
michael@0: 
michael@0:             mLimit = maxLimit = nextCEI->lowIndex;
michael@0: 
michael@0:             //  Advance the match end position to the first acceptable match boundary.
michael@0:             //    This advances the index over any combining charcters.
michael@0:             if (minLimit < maxLimit) {
michael@0:                 int32_t nba = nextBoundaryAfter(strsrch, minLimit);
michael@0: 
michael@0:                 if (nba >= lastCEI->highIndex) {
michael@0:                     mLimit = nba;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             // If advancing to the end of a combining sequence in character indexing space
michael@0:             //   advanced us beyond the end of the match in CE space, reject this match.
michael@0:             if (mLimit > maxLimit) {
michael@0:                 found = FALSE;
michael@0:             }
michael@0: 
michael@0:             // Make sure the end of the match is on a break boundary
michael@0:             if (!isBreakBoundary(strsrch, mLimit)) {
michael@0:                 found = FALSE;
michael@0:             }
michael@0: 
michael@0:         } else {
michael@0:             // No non-ignorable CEs after this point.
michael@0:             // The maximum position is detected by boundary after
michael@0:             // the last non-ignorable CE. Combining sequence
michael@0:             // across the start index will be truncated.
michael@0:             int32_t nba = nextBoundaryAfter(strsrch, minLimit);
michael@0:             mLimit = maxLimit = (nba > 0) && (startIdx > nba) ? nba : startIdx;
michael@0:         }
michael@0: 
michael@0:     #ifdef USEARCH_DEBUG
michael@0:         if (getenv("USEARCH_DEBUG") != NULL) {
michael@0:             printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
michael@0:         }
michael@0:     #endif
michael@0: 
michael@0: 
michael@0:         if (! checkIdentical(strsrch, mStart, mLimit)) {
michael@0:             found = FALSE;
michael@0:         }
michael@0: 
michael@0:         if (found) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     #ifdef USEARCH_DEBUG
michael@0:     if (getenv("USEARCH_DEBUG") != NULL) {
michael@0:         printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx);
michael@0:         int32_t  lastToPrint = ceb.limitIx+2;
michael@0:         for (int ii=ceb.firstIx; ii<lastToPrint; ii++) {
michael@0:             printf("%8x@%d ", ceb.get(ii)->ce, ceb.get(ii)->srcIndex);
michael@0:         }
michael@0:         printf("\n%s\n", found? "match found" : "no match");
michael@0:     }
michael@0:     #endif
michael@0: 
michael@0:     // All Done.  Store back the match bounds to the caller.
michael@0:     //
michael@0:     if (found==FALSE) {
michael@0:         mLimit = -1;
michael@0:         mStart = -1;
michael@0:     }
michael@0: 
michael@0:     if (matchStart != NULL) {
michael@0:         *matchStart= mStart;
michael@0:     }
michael@0: 
michael@0:     if (matchLimit != NULL) {
michael@0:         *matchLimit = mLimit;
michael@0:     }
michael@0: 
michael@0:     return found;
michael@0: }
michael@0: 
michael@0: // internal use methods declared in usrchimp.h -----------------------------
michael@0: 
michael@0: UBool usearch_handleNextExact(UStringSearch *strsrch, UErrorCode *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0:     UCollationElements *coleiter        = strsrch->textIter;
michael@0:     int32_t             textlength      = strsrch->search->textLength;
michael@0:     int32_t            *patternce       = strsrch->pattern.CE;
michael@0:     int32_t             patterncelength = strsrch->pattern.CELength;
michael@0:     int32_t             textoffset      = ucol_getOffset(coleiter);
michael@0: 
michael@0:     // status used in setting coleiter offset, since offset is checked in
michael@0:     // shiftForward before setting the coleiter offset, status never
michael@0:     // a failure
michael@0:     textoffset = shiftForward(strsrch, textoffset, UCOL_NULLORDER,
michael@0:                               patterncelength);
michael@0:     while (textoffset <= textlength)
michael@0:     {
michael@0:         uint32_t    patternceindex = patterncelength - 1;
michael@0:         int32_t     targetce;
michael@0:         UBool       found          = FALSE;
michael@0:         int32_t    lastce          = UCOL_NULLORDER;
michael@0: 
michael@0:         setColEIterOffset(coleiter, textoffset);
michael@0: 
michael@0:         for (;;) {
michael@0:             // finding the last pattern ce match, imagine composite characters
michael@0:             // for example: search for pattern A in text \u00C0
michael@0:             // we'll have to skip \u0300 the grave first before we get to A
michael@0:             targetce = ucol_previous(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce = getCE(strsrch, targetce);
michael@0:             if (targetce == UCOL_IGNORABLE && inNormBuf(coleiter)) {
michael@0:                 // this is for the text \u0315\u0300 that requires
michael@0:                 // normalization and pattern \u0300, where \u0315 is ignorable
michael@0:                 continue;
michael@0:             }
michael@0:             if (lastce == UCOL_NULLORDER || lastce == UCOL_IGNORABLE) {
michael@0:                 lastce = targetce;
michael@0:             }
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             if (targetce == patternce[patternceindex]) {
michael@0:                 // the first ce can be a contraction
michael@0:                 found = TRUE;
michael@0:                 break;
michael@0:             }
michael@0:             if (!hasExpansion(coleiter)) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         //targetce = lastce;
michael@0: 
michael@0:         while (found && patternceindex > 0) {
michael@0:             lastce = targetce;
michael@0:             targetce    = ucol_previous(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce    = getCE(strsrch, targetce);
michael@0:             if (targetce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             patternceindex --;
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             found = found && targetce == patternce[patternceindex];
michael@0:         }
michael@0: 
michael@0:         targetce = lastce;
michael@0: 
michael@0:         if (!found) {
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 break;
michael@0:             }
michael@0:             textoffset = shiftForward(strsrch, textoffset, lastce,
michael@0:                                       patternceindex);
michael@0:             // status checked at loop.
michael@0:             patternceindex = patterncelength;
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (checkNextExactMatch(strsrch, &textoffset, status)) {
michael@0:             // status checked in ucol_setOffset
michael@0:             setColEIterOffset(coleiter, strsrch->search->matchedIndex);
michael@0:             return TRUE;
michael@0:         }
michael@0:     }
michael@0:     setMatchNotFound(strsrch);
michael@0:     return FALSE;
michael@0: #else
michael@0:     int32_t textOffset = ucol_getOffset(strsrch->textIter);
michael@0:     int32_t start = -1;
michael@0:     int32_t end = -1;
michael@0: 
michael@0:     if (usearch_search(strsrch, textOffset, &start, &end, status)) {
michael@0:         strsrch->search->matchedIndex  = start;
michael@0:         strsrch->search->matchedLength = end - start;
michael@0:         return TRUE;
michael@0:     } else {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: UBool usearch_handleNextCanonical(UStringSearch *strsrch, UErrorCode *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0:     UCollationElements *coleiter        = strsrch->textIter;
michael@0:     int32_t             textlength      = strsrch->search->textLength;
michael@0:     int32_t            *patternce       = strsrch->pattern.CE;
michael@0:     int32_t             patterncelength = strsrch->pattern.CELength;
michael@0:     int32_t             textoffset      = ucol_getOffset(coleiter);
michael@0:     UBool               hasPatternAccents =
michael@0:        strsrch->pattern.hasSuffixAccents || strsrch->pattern.hasPrefixAccents;
michael@0: 
michael@0:     textoffset = shiftForward(strsrch, textoffset, UCOL_NULLORDER,
michael@0:                               patterncelength);
michael@0:     strsrch->canonicalPrefixAccents[0] = 0;
michael@0:     strsrch->canonicalSuffixAccents[0] = 0;
michael@0: 
michael@0:     while (textoffset <= textlength)
michael@0:     {
michael@0:         int32_t     patternceindex = patterncelength - 1;
michael@0:         int32_t     targetce;
michael@0:         UBool       found          = FALSE;
michael@0:         int32_t     lastce         = UCOL_NULLORDER;
michael@0: 
michael@0:         setColEIterOffset(coleiter, textoffset);
michael@0: 
michael@0:         for (;;) {
michael@0:             // finding the last pattern ce match, imagine composite characters
michael@0:             // for example: search for pattern A in text \u00C0
michael@0:             // we'll have to skip \u0300 the grave first before we get to A
michael@0:             targetce = ucol_previous(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce = getCE(strsrch, targetce);
michael@0:             if (lastce == UCOL_NULLORDER || lastce == UCOL_IGNORABLE) {
michael@0:                 lastce = targetce;
michael@0:             }
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             if (targetce == patternce[patternceindex]) {
michael@0:                 // the first ce can be a contraction
michael@0:                 found = TRUE;
michael@0:                 break;
michael@0:             }
michael@0:             if (!hasExpansion(coleiter)) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         while (found && patternceindex > 0) {
michael@0:             targetce    = ucol_previous(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce    = getCE(strsrch, targetce);
michael@0:             if (targetce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             patternceindex --;
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             found = found && targetce == patternce[patternceindex];
michael@0:         }
michael@0: 
michael@0:         // initializing the rearranged accent array
michael@0:         if (hasPatternAccents && !found) {
michael@0:             strsrch->canonicalPrefixAccents[0] = 0;
michael@0:             strsrch->canonicalSuffixAccents[0] = 0;
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 break;
michael@0:             }
michael@0:             found = doNextCanonicalMatch(strsrch, textoffset, status);
michael@0:         }
michael@0: 
michael@0:         if (!found) {
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 break;
michael@0:             }
michael@0:             textoffset = shiftForward(strsrch, textoffset, lastce,
michael@0:                                       patternceindex);
michael@0:             // status checked at loop
michael@0:             patternceindex = patterncelength;
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (checkNextCanonicalMatch(strsrch, &textoffset, status)) {
michael@0:             setColEIterOffset(coleiter, strsrch->search->matchedIndex);
michael@0:             return TRUE;
michael@0:         }
michael@0:     }
michael@0:     setMatchNotFound(strsrch);
michael@0:     return FALSE;
michael@0: #else
michael@0:     int32_t textOffset = ucol_getOffset(strsrch->textIter);
michael@0:     int32_t start = -1;
michael@0:     int32_t end = -1;
michael@0: 
michael@0:     if (usearch_search(strsrch, textOffset, &start, &end, status)) {
michael@0:         strsrch->search->matchedIndex  = start;
michael@0:         strsrch->search->matchedLength = end - start;
michael@0:         return TRUE;
michael@0:     } else {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: UBool usearch_handlePreviousExact(UStringSearch *strsrch, UErrorCode *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0:     UCollationElements *coleiter        = strsrch->textIter;
michael@0:     int32_t            *patternce       = strsrch->pattern.CE;
michael@0:     int32_t             patterncelength = strsrch->pattern.CELength;
michael@0:     int32_t             textoffset      = ucol_getOffset(coleiter);
michael@0: 
michael@0:     // shifting it check for setting offset
michael@0:     // if setOffset is called previously or there was no previous match, we
michael@0:     // leave the offset as it is.
michael@0:     if (strsrch->search->matchedIndex != USEARCH_DONE) {
michael@0:         textoffset = strsrch->search->matchedIndex;
michael@0:     }
michael@0: 
michael@0:     textoffset = reverseShift(strsrch, textoffset, UCOL_NULLORDER,
michael@0:                               patterncelength);
michael@0: 
michael@0:     while (textoffset >= 0)
michael@0:     {
michael@0:         int32_t     patternceindex = 1;
michael@0:         int32_t     targetce;
michael@0:         UBool       found          = FALSE;
michael@0:         int32_t     firstce        = UCOL_NULLORDER;
michael@0: 
michael@0:         // if status is a failure, ucol_setOffset does nothing
michael@0:         setColEIterOffset(coleiter, textoffset);
michael@0: 
michael@0:         for (;;) {
michael@0:             // finding the first pattern ce match, imagine composite
michael@0:             // characters. for example: search for pattern \u0300 in text
michael@0:             // \u00C0, we'll have to skip A first before we get to
michael@0:             // \u0300 the grave accent
michael@0:             targetce = ucol_next(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce = getCE(strsrch, targetce);
michael@0:             if (firstce == UCOL_NULLORDER || firstce == UCOL_IGNORABLE) {
michael@0:                 firstce = targetce;
michael@0:             }
michael@0:             if (targetce == UCOL_IGNORABLE && strsrch->strength != UCOL_PRIMARY) {
michael@0:                 continue;
michael@0:             }
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             if (targetce == patternce[0]) {
michael@0:                 found = TRUE;
michael@0:                 break;
michael@0:             }
michael@0:             if (!hasExpansion(coleiter)) {
michael@0:                 // checking for accents in composite character
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         //targetce = firstce;
michael@0: 
michael@0:         while (found && (patternceindex < patterncelength)) {
michael@0:             firstce = targetce;
michael@0:             targetce    = ucol_next(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce    = getCE(strsrch, targetce);
michael@0:             if (targetce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             found = found && targetce == patternce[patternceindex];
michael@0:             patternceindex ++;
michael@0:         }
michael@0: 
michael@0:         targetce = firstce;
michael@0: 
michael@0:         if (!found) {
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             textoffset = reverseShift(strsrch, textoffset, targetce,
michael@0:                                       patternceindex);
michael@0:             patternceindex = 0;
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (checkPreviousExactMatch(strsrch, &textoffset, status)) {
michael@0:             setColEIterOffset(coleiter, textoffset);
michael@0:             return TRUE;
michael@0:         }
michael@0:     }
michael@0:     setMatchNotFound(strsrch);
michael@0:     return FALSE;
michael@0: #else
michael@0:     int32_t textOffset;
michael@0: 
michael@0:     if (strsrch->search->isOverlap) {
michael@0:         if (strsrch->search->matchedIndex != USEARCH_DONE) {
michael@0:             textOffset = strsrch->search->matchedIndex + strsrch->search->matchedLength - 1;
michael@0:         } else {
michael@0:             // move the start position at the end of possible match
michael@0:             initializePatternPCETable(strsrch, status);
michael@0:             for (int32_t nPCEs = 0; nPCEs < strsrch->pattern.PCELength - 1; nPCEs++) {
michael@0:                 int64_t pce = ucol_nextProcessed(strsrch->textIter, NULL, NULL, status);
michael@0:                 if (pce == UCOL_PROCESSED_NULLORDER) {
michael@0:                     // at the end of the text
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 setMatchNotFound(strsrch);
michael@0:                 return FALSE;
michael@0:             }
michael@0:             textOffset = ucol_getOffset(strsrch->textIter);
michael@0:         }
michael@0:     } else {
michael@0:         textOffset = ucol_getOffset(strsrch->textIter);
michael@0:     }
michael@0: 
michael@0:     int32_t start = -1;
michael@0:     int32_t end = -1;
michael@0: 
michael@0:     if (usearch_searchBackwards(strsrch, textOffset, &start, &end, status)) {
michael@0:         strsrch->search->matchedIndex = start;
michael@0:         strsrch->search->matchedLength = end - start;
michael@0:         return TRUE;
michael@0:     } else {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: UBool usearch_handlePreviousCanonical(UStringSearch *strsrch,
michael@0:                                       UErrorCode    *status)
michael@0: {
michael@0:     if (U_FAILURE(*status)) {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: 
michael@0: #if BOYER_MOORE
michael@0:     UCollationElements *coleiter        = strsrch->textIter;
michael@0:     int32_t            *patternce       = strsrch->pattern.CE;
michael@0:     int32_t             patterncelength = strsrch->pattern.CELength;
michael@0:     int32_t             textoffset      = ucol_getOffset(coleiter);
michael@0:     UBool               hasPatternAccents =
michael@0:        strsrch->pattern.hasSuffixAccents || strsrch->pattern.hasPrefixAccents;
michael@0: 
michael@0:     // shifting it check for setting offset
michael@0:     // if setOffset is called previously or there was no previous match, we
michael@0:     // leave the offset as it is.
michael@0:     if (strsrch->search->matchedIndex != USEARCH_DONE) {
michael@0:         textoffset = strsrch->search->matchedIndex;
michael@0:     }
michael@0: 
michael@0:     textoffset = reverseShift(strsrch, textoffset, UCOL_NULLORDER,
michael@0:                               patterncelength);
michael@0:     strsrch->canonicalPrefixAccents[0] = 0;
michael@0:     strsrch->canonicalSuffixAccents[0] = 0;
michael@0: 
michael@0:     while (textoffset >= 0)
michael@0:     {
michael@0:         int32_t     patternceindex = 1;
michael@0:         int32_t     targetce;
michael@0:         UBool       found          = FALSE;
michael@0:         int32_t     firstce        = UCOL_NULLORDER;
michael@0: 
michael@0:         setColEIterOffset(coleiter, textoffset);
michael@0:         for (;;) {
michael@0:             // finding the first pattern ce match, imagine composite
michael@0:             // characters. for example: search for pattern \u0300 in text
michael@0:             // \u00C0, we'll have to skip A first before we get to
michael@0:             // \u0300 the grave accent
michael@0:             targetce = ucol_next(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce = getCE(strsrch, targetce);
michael@0:             if (firstce == UCOL_NULLORDER || firstce == UCOL_IGNORABLE) {
michael@0:                 firstce = targetce;
michael@0:             }
michael@0: 
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             if (targetce == patternce[0]) {
michael@0:                 // the first ce can be a contraction
michael@0:                 found = TRUE;
michael@0:                 break;
michael@0:             }
michael@0:             if (!hasExpansion(coleiter)) {
michael@0:                 // checking for accents in composite character
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         targetce = firstce;
michael@0: 
michael@0:         while (found && patternceindex < patterncelength) {
michael@0:             targetce    = ucol_next(coleiter, status);
michael@0:             if (U_FAILURE(*status) || targetce == UCOL_NULLORDER) {
michael@0:                 found = FALSE;
michael@0:                 break;
michael@0:             }
michael@0:             targetce = getCE(strsrch, targetce);
michael@0:             if (targetce == UCOL_IGNORABLE) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             // TODO: #if BOYER_MOORE, replace with code using 32-bit version of compareCE64s
michael@0:             found = found && targetce == patternce[patternceindex];
michael@0:             patternceindex ++;
michael@0:         }
michael@0: 
michael@0:         // initializing the rearranged accent array
michael@0:         if (hasPatternAccents && !found) {
michael@0:             strsrch->canonicalPrefixAccents[0] = 0;
michael@0:             strsrch->canonicalSuffixAccents[0] = 0;
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 break;
michael@0:             }
michael@0:             found = doPreviousCanonicalMatch(strsrch, textoffset, status);
michael@0:         }
michael@0: 
michael@0:         if (!found) {
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 break;
michael@0:             }
michael@0:             textoffset = reverseShift(strsrch, textoffset, targetce,
michael@0:                                       patternceindex);
michael@0:             patternceindex = 0;
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         if (checkPreviousCanonicalMatch(strsrch, &textoffset, status)) {
michael@0:             setColEIterOffset(coleiter, textoffset);
michael@0:             return TRUE;
michael@0:         }
michael@0:     }
michael@0:     setMatchNotFound(strsrch);
michael@0:     return FALSE;
michael@0: #else
michael@0:     int32_t textOffset;
michael@0: 
michael@0:     if (strsrch->search->isOverlap) {
michael@0:         if (strsrch->search->matchedIndex != USEARCH_DONE) {
michael@0:             textOffset = strsrch->search->matchedIndex + strsrch->search->matchedLength - 1;
michael@0:         } else {
michael@0:             // move the start position at the end of possible match
michael@0:             initializePatternPCETable(strsrch, status);
michael@0:             for (int32_t nPCEs = 0; nPCEs < strsrch->pattern.PCELength - 1; nPCEs++) {
michael@0:                 int64_t pce = ucol_nextProcessed(strsrch->textIter, NULL, NULL, status);
michael@0:                 if (pce == UCOL_PROCESSED_NULLORDER) {
michael@0:                     // at the end of the text
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:             if (U_FAILURE(*status)) {
michael@0:                 setMatchNotFound(strsrch);
michael@0:                 return FALSE;
michael@0:             }
michael@0:             textOffset = ucol_getOffset(strsrch->textIter);
michael@0:         }
michael@0:     } else {
michael@0:         textOffset = ucol_getOffset(strsrch->textIter);
michael@0:     }
michael@0: 
michael@0:     int32_t start = -1;
michael@0:     int32_t end = -1;
michael@0: 
michael@0:     if (usearch_searchBackwards(strsrch, textOffset, &start, &end, status)) {
michael@0:         strsrch->search->matchedIndex = start;
michael@0:         strsrch->search->matchedLength = end - start;
michael@0:         return TRUE;
michael@0:     } else {
michael@0:         setMatchNotFound(strsrch);
michael@0:         return FALSE;
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: #endif /* #if !UCONFIG_NO_COLLATION */