ICU 56 update step 1

source/i18n/usearch.cpp

 /*
 **********************************************************************
-*   Copyright (C) 2001-2014 IBM and others. All rights reserved.
+*   Copyright (C) 2001-2015 IBM and others. All rights reserved.
 **********************************************************************
 *   Date        Name        Description
 *  07/02/2001   synwee      Creation.
 **********************************************************************
 */
 
 #include "unicode/utypes.h"
 
 #if !UCONFIG_NO_COLLATION && !UCONFIG_NO_BREAK_ITERATION
 
@@ skipping 54 matching lines @@
         return UCOL_PRIMARYORDERMASK;
     case UCOL_SECONDARY:
         return UCOL_SECONDARYORDERMASK | UCOL_PRIMARYORDERMASK;
     default:
         return UCOL_TERTIARYORDERMASK | UCOL_SECONDARYORDERMASK |
                UCOL_PRIMARYORDERMASK;
     }
 }
 
 /**
-* This is to squeeze the 21bit ces into a 256 table
-* @param ce collation element
-* @return collapsed version of the collation element
+* @param ce 32-bit collation element
+* @return hash code
 */
 static
-inline int hash(uint32_t ce)
+inline int hashFromCE32(uint32_t ce)
 {
-    // the old value UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_ does not work
-    // well with the new collation where most of the latin 1 characters
-    // are of the value xx000xxx. their hashes will most of the time be 0
-    // to be discussed on the hash algo.
-    return UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_;
+    int hc = (int)(
+            ((((((ce >> 24) * 37) +
+            (ce >> 16)) * 37) +
+            (ce >> 8)) * 37) +
+            ce);
+    hc %= MAX_TABLE_SIZE_;
+    if (hc < 0) {
+        hc += MAX_TABLE_SIZE_;
+    }
+    return hc;
 }
 
 U_CDECL_BEGIN
 static UBool U_CALLCONV
 usearch_cleanup(void) {
     g_nfcImpl = NULL;
     return TRUE;
 }
 U_CDECL_END
 
@@ skipping 385 matching lines @@
     // the number of ces minus their expansion, since expansions can come
     // from a character.
     int32_t count;
     for (count = 0; count < MAX_TABLE_SIZE_; count ++) {
         shift[count] = defaultforward;
     }
     cesize --; // down to the last index
     for (count = 0; count < cesize; count ++) {
         // number of ces from right of array to the count
         int temp = defaultforward - count - 1;
-        shift[hash(cetable[count])] = temp > 1 ? temp : 1;
+        shift[hashFromCE32(cetable[count])] = temp > 1 ? temp : 1;
     }
-    shift[hash(cetable[cesize])] = 1;
+    shift[hashFromCE32(cetable[cesize])] = 1;
     // for ignorables we just shift by one. see test examples.
-    shift[hash(0)] = 1;
+    shift[hashFromCE32(0)] = 1;
 
     for (count = 0; count < MAX_TABLE_SIZE_; count ++) {
         backshift[count] = defaultbackward;
     }
     for (count = cesize; count > 0; count --) {
         // the original value count does not seem to work
-        backshift[hash(cetable[count])] = count > expansionsize ?
+        backshift[hashFromCE32(cetable[count])] = count > expansionsize ?
                                           (int16_t)(count - expansionsize) : 1;
     }
