+//
+// CEI Collation Element + source text index.
+// These structs are kept in the circular buffer.
+//
+struct CEI {
+ int64_t ce;
+ int32_t lowIndex;
+ int32_t highIndex;
+};
+
+U_NAMESPACE_BEGIN
+
+namespace {
+//
+// CEIBuffer A circular buffer of CEs-with-index from the text being searched.
+//
+#define DEFAULT_CEBUFFER_SIZE 96
+#define CEBUFFER_EXTRA 32
+// Some typical max values to make buffer size more reasonable for asymmetric search.
+// #8694 is for a better long-term solution to allocation of this buffer.
+#define MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L 8
+#define MAX_TARGET_IGNORABLES_PER_PAT_OTHER 3
+#define MIGHT_BE_JAMO_L(c) ((c >= 0x1100 && c <= 0x115E) || (c >= 0x3131 && c <= 0x314E) || (c >= 0x3165 && c <= 0x3186))
+struct CEIBuffer {
+ CEI defBuf[DEFAULT_CEBUFFER_SIZE];
+ CEI *buf;
+ int32_t bufSize;
+ int32_t firstIx;
+ int32_t limitIx;
+ UCollationElements *ceIter;
+ UStringSearch *strSearch;
+
+
+
+ CEIBuffer(UStringSearch *ss, UErrorCode *status);
+ ~CEIBuffer();
+ const CEI *get(int32_t index);
+ const CEI *getPrevious(int32_t index);
+};
+
+
+CEIBuffer::CEIBuffer(UStringSearch *ss, UErrorCode *status) {
+ buf = defBuf;
+ strSearch = ss;
+ bufSize = ss->pattern.pcesLength + CEBUFFER_EXTRA;
+ if (ss->search->elementComparisonType != 0) {
+ const UChar * patText = ss->pattern.text;
+ if (patText) {
+ const UChar * patTextLimit = patText + ss->pattern.textLength;
+ while ( patText < patTextLimit ) {
+ UChar c = *patText++;
+ if (MIGHT_BE_JAMO_L(c)) {
+ bufSize += MAX_TARGET_IGNORABLES_PER_PAT_JAMO_L;
+ } else {
+ // No check for surrogates, we might allocate slightly more buffer than necessary.
+ bufSize += MAX_TARGET_IGNORABLES_PER_PAT_OTHER;
+ }
+ }
+ }
+ }
+ ceIter = ss->textIter;
+ firstIx = 0;
+ limitIx = 0;
+
+ if (!initTextProcessedIter(ss, status)) { return; }
+
+ if (bufSize>DEFAULT_CEBUFFER_SIZE) {
+ buf = (CEI *)uprv_malloc(bufSize * sizeof(CEI));
+ if (buf == NULL) {
+ *status = U_MEMORY_ALLOCATION_ERROR;
+ }
+ }
+}
+
+// TODO: add a reset or init function so that allocated
+// buffers can be retained & reused.
+
+CEIBuffer::~CEIBuffer() {
+ if (buf != defBuf) {
+ uprv_free(buf);
+ }
+}
+
+
+// Get the CE with the specified index.
+// Index must be in the range
+// n-history_size < index < n+1
+// where n is the largest index to have been fetched by some previous call to this function.
+// The CE value will be UCOL__PROCESSED_NULLORDER at end of input.
+//
+const CEI *CEIBuffer::get(int32_t index) {
+ int i = index % bufSize;
+
+ if (index>=firstIx && index<limitIx) {
+ // The request was for an entry already in our buffer.
+ // Just return it.
+ return &buf[i];
+ }
+
+ // Caller is requesting a new, never accessed before, CE.
+ // Verify that it is the next one in sequence, which is all
+ // that is allowed.
+ if (index != limitIx) {
+ U_ASSERT(FALSE);
+
+ return NULL;
+ }
+
+ // Manage the circular CE buffer indexing
+ limitIx++;
+
+ if (limitIx - firstIx >= bufSize) {
+ // The buffer is full, knock out the lowest-indexed entry.
+ firstIx++;
+ }
+
+ UErrorCode status = U_ZERO_ERROR;
+
+ buf[i].ce = strSearch->textProcessedIter->nextProcessed(&buf[i].lowIndex, &buf[i].highIndex, &status);
+
+ return &buf[i];
+}
+
+// Get the CE with the specified index.
+// Index must be in the range
+// n-history_size < index < n+1
+// where n is the largest index to have been fetched by some previous call to this function.
+// The CE value will be UCOL__PROCESSED_NULLORDER at end of input.
+//
+const CEI *CEIBuffer::getPrevious(int32_t index) {
+ int i = index % bufSize;
+
+ if (index>=firstIx && index<limitIx) {
+ // The request was for an entry already in our buffer.
+ // Just return it.
+ return &buf[i];
+ }
+
+ // Caller is requesting a new, never accessed before, CE.
+ // Verify that it is the next one in sequence, which is all
+ // that is allowed.
+ if (index != limitIx) {
+ U_ASSERT(FALSE);
+
+ return NULL;
+ }
+
+ // Manage the circular CE buffer indexing
+ limitIx++;
+
+ if (limitIx - firstIx >= bufSize) {
+ // The buffer is full, knock out the lowest-indexed entry.
+ firstIx++;
+ }
+
+ UErrorCode status = U_ZERO_ERROR;
+
+ buf[i].ce = strSearch->textProcessedIter->previousProcessed(&buf[i].lowIndex, &buf[i].highIndex, &status);
+
+ return &buf[i];
+}
+
+}
+
+U_NAMESPACE_END
+
+
+// #define USEARCH_DEBUG
+
+#ifdef USEARCH_DEBUG
+#include <stdio.h>
+#include <stdlib.h>
+#endif
+
+/*
+ * Find the next break boundary after startIndex. If the UStringSearch object
+ * has an external break iterator, use that. Otherwise use the internal character
+ * break iterator.
+ */
+static int32_t nextBoundaryAfter(UStringSearch *strsrch, int32_t startIndex) {
+#if 0
+ const UChar *text = strsrch->search->text;
+ int32_t textLen = strsrch->search->textLength;
+
+ U_ASSERT(startIndex>=0);
+ U_ASSERT(startIndex<=textLen);
+
+ if (startIndex >= textLen) {
+ return startIndex;
+ }
+
+ UChar32 c;
+ int32_t i = startIndex;
+ U16_NEXT(text, i, textLen, c);
+
+ // If we are on a control character, stop without looking for combining marks.
+ // Control characters do not combine.
+ int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
+ if (gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR) {
+ return i;
+ }
+
+ // The initial character was not a control, and can thus accept trailing
+ // combining characters. Advance over however many of them there are.
+ int32_t indexOfLastCharChecked;
+ for (;;) {
+ indexOfLastCharChecked = i;
+ if (i>=textLen) {
+ break;
+ }
+ U16_NEXT(text, i, textLen, c);
+ gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
+ if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) {
+ break;
+ }
+ }
+ return indexOfLastCharChecked;
+#elif !UCONFIG_NO_BREAK_ITERATION
+ UBreakIterator *breakiterator = strsrch->search->breakIter;
+
+ if (breakiterator == NULL) {
+ breakiterator = strsrch->search->internalBreakIter;
+ }
+
+ if (breakiterator != NULL) {
+ return ubrk_following(breakiterator, startIndex);
+ }
+
+ return startIndex;
+#else
+ // **** or should we use the original code? ****
+ return startIndex;
+#endif
+
+}
+
+/*
+ * Returns TRUE if index is on a break boundary. If the UStringSearch
+ * has an external break iterator, test using that, otherwise test
+ * using the internal character break iterator.
+ */
+static UBool isBreakBoundary(UStringSearch *strsrch, int32_t index) {
+#if 0
+ const UChar *text = strsrch->search->text;
+ int32_t textLen = strsrch->search->textLength;
+
+ U_ASSERT(index>=0);
+ U_ASSERT(index<=textLen);
+
+ if (index>=textLen || index<=0) {
+ return TRUE;
+ }
+
+ // If the character at the current index is not a GRAPHEME_EXTEND
+ // then we can not be within a combining sequence.
+ UChar32 c;
+ U16_GET(text, 0, index, textLen, c);
+ int32_t gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
+ if (gcProperty != U_GCB_EXTEND && gcProperty != U_GCB_SPACING_MARK) {
+ return TRUE;
+ }
+
+ // We are at a combining mark. If the preceding character is anything
+ // except a CONTROL, CR or LF, we are in a combining sequence.
+ U16_PREV(text, 0, index, c);
+ gcProperty = u_getIntPropertyValue(c, UCHAR_GRAPHEME_CLUSTER_BREAK);
+ UBool combining = !(gcProperty==U_GCB_CONTROL || gcProperty==U_GCB_LF || gcProperty==U_GCB_CR);
+ return !combining;
+#elif !UCONFIG_NO_BREAK_ITERATION
+ UBreakIterator *breakiterator = strsrch->search->breakIter;
+
+ if (breakiterator == NULL) {
+ breakiterator = strsrch->search->internalBreakIter;
+ }
+
+ return (breakiterator != NULL && ubrk_isBoundary(breakiterator, index));
+#else
+ // **** or use the original code? ****
+ return TRUE;
+#endif
+}
+
+#if 0
+static UBool onBreakBoundaries(const UStringSearch *strsrch, int32_t start, int32_t end)
+{
+#if !UCONFIG_NO_BREAK_ITERATION
+ UBreakIterator *breakiterator = strsrch->search->breakIter;
+
+ if (breakiterator != NULL) {
+ int32_t startindex = ubrk_first(breakiterator);
+ int32_t endindex = ubrk_last(breakiterator);
+
+ // out-of-range indexes are never boundary positions
+ if (start < startindex || start > endindex ||
+ end < startindex || end > endindex) {
+ return FALSE;
+ }
+
+ return ubrk_isBoundary(breakiterator, start) &&
+ ubrk_isBoundary(breakiterator, end);
+ }
+#endif
+
+ return TRUE;
+}
+#endif
+
+typedef enum {
+ U_CE_MATCH = -1,
+ U_CE_NO_MATCH = 0,
+ U_CE_SKIP_TARG,
+ U_CE_SKIP_PATN
+} UCompareCEsResult;
+#define U_CE_LEVEL2_BASE 0x00000005
+#define U_CE_LEVEL3_BASE 0x00050000
+
+static UCompareCEsResult compareCE64s(int64_t targCE, int64_t patCE, int16_t compareType) {
+ if (targCE == patCE) {
+ return U_CE_MATCH;
+ }
+ if (compareType == 0) {
+ return U_CE_NO_MATCH;
+ }
+
+ int64_t targCEshifted = targCE >> 32;
+ int64_t patCEshifted = patCE >> 32;
+ int64_t mask;
+
+ mask = 0xFFFF0000;
+ int32_t targLev1 = (int32_t)(targCEshifted & mask);
+ int32_t patLev1 = (int32_t)(patCEshifted & mask);
+ if ( targLev1 != patLev1 ) {
+ if ( targLev1 == 0 ) {
+ return U_CE_SKIP_TARG;
+ }
+ if ( patLev1 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) {
+ return U_CE_SKIP_PATN;
+ }
+ return U_CE_NO_MATCH;
+ }
+
+ mask = 0x0000FFFF;
+ int32_t targLev2 = (int32_t)(targCEshifted & mask);
+ int32_t patLev2 = (int32_t)(patCEshifted & mask);
+ if ( targLev2 != patLev2 ) {
+ if ( targLev2 == 0 ) {
+ return U_CE_SKIP_TARG;
+ }
+ if ( patLev2 == 0 && compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD ) {
+ return U_CE_SKIP_PATN;
+ }
+ return (patLev2 == U_CE_LEVEL2_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev2 == U_CE_LEVEL2_BASE) )?
+ U_CE_MATCH: U_CE_NO_MATCH;
+ }
+
+ mask = 0xFFFF0000;
+ int32_t targLev3 = (int32_t)(targCE & mask);
+ int32_t patLev3 = (int32_t)(patCE & mask);
+ if ( targLev3 != patLev3 ) {
+ return (patLev3 == U_CE_LEVEL3_BASE || (compareType == USEARCH_ANY_BASE_WEIGHT_IS_WILDCARD && targLev3 == U_CE_LEVEL3_BASE) )?
+ U_CE_MATCH: U_CE_NO_MATCH;
+ }
+
+ return U_CE_MATCH;
+}
+
+#if BOYER_MOORE
+// TODO: #if BOYER_MOORE, need 32-bit version of compareCE64s
+#endif
+
+U_CAPI UBool U_EXPORT2 usearch_search(UStringSearch *strsrch,
+ int32_t startIdx,
+ int32_t *matchStart,
+ int32_t *matchLimit,
+ UErrorCode *status)
+{
+ if (U_FAILURE(*status)) {
+ return FALSE;
+ }
+
+ // TODO: reject search patterns beginning with a combining char.
+
+#ifdef USEARCH_DEBUG
+ if (getenv("USEARCH_DEBUG") != NULL) {
+ printf("Pattern CEs\n");
+ for (int ii=0; ii<strsrch->pattern.cesLength; ii++) {
+ printf(" %8x", strsrch->pattern.ces[ii]);
+ }
+ printf("\n");
+ }
+
+#endif
+ // Input parameter sanity check.
+ // TODO: should input indicies clip to the text length
+ // in the same way that UText does.
+ if(strsrch->pattern.cesLength == 0 ||
+ startIdx < 0 ||
+ startIdx > strsrch->search->textLength ||
+ strsrch->pattern.ces == NULL) {
+ *status = U_ILLEGAL_ARGUMENT_ERROR;
+ return FALSE;
+ }
+
+ if (strsrch->pattern.pces == NULL) {
+ initializePatternPCETable(strsrch, status);
+ }
+
+ ucol_setOffset(strsrch->textIter, startIdx, status);
+ CEIBuffer ceb(strsrch, status);
+
+
+ int32_t targetIx = 0;
+ const CEI *targetCEI = NULL;
+ int32_t patIx;
+ UBool found;
+
+ int32_t mStart = -1;
+ int32_t mLimit = -1;
+ int32_t minLimit;
+ int32_t maxLimit;
+
+
+
+ // Outer loop moves over match starting positions in the
+ // target CE space.
+ // Here we see the target as a sequence of collation elements, resulting from the following:
+ // 1. Target characters were decomposed, and (if appropriate) other compressions and expansions are applied
+ // (for example, digraphs such as IJ may be broken into two characters).
+ // 2. An int64_t CE weight is determined for each resulting unit (high 16 bits are primary strength, next
+ // 16 bits are secondary, next 16 (the high 16 bits of the low 32-bit half) are tertiary. Any of these
+ // fields that are for strengths below that of the collator are set to 0. If this makes the int64_t
+ // CE weight 0 (as for a combining diacritic with secondary weight when the collator strentgh is primary),
+ // then the CE is deleted, so the following code sees only CEs that are relevant.
+ // For each CE, the lowIndex and highIndex correspond to where this CE begins and ends in the original text.
+ // If lowIndex==highIndex, either the CE resulted from an expansion/decomposition of one of the original text
+ // characters, or the CE marks the limit of the target text (in which case the CE weight is UCOL_PROCESSED_NULLORDER).
+ //
+ for(targetIx=0; ; targetIx++)
+ {
+ found = TRUE;
+ // Inner loop checks for a match beginning at each
+ // position from the outer loop.
+ int32_t targetIxOffset = 0;
+ int64_t patCE = 0;
+ // For targetIx > 0, this ceb.get gets a CE that is as far back in the ring buffer
+ // (compared to the last CE fetched for the previous targetIx value) as we need to go
+ // for this targetIx value, so if it is non-NULL then other ceb.get calls should be OK.
+ const CEI *firstCEI = ceb.get(targetIx);
+ if (firstCEI == NULL) {
+ *status = U_INTERNAL_PROGRAM_ERROR;
+ found = FALSE;
+ break;
+ }
+
+ for (patIx=0; patIx<strsrch->pattern.pcesLength; patIx++) {
+ patCE = strsrch->pattern.pces[patIx];
+ targetCEI = ceb.get(targetIx+patIx+targetIxOffset);
+ // Compare CE from target string with CE from the pattern.
+ // Note that the target CE will be UCOL_PROCESSED_NULLORDER if we reach the end of input,
+ // which will fail the compare, below.
+ UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType);
+ if ( ceMatch == U_CE_NO_MATCH ) {
+ found = FALSE;
+ break;
+ } else if ( ceMatch > U_CE_NO_MATCH ) {
+ if ( ceMatch == U_CE_SKIP_TARG ) {
+ // redo with same patCE, next targCE
+ patIx--;
+ targetIxOffset++;
+ } else { // ceMatch == U_CE_SKIP_PATN
+ // redo with same targCE, next patCE
+ targetIxOffset--;
+ }
+ }
+ }
+ targetIxOffset += strsrch->pattern.pcesLength; // this is now the offset in target CE space to end of the match so far
+
+ if (!found && ((targetCEI == NULL) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) {
+ // No match at this targetIx. Try again at the next.
+ continue;
+ }
+
+ if (!found) {
+ // No match at all, we have run off the end of the target text.
+ break;
+ }
+
+
+ // We have found a match in CE space.
+ // Now determine the bounds in string index space.
+ // There still is a chance of match failure if the CE range not correspond to
+ // an acceptable character range.
+ //
+ const CEI *lastCEI = ceb.get(targetIx + targetIxOffset - 1);
+
+ mStart = firstCEI->lowIndex;
+ minLimit = lastCEI->lowIndex;
+
+ // Look at the CE following the match. If it is UCOL_NULLORDER the match
+ // extended to the end of input, and the match is good.
+
+ // Look at the high and low indices of the CE following the match. If
+ // they are the same it means one of two things:
+ // 1. The match extended to the last CE from the target text, which is OK, or
+ // 2. The last CE that was part of the match is in an expansion that extends
+ // to the first CE after the match. In this case, we reject the match.
+ const CEI *nextCEI = 0;
+ if (strsrch->search->elementComparisonType == 0) {
+ nextCEI = ceb.get(targetIx + targetIxOffset);
+ maxLimit = nextCEI->lowIndex;
+ if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
+ found = FALSE;
+ }
+ } else {
+ for ( ; ; ++targetIxOffset ) {
+ nextCEI = ceb.get(targetIx + targetIxOffset);
+ maxLimit = nextCEI->lowIndex;
+ // If we are at the end of the target too, match succeeds
+ if ( nextCEI->ce == UCOL_PROCESSED_NULLORDER ) {
+ break;
+ }
+ // As long as the next CE has primary weight of 0,
+ // it is part of the last target element matched by the pattern;
+ // make sure it can be part of a match with the last patCE
+ if ( (((nextCEI->ce) >> 32) & 0xFFFF0000UL) == 0 ) {
+ UCompareCEsResult ceMatch = compareCE64s(nextCEI->ce, patCE, strsrch->search->elementComparisonType);
+ if ( ceMatch == U_CE_NO_MATCH || ceMatch == U_CE_SKIP_PATN ) {
+ found = FALSE;
+ break;
+ }
+ // If lowIndex == highIndex, this target CE is part of an expansion of the last matched
+ // target element, but it has non-zero primary weight => match fails
+ } else if ( nextCEI->lowIndex == nextCEI->highIndex ) {
+ found = false;
+ break;
+ // Else the target CE is not part of an expansion of the last matched element, match succeeds
+ } else {
+ break;
+ }
+ }
+ }
+
+
+ // Check for the start of the match being within a combining sequence.
+ // This can happen if the pattern itself begins with a combining char, and
+ // the match found combining marks in the target text that were attached
+ // to something else.
+ // This type of match should be rejected for not completely consuming a
+ // combining sequence.
+ if (!isBreakBoundary(strsrch, mStart)) {
+ found = FALSE;
+ }
+
+ // 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;
+ }
+
+ // 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) {
+ mLimit = nba;
+ }
+ }
+ }
+
+ #ifdef USEARCH_DEBUG
+ if (getenv("USEARCH_DEBUG") != NULL) {
+ printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
+ }
+ #endif
+
+ // If default breakIter is being used, and next collation element belonging to this
+ // combining sequence has non-zero primary weight and corresponds to a separate
+ // character following the one at end of the current match, then do NOT require
+ // that match end position be on a breakIter boundary, or that end of the
+ // combining sequence not extend beyond the match in CE space. Only do those
+ // tests if the conditions above are not met. Added this to make prefix search
+ // work in Indic scripts per <rdar://problem/18063262>.
+ UBool doLimitTests = !(strsrch->search->breakIter == NULL &&
+ nextCEI != NULL && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 &&
+ nextCEI->lowIndex >= lastCEI->highIndex && nextCEI->highIndex > nextCEI->lowIndex);
+
+ if (doLimitTests) { // <rdar://problem/18063262>
+ // 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 (! checkIdentical(strsrch, mStart, mLimit)) {
+ found = FALSE;
+ }
+
+ if (found) {
+ break;
+ }
+ }
+
+ #ifdef USEARCH_DEBUG
+ if (getenv("USEARCH_DEBUG") != NULL) {
+ printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx);
+ int32_t lastToPrint = ceb.limitIx+2;
+ for (int ii=ceb.firstIx; ii<lastToPrint; ii++) {
+ printf("%8x@%d ", ceb.get(ii)->ce, ceb.get(ii)->srcIndex);
+ }
+ printf("\n%s\n", found? "match found" : "no match");
+ }
+ #endif
+
+ // All Done. Store back the match bounds to the caller.
+ //
+ if (found==FALSE) {
+ mLimit = -1;
+ mStart = -1;
+ }
+
+ if (matchStart != NULL) {
+ *matchStart= mStart;
+ }
+
+ if (matchLimit != NULL) {
+ *matchLimit = mLimit;
+ }
+
+ return found;
+}
+
+U_CAPI UBool U_EXPORT2 usearch_searchBackwards(UStringSearch *strsrch,
+ int32_t startIdx,
+ int32_t *matchStart,
+ int32_t *matchLimit,
+ UErrorCode *status)
+{
+ if (U_FAILURE(*status)) {
+ return FALSE;
+ }
+
+ // TODO: reject search patterns beginning with a combining char.
+
+#ifdef USEARCH_DEBUG
+ if (getenv("USEARCH_DEBUG") != NULL) {
+ printf("Pattern CEs\n");
+ for (int ii=0; ii<strsrch->pattern.cesLength; ii++) {
+ printf(" %8x", strsrch->pattern.ces[ii]);
+ }
+ printf("\n");
+ }
+
+#endif
+ // Input parameter sanity check.
+ // TODO: should input indicies clip to the text length
+ // in the same way that UText does.
+ if(strsrch->pattern.cesLength == 0 ||
+ startIdx < 0 ||
+ startIdx > strsrch->search->textLength ||
+ strsrch->pattern.ces == NULL) {
+ *status = U_ILLEGAL_ARGUMENT_ERROR;
+ return FALSE;
+ }
+
+ if (strsrch->pattern.pces == NULL) {
+ initializePatternPCETable(strsrch, status);
+ }
+
+ CEIBuffer ceb(strsrch, status);
+ int32_t targetIx = 0;
+
+ /*
+ * Pre-load the buffer with the CE's for the grapheme
+ * after our starting position so that we're sure that
+ * we can look at the CE following the match when we
+ * check the match boundaries.
+ *
+ * This will also pre-fetch the first CE that we'll
+ * consider for the match.
+ */
+ if (startIdx < strsrch->search->textLength) {
+ UBreakIterator *bi = strsrch->search->internalBreakIter;
+ int32_t next = ubrk_following(bi, startIdx);
+
+ ucol_setOffset(strsrch->textIter, next, status);
+
+ for (targetIx = 0; ; targetIx += 1) {
+ if (ceb.getPrevious(targetIx)->lowIndex < startIdx) {
+ break;
+ }
+ }
+ } else {
+ ucol_setOffset(strsrch->textIter, startIdx, status);
+ }
+
+
+ const CEI *targetCEI = NULL;
+ int32_t patIx;
+ UBool found;
+
+ int32_t limitIx = targetIx;
+ int32_t mStart = -1;
+ int32_t mLimit = -1;
+ int32_t minLimit;
+ int32_t maxLimit;
+
+
+
+ // Outer loop moves over match starting positions in the
+ // target CE space.
+ // Here, targetIx values increase toward the beginning of the base text (i.e. we get the text CEs in reverse order).
+ // But patIx is 0 at the beginning of the pattern and increases toward the end.
+ // So this loop performs a comparison starting with the end of pattern, and prcessd toward the beginning of the pattern
+ // and the beginning of the base text.
+ for(targetIx = limitIx; ; targetIx += 1)
+ {
+ found = TRUE;
+ // For targetIx > limitIx, this ceb.getPrevious gets a CE that is as far back in the ring buffer
+ // (compared to the last CE fetched for the previous targetIx value) as we need to go
+ // for this targetIx value, so if it is non-NULL then other ceb.getPrevious calls should be OK.
+ const CEI *lastCEI = ceb.getPrevious(targetIx);
+ if (lastCEI == NULL) {
+ *status = U_INTERNAL_PROGRAM_ERROR;
+ found = FALSE;
+ break;
+ }
+ // Inner loop checks for a match beginning at each
+ // position from the outer loop.
+ int32_t targetIxOffset = 0;
+ for (patIx = strsrch->pattern.pcesLength - 1; patIx >= 0; patIx -= 1) {
+ int64_t patCE = strsrch->pattern.pces[patIx];
+
+ targetCEI = ceb.getPrevious(targetIx + strsrch->pattern.pcesLength - 1 - patIx + targetIxOffset);
+ // Compare CE from target string with CE from the pattern.
+ // Note that the target CE will be UCOL_NULLORDER if we reach the end of input,
+ // which will fail the compare, below.
+ UCompareCEsResult ceMatch = compareCE64s(targetCEI->ce, patCE, strsrch->search->elementComparisonType);
+ if ( ceMatch == U_CE_NO_MATCH ) {
+ found = FALSE;
+ break;
+ } else if ( ceMatch > U_CE_NO_MATCH ) {
+ if ( ceMatch == U_CE_SKIP_TARG ) {
+ // redo with same patCE, next targCE
+ patIx++;
+ targetIxOffset++;
+ } else { // ceMatch == U_CE_SKIP_PATN
+ // redo with same targCE, next patCE
+ targetIxOffset--;
+ }
+ }
+ }
+
+ if (!found && ((targetCEI == NULL) || (targetCEI->ce != UCOL_PROCESSED_NULLORDER))) {
+ // No match at this targetIx. Try again at the next.
+ continue;
+ }
+
+ if (!found) {
+ // No match at all, we have run off the end of the target text.
+ break;
+ }
+
+
+ // We have found a match in CE space.
+ // Now determine the bounds in string index space.
+ // There still is a chance of match failure if the CE range not correspond to
+ // an acceptable character range.
+ //
+ const CEI *firstCEI = ceb.getPrevious(targetIx + strsrch->pattern.pcesLength - 1 + targetIxOffset);
+ mStart = firstCEI->lowIndex;
+
+ // Check for the start of the match being within a combining sequence.
+ // This can happen if the pattern itself begins with a combining char, and
+ // the match found combining marks in the target text that were attached
+ // to something else.
+ // This type of match should be rejected for not completely consuming a
+ // combining sequence.
+ if (!isBreakBoundary(strsrch, mStart)) {
+ found = FALSE;
+ }
+
+ // Look at the high index of the first CE in the match. If it's the same as the
+ // low index, the first CE in the match is in the middle of an expansion.
+ if (mStart == firstCEI->highIndex) {
+ found = FALSE;
+ }
+
+
+ minLimit = lastCEI->lowIndex;
+
+ if (targetIx > 0) {
+ // Look at the CE following the match. If it is UCOL_NULLORDER the match
+ // extended to the end of input, and the match is good.
+
+ // Look at the high and low indices of the CE following the match. If
+ // they are the same it means one of two things:
+ // 1. The match extended to the last CE from the target text, which is OK, or
+ // 2. The last CE that was part of the match is in an expansion that extends
+ // to the first CE after the match. In this case, we reject the match.
+ const CEI *nextCEI = ceb.getPrevious(targetIx - 1);
+
+ if (nextCEI->lowIndex == nextCEI->highIndex && nextCEI->ce != UCOL_PROCESSED_NULLORDER) {
+ found = FALSE;
+ }
+
+ mLimit = maxLimit = nextCEI->lowIndex;
+
+ // Advance the match end position to the first acceptable match boundary.
+ // This advances the index over any combining characters.
+ if (minLimit < maxLimit) {
+ int32_t nba = nextBoundaryAfter(strsrch, minLimit);
+
+ if (nba >= lastCEI->highIndex) {
+ mLimit = nba;
+ }
+ }
+
+ // If default breakIter is being used, and next collation element belonging to this
+ // combining sequence has non-zero primary weight and corresponds to a separate
+ // character following the one at end of the current match, then do NOT require
+ // that match end position be on a breakIter boundary, or that end of the
+ // combining sequence not extend beyond the match in CE space. Only do those
+ // tests if the conditions above are not met. Added this to make prefix search
+ // work in Indic scripts per <rdar://problem/18063262>.
+ UBool doLimitTests = !(strsrch->search->breakIter == NULL &&
+ nextCEI != NULL && (((nextCEI->ce) >> 32) & 0xFFFF0000UL) != 0 &&
+ nextCEI->lowIndex >= lastCEI->highIndex && nextCEI->highIndex > nextCEI->lowIndex);
+
+ if (doLimitTests) { // <rdar://problem/18063262>
+ // 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;
+ }
+ }
+
+ } 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;
+ }
+
+ #ifdef USEARCH_DEBUG
+ if (getenv("USEARCH_DEBUG") != NULL) {
+ printf("minLimit, maxLimit, mLimit = %d, %d, %d\n", minLimit, maxLimit, mLimit);
+ }
+ #endif
+
+
+ if (! checkIdentical(strsrch, mStart, mLimit)) {
+ found = FALSE;
+ }
+
+ if (found) {
+ break;
+ }
+ }
+
+ #ifdef USEARCH_DEBUG
+ if (getenv("USEARCH_DEBUG") != NULL) {
+ printf("Target CEs [%d .. %d]\n", ceb.firstIx, ceb.limitIx);
+ int32_t lastToPrint = ceb.limitIx+2;
+ for (int ii=ceb.firstIx; ii<lastToPrint; ii++) {
+ printf("%8x@%d ", ceb.get(ii)->ce, ceb.get(ii)->srcIndex);
+ }
+ printf("\n%s\n", found? "match found" : "no match");
+ }
+ #endif
+
+ // All Done. Store back the match bounds to the caller.
+ //
+ if (found==FALSE) {
+ mLimit = -1;
+ mStart = -1;
+ }
+
+ if (matchStart != NULL) {
+ *matchStart= mStart;
+ }
+
+ if (matchLimit != NULL) {
+ *matchLimit = mLimit;
+ }
+
+ return found;
+}
+
projects / apple / icu.git / blobdiff