-    backshift[hash(cetable[0])] = 1;
-    backshift[hash(0)] = 1;
+    backshift[hashFromCE32(cetable[0])] = 1;
+    backshift[hashFromCE32(0)] = 1;
 }
 
 /**
 * Building of the pattern collation element list and the boyer moore strsrch
 * table.
 * The canonical match will only be performed after the default match fails.
 * For both cases we need to remember the size of the composed and decomposed
 * versions of the string. Since the Boyer-Moore shift calculations shifts by
 * a number of characters in the text and tries to match the pattern from that
 * offset, the shift value can not be too large in case we miss some
@@ skipping 202 matching lines @@
 * @return final offset
 */
 static
 inline int32_t shiftForward(UStringSearch *strsrch,
                                 int32_t    textoffset,
                                 int32_t       ce,
                                 int32_t        patternceindex)
 {
     UPattern *pattern = &(strsrch->pattern);
     if (ce != UCOL_NULLORDER) {
-        int32_t shift = pattern->shift[hash(ce)];
+        int32_t shift = pattern->shift[hashFromCE32(ce)];
         // this is to adjust for characters in the middle of the
         // substring for matching that failed.
         int32_t adjust = pattern->cesLength - patternceindex;
         if (adjust > 1 && shift >= adjust) {
             shift -= adjust - 1;
         }
         textoffset += shift;
     }
     else {
         textoffset += pattern->defaultShiftSize;
@@ skipping 1220 matching lines @@
     if (strsrch->search->isOverlap) {
         if (textoffset != strsrch->search->textLength) {
             textoffset --;
         }
         else {
             textoffset -= strsrch->pattern.defaultShiftSize;
         }
     }
     else {
         if (ce != UCOL_NULLORDER) {
-            int32_t shift = strsrch->pattern.backShift[hash(ce)];
+            int32_t shift = strsrch->pattern.backShift[hashFromCE32(ce)];
 
             // this is to adjust for characters in the middle of the substring
             // for matching that failed.
             int32_t adjust = patternceindex;
             if (adjust > 1 && shift > adjust) {
                 shift -= adjust - 1;
             }
             textoffset -= shift;
         }
         else {
@@ skipping 1813 matching lines @@
             U_CE_MATCH: U_CE_NO_MATCH;
    }
 
     return U_CE_MATCH;
 }
 
 #if BOYER_MOORE
 // TODO: #if BOYER_MOORE, need 32-bit version of compareCE64s
 #endif
 
+namespace {
+
+UChar32 codePointAt(const USearch &search, int32_t index) {
+    if (index < search.textLength) {
+        UChar32 c;
+        U16_NEXT(search.text, index, search.textLength, c);
+        return c;
+    }
+    return U_SENTINEL;
+}
+
+UChar32 codePointBefore(const USearch &search, int32_t index) {
+    if (0 < index) {
+        UChar32 c;
+        U16_PREV(search.text, 0, index, c);
+        return c;
+    }
+    return U_SENTINEL;
+}
+
+}  // namespace
+
 U_CAPI UBool U_EXPORT2 usearch_search(UStringSearch  *strsrch,
                                        int32_t        startIdx,
                                        int32_t        *matchStart,
                                        int32_t        *matchLimit,
                                        UErrorCode     *status)
 {
     if (U_FAILURE(*status)) {
         return FALSE;
     }
 
@@ skipping 173 matching lines @@
         // Check for the start of the match being within an Collation Element Expansion,
         //   meaning that the first char of the match is only partially matched.
         //   With exapnsions, the first CE will report the index of the source
         //   character, and all subsequent (expansions) CEs will report the source index of the
         //    _following_ character.
         int32_t secondIx = firstCEI->highIndex;
         if (mStart == secondIx) {
             found = FALSE;
         }
 
+        // Allow matches to end in the middle of a grapheme cluster if the following
+        // conditions are met; this is needed to make prefix search work properly in
+        // Indic, see #11750
+        // * the default breakIter is being used
+        // * the next collation element after this combining sequence
+        //   - has non-zero primary weight
+        //   - corresponds to a separate character following the one at end of the current match
+        //   (the second of these conditions, and perhaps both, may be redundant given the
+        //   subsequent check for normalization boundary; however they are likely much faster
+        //   tests in any case)
+        // * the match limit is a normalization boundary
+        UBool allowMidclusterMatch = FALSE;
+        if (strsrch->search->text != NULL && strsrch->search->textLength > maxLimit) {
+            allowMidclusterMatch =
+                    strsrch->search->breakIter == NULL &&
+                    nextCEI != NULL && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 &&
+                    maxLimit >= lastCEI->highIndex && nextCEI->highIndex > maxLimit &&
+                    (strsrch->nfd->hasBoundaryBefore(codePointAt(*strsrch->search, maxLimit)) ||
+                        strsrch->nfd->hasBoundaryAfter(codePointBefore(*strsrch->search, maxLimit)));
+        }
+        // If those conditions are met, then:
+        // * do NOT advance the candidate match limit (mLimit) to a break boundary; however
+        //   the match limit may be backed off to a previous break boundary. This handles
+        //   cases in which mLimit includes target characters that are ignorable with current
+        //   settings (such as space) and which extend beyond the pattern match.
+        // * do NOT require that end of the combining sequence not extend beyond the match in CE space
+        // * do NOT require that match limit be on a breakIter boundary
+
         //  Advance the match end position to the first acceptable match boundary.
         //    This advances the index over any combining charcters.
         mLimit = maxLimit;
         if (minLimit < maxLimit) {
             // When the last CE's low index is same with its high index, the CE is likely
             // a part of expansion. In this case, the index is located just after the
             // character corresponding to the CEs compared above. If the index is right
             // at the break boundary, move the position to the next boundary will result
             // incorrect match length when there are ignorable characters exist between
             // the position and the next character produces CE(s). See ticket#8482.
             if (minLimit == lastCEI->highIndex && isBreakBoundary(strsrch, minLimit)) {
                 mLimit = minLimit;
             } else {
                 int32_t nba = nextBoundaryAfter(strsrch, minLimit);
-                if (nba >= lastCEI->highIndex) {
+                // Note that we can have nba < maxLimit && nba >= minLImit, in which
+                // case we want to set mLimit to nba regardless of allowMidclusterMatch
+                // (i.e. we back off mLimit to the previous breakIterator boundary).
+                if (nba >= lastCEI->highIndex && (!allowMidclusterMatch || nba < maxLimit)) {
                     mLimit = nba;
                 }
             }
         }
 
     #ifdef USEARCH_DEBUG
         if (getenv("USEARCH_DEBUG") != NULL) {
             printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
         }
     #endif
 
-        // If advancing to the end of a combining sequence in character indexing space
-        //   advanced us beyond the end of the match in CE space, reject this match.
-        if (mLimit > maxLimit) {
-            found = FALSE;
-        }
+        if (!allowMidclusterMatch) {
+            // If advancing to the end of a combining sequence in character indexing space
+            //   advanced us beyond the end of the match in CE space, reject this match.
+            if (mLimit > maxLimit) {
+                found = FALSE;
+            }
 
-        if (!isBreakBoundary(strsrch, mLimit)) {
-            found = FALSE;
+            if (!isBreakBoundary(strsrch, mLimit)) {
+                found = FALSE;
+            }
         }
 
         if (! checkIdentical(strsrch, mStart, mLimit)) {
             found = FALSE;
         }
 
         if (found) {
             break;
         }
     }
@@ skipping 196 matching lines @@
             //    2. The last CE that was part of the match is in an expansion that extends
             //       to the first CE after the match. In this case, we reject the match.
             const CEI *nextCEI  = ceb.getPrevious(targetIx - 1);
 
             if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
                 found = FALSE;
             }
 
             mLimit = maxLimit = nextCEI->lowIndex;
 
+            // Allow matches to end in the middle of a grapheme cluster if the following
+            // conditions are met; this is needed to make prefix search work properly in
+            // Indic, see #11750
+            // * the default breakIter is being used
+            // * the next collation element after this combining sequence
+            //   - has non-zero primary weight
+            //   - corresponds to a separate character following the one at end of the current match
+            //   (the second of these conditions, and perhaps both, may be redundant given the
+            //   subsequent check for normalization boundary; however they are likely much faster
+            //   tests in any case)
+            // * the match limit is a normalization boundary
+            UBool allowMidclusterMatch = FALSE;
+            if (strsrch->search->text != NULL && strsrch->search->textLength > maxLimit) {
+                allowMidclusterMatch =
+                        strsrch->search->breakIter == NULL &&
+                        nextCEI != NULL && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 &&
+                        maxLimit >= lastCEI->highIndex && nextCEI->highIndex > maxLimit &&
+                        (strsrch->nfd->hasBoundaryBefore(codePointAt(*strsrch->search, maxLimit)) ||
+                            strsrch->nfd->hasBoundaryAfter(codePointBefore(*strsrch->search, maxLimit)));
+            }
+            // If those conditions are met, then:
+            // * do NOT advance the candidate match limit (mLimit) to a break boundary; however
+            //   the match limit may be backed off to a previous break boundary. This handles
+            //   cases in which mLimit includes target characters that are ignorable with current
+            //   settings (such as space) and which extend beyond the pattern match.
+            // * do NOT require that end of the combining sequence not extend beyond the match in CE space
+            // * do NOT require that match limit be on a breakIter boundary
+
             //  Advance the match end position to the first acceptable match boundary.
-            //    This advances the index over any combining charcters.
+            //    This advances the index over any combining characters.
             if (minLimit < maxLimit) {
                 int32_t nba = nextBoundaryAfter(strsrch, minLimit);
-
-                if (nba >= lastCEI->highIndex) {
+                // Note that we can have nba < maxLimit && nba >= minLImit, in which
+                // case we want to set mLimit to nba regardless of allowMidclusterMatch
+                // (i.e. we back off mLimit to the previous breakIterator boundary).
+                if (nba >= lastCEI->highIndex && (!allowMidclusterMatch || nba < maxLimit)) {
                     mLimit = nba;
                 }
             }
 
-            // If advancing to the end of a combining sequence in character indexing space
-            //   advanced us beyond the end of the match in CE space, reject this match.
-            if (mLimit > maxLimit) {
-                found = FALSE;
-            }
+            if (!allowMidclusterMatch) {
+                // If advancing to the end of a combining sequence in character indexing space
+                //   advanced us beyond the end of the match in CE space, reject this match.
+                if (mLimit > maxLimit) {
+                    found = FALSE;
+                }
 
-            // Make sure the end of the match is on a break boundary
-            if (!isBreakBoundary(strsrch, mLimit)) {
-                found = FALSE;
+                // Make sure the end of the match is on a break boundary
+                if (!isBreakBoundary(strsrch, mLimit)) {
+                    found = FALSE;
+                }
             }
 
         } else {
             // No non-ignorable CEs after this point.
             // The maximum position is detected by boundary after
             // the last non-ignorable CE. Combining sequence
             // across the start index will be truncated.
             int32_t nba = nextBoundaryAfter(strsrch, minLimit);
             mLimit = maxLimit = (nba > 0) && (startIdx > nba) ? nba : startIdx;
         }
@@ skipping 566 matching lines @@
         strsrch->search->matchedLength = end - start;
         return TRUE;
     } else {
         setMatchNotFound(strsrch);
         return FALSE;
     }
 #endif
 }
 
 #endif /* #if !UCONFIG_NO_COLLATION */