WebCore:
authordarin@apple.com <darin@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 1 Jan 2009 21:19:59 +0000 (21:19 +0000)
committerdarin@apple.com <darin@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 1 Jan 2009 21:19:59 +0000 (21:19 +0000)
2009-01-01  Darin Adler  <darin@apple.com>

        Reviewed by Dan Bernstein.

        Bug 23051: web page searching should use ICU's search so it can ignore diacritical differences
        https://bugs.webkit.org/show_bug.cgi?id=23051
        rdar://problem/3574497

        Test: editing/execCommand/findString-diacriticals.html

        * editing/TextIterator.cpp: Changed the CircularSearchBuffer class to have a new
        name, since it doesn't always use a circular buffer any more. Changed the interface
        so it can work well in the new chunky comparison mode for ICU search, and also
        added private data members for both the ICU-search and non-ICU-search code paths.
        (WebCore::TextIterator::TextIterator): Use the versions of the Range functions
        that don't take an exception code.
        (WebCore::TextIterator::handleTextBox): Added a special case to handle the position
        of a collapsed-away space better. This is not needed for search mechanism, but was
        helpful in an earlier version of this patch, and is still an improvement.
        (WebCore::SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator): Use the
        versions of the Range functions that don't take an exception code.
        (WebCore::CharacterIterator::range): Ditto.
        (WebCore::characterSubrange): Added. Helper function used in both places below where
        we want to convert a range and character offsets into a subrange.
        (WebCore::WordAwareIterator::advance): Use the versions of the Range functions that
        don't take an exception code.
        (WebCore::createSearcher): Added.
        (WebCore::searcher): Added.
        (WebCore::lockSearcher): Added.
        (WebCore::unlockSearcher): Added.
        (WebCore::SearchBuffer::SearchBuffer): Added.
        (WebCore::SearchBuffer::~SearchBuffer): Added.
        (WebCore::SearchBuffer::append): Added.
        (WebCore::SearchBuffer::atBreak): Added.
        (WebCore::SearchBuffer::reachedBreak): Added.
        (WebCore::SearchBuffer::search): Added.
        (WebCore::SearchBuffer::length): Added.
        (WebCore::TextIterator::subrange): Changed to call the characterSubrange
        function above.
        (WebCore::TextIterator::rangeFromLocationAndLength): Use the versions of the
        Range functions that don't take an exception code. Also tweak some other details
        of the code.
        (WebCore::isAllCollapsibleWhitespace): Added.
        (WebCore::collapsedToBoundary): Added.
        (WebCore::findPlainText): Rewrote to use new interface and streamline the
        logic a bit.

        Add the relevant files in the icu directory. As icu/README says, the "icu"
        directory is really just for Mac OS X, where we have the ICU library but not
        the headers installed. It should be moved inside platform/mac at some point
        to make this more clear (and the copy in JavaScriptCore should be moved
        somewhere similar for the same reason).

        * icu/unicode/ucoleitr.h: Added.
        * icu/unicode/usearch.h: Added.

LayoutTests:

2009-01-01  Darin Adler  <darin@apple.com>

        Reviewed by Dan Bernstein.

        Bug 23051: web page searching should use ICU's search so it can ignore diacritical differences
        https://bugs.webkit.org/show_bug.cgi?id=23051
        rdar://problem/3574497

        Currently this is only activated on the Mac platform, not including Tiger.

        * editing/execCommand/findString-diacriticals-expected.txt: Added. Expect failure.
        * editing/execCommand/findString-diacriticals.html: Added.
        * platform/mac-tiger/editing/execCommand: Added.
        * platform/mac-tiger/editing/execCommand/findString-diacriticals-expected.txt: Added. Expect failure.
        * platform/mac/editing/execCommand/findString-diacriticals-expected.txt: Added. Expect success.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@39536 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/editing/execCommand/findString-diacriticals-expected.txt [new file with mode: 0644]
LayoutTests/editing/execCommand/findString-diacriticals.html [new file with mode: 0644]
LayoutTests/platform/mac-tiger/editing/execCommand/findString-diacriticals-expected.txt [new file with mode: 0644]
LayoutTests/platform/mac/editing/execCommand/findString-diacriticals-expected.txt [new file with mode: 0644]
WebCore/ChangeLog
WebCore/editing/TextIterator.cpp
WebCore/icu/unicode/ucoleitr.h [new file with mode: 0644]
WebCore/icu/unicode/usearch.h [new file with mode: 0644]

index fd3f690ab785d862de67d88d36d55d480cbd5a5e..051579a285220a70fb6d3f3c5cb5ea8459187c21 100644 (file)
@@ -1,3 +1,19 @@
+2009-01-01  Darin Adler  <darin@apple.com>
+
+        Reviewed by Dan Bernstein.
+
+        Bug 23051: web page searching should use ICU's search so it can ignore diacritical differences
+        https://bugs.webkit.org/show_bug.cgi?id=23051
+        rdar://problem/3574497
+
+        Currently this is only activated on the Mac platform, not including Tiger.
+
+        * editing/execCommand/findString-diacriticals-expected.txt: Added. Expect failure.
+        * editing/execCommand/findString-diacriticals.html: Added.
+        * platform/mac-tiger/editing/execCommand: Added.
+        * platform/mac-tiger/editing/execCommand/findString-diacriticals-expected.txt: Added. Expect failure.
+        * platform/mac/editing/execCommand/findString-diacriticals-expected.txt: Added. Expect success.
+
 2008-12-31  Oliver Hunt  <oliver@apple.com>
 
         Reviewed by Cameron Zwarich.
diff --git a/LayoutTests/editing/execCommand/findString-diacriticals-expected.txt b/LayoutTests/editing/execCommand/findString-diacriticals-expected.txt
new file mode 100644 (file)
index 0000000..231dfe7
--- /dev/null
@@ -0,0 +1,5 @@
+Test for https://bugs.webkit.org/show_bug.cgi?id=23051 web page searching should use ICU's search so it can ignore diacritical differences.
+
+The word "sélect" should be selected.
+
+FAIL
diff --git a/LayoutTests/editing/execCommand/findString-diacriticals.html b/LayoutTests/editing/execCommand/findString-diacriticals.html
new file mode 100644 (file)
index 0000000..edcdcf9
--- /dev/null
@@ -0,0 +1,17 @@
+<p>
+    Test for <i><a href="https://bugs.webkit.org/show_bug.cgi?id=23051">https://bugs.webkit.org/show_bug.cgi?id=23051</a>
+    web page searching should use ICU's search so it can ignore diacritical differences</i>.
+</p>
+<p>
+    The word "s&eacute;lect" should be selected.
+</p>
+<hr>
+<p id="result">
+    FAIL
+</p>
+<script>
+    if (window.layoutTestController)
+        layoutTestController.dumpAsText();
+    if (document.execCommand("FindString", false, "Sel" + String.fromCharCode(0x00CB) + "ct"))
+        document.getElementById("result").innerText = "PASS";
+</script>
diff --git a/LayoutTests/platform/mac-tiger/editing/execCommand/findString-diacriticals-expected.txt b/LayoutTests/platform/mac-tiger/editing/execCommand/findString-diacriticals-expected.txt
new file mode 100644 (file)
index 0000000..231dfe7
--- /dev/null
@@ -0,0 +1,5 @@
+Test for https://bugs.webkit.org/show_bug.cgi?id=23051 web page searching should use ICU's search so it can ignore diacritical differences.
+
+The word "sélect" should be selected.
+
+FAIL
diff --git a/LayoutTests/platform/mac/editing/execCommand/findString-diacriticals-expected.txt b/LayoutTests/platform/mac/editing/execCommand/findString-diacriticals-expected.txt
new file mode 100644 (file)
index 0000000..bd766d8
--- /dev/null
@@ -0,0 +1,5 @@
+Test for https://bugs.webkit.org/show_bug.cgi?id=23051 web page searching should use ICU's search so it can ignore diacritical differences.
+
+The word "sélect" should be selected.
+
+PASS
index e8db01a67a6449866c363ae8e253422af2f8d105..ec3e937c97c59521d81c859193d42560a2ca4361 100644 (file)
@@ -1,3 +1,59 @@
+2009-01-01  Darin Adler  <darin@apple.com>
+
+        Reviewed by Dan Bernstein.
+
+        Bug 23051: web page searching should use ICU's search so it can ignore diacritical differences
+        https://bugs.webkit.org/show_bug.cgi?id=23051
+        rdar://problem/3574497
+
+        Test: editing/execCommand/findString-diacriticals.html
+
+        * editing/TextIterator.cpp: Changed the CircularSearchBuffer class to have a new
+        name, since it doesn't always use a circular buffer any more. Changed the interface
+        so it can work well in the new chunky comparison mode for ICU search, and also
+        added private data members for both the ICU-search and non-ICU-search code paths.
+        (WebCore::TextIterator::TextIterator): Use the versions of the Range functions
+        that don't take an exception code.
+        (WebCore::TextIterator::handleTextBox): Added a special case to handle the position
+        of a collapsed-away space better. This is not needed for search mechanism, but was
+        helpful in an earlier version of this patch, and is still an improvement.
+        (WebCore::SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator): Use the
+        versions of the Range functions that don't take an exception code.
+        (WebCore::CharacterIterator::range): Ditto.
+        (WebCore::characterSubrange): Added. Helper function used in both places below where
+        we want to convert a range and character offsets into a subrange.
+        (WebCore::WordAwareIterator::advance): Use the versions of the Range functions that
+        don't take an exception code.
+        (WebCore::createSearcher): Added.
+        (WebCore::searcher): Added.
+        (WebCore::lockSearcher): Added.
+        (WebCore::unlockSearcher): Added.
+        (WebCore::SearchBuffer::SearchBuffer): Added.
+        (WebCore::SearchBuffer::~SearchBuffer): Added.
+        (WebCore::SearchBuffer::append): Added.
+        (WebCore::SearchBuffer::atBreak): Added.
+        (WebCore::SearchBuffer::reachedBreak): Added.
+        (WebCore::SearchBuffer::search): Added.
+        (WebCore::SearchBuffer::length): Added.
+        (WebCore::TextIterator::subrange): Changed to call the characterSubrange
+        function above.
+        (WebCore::TextIterator::rangeFromLocationAndLength): Use the versions of the
+        Range functions that don't take an exception code. Also tweak some other details
+        of the code.
+        (WebCore::isAllCollapsibleWhitespace): Added.
+        (WebCore::collapsedToBoundary): Added.
+        (WebCore::findPlainText): Rewrote to use new interface and streamline the
+        logic a bit.
+
+        Add the relevant files in the icu directory. As icu/README says, the "icu"
+        directory is really just for Mac OS X, where we have the ICU library but not
+        the headers installed. It should be moved inside platform/mac at some point
+        to make this more clear (and the copy in JavaScriptCore should be moved
+        somewhere similar for the same reason).
+
+        * icu/unicode/ucoleitr.h: Added.
+        * icu/unicode/usearch.h: Added.
+
 2009-01-01  Oliver Hunt  <oliver@apple.com>
 
         Reviewed by Cameron Zwarich.
index 2a705ed59b607a5c2571b4f63d682f38677a9e65..fa641742672a34be78c810249a83a4e4b3d5f813 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
+ * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
  * Copyright (C) 2005 Alexey Proskuryakov.
  *
  * Redistribution and use in source and binary forms, with or without
 #include "RenderTextControl.h"
 #include "visible_units.h"
 
+#if PLATFORM(MAC) && !defined(BUILDING_ON_TIGER)
+#define HAVE_ICU_SEARCH 1
+#endif
+
+#if HAVE(ICU_SEARCH)
+#include <unicode/usearch.h>
+#endif
+
 using namespace std;
 using namespace WTF::Unicode;
 
@@ -49,26 +57,47 @@ using namespace HTMLNames;
 
 // Buffer that knows how to compare with a search target.
 // Keeps enough of the previous text to be able to search in the future, but no more.
-class CircularSearchBuffer : Noncopyable {
+// Non-breaking spaces are always equal to normal spaces.
+// Case folding is also done if <isCaseSensitive> is false.
+class SearchBuffer : Noncopyable {
 public:
-    CircularSearchBuffer(const String& target, bool isCaseSensitive);
+    SearchBuffer(const String& target, bool isCaseSensitive);
+    ~SearchBuffer();
+
+    // Returns number of characters appended; guaranteed to be in the range [1, length].
+    size_t append(const UChar*, size_t length);
+    void reachedBreak();
 
-    void clear() { m_cursor = 0; m_isBufferFull = false; }
-    void append(UChar);
+    // Result is the size in characters of what was found.
+    // And <startOffset> is the number of charactesrs back to the start of what was found.
+    size_t search(size_t& startOffset);
+    bool atBreak() const;
+
+#if HAVE(ICU_SEARCH)
+
+private:
+    String m_target;
+    Vector<UChar> m_buffer;
+    size_t m_overlap;
+    bool m_atBreak;
 
-    bool isMatch() const;
-    unsigned length() const;
+#else
 
 private:
     void append(UChar, bool isCharacterStart);
+    size_t length() const;
 
     String m_target;
     bool m_isCaseSensitive;
 
-    Vector<UChar> m_characterBuffer;
+    Vector<UChar> m_buffer;
     Vector<bool> m_isCharacterStartBuffer;
     bool m_isBufferFull;
-    unsigned m_cursor;
+    size_t m_cursor;
+
+    bool m_atBreak;
+
+#endif
 };
 
 // --------
@@ -98,14 +127,12 @@ TextIterator::TextIterator(const Range* r, bool emitCharactersBetweenAllVisibleP
     if (!r)
         return;
 
-    ExceptionCode ec = 0;
-    
     // get and validate the range endpoints
-    Node *startContainer = r->startContainer(ec);
-    int startOffset = r->startOffset(ec);
-    Node *endContainer = r->endContainer(ec);
-    int endOffset = r->endOffset(ec);
-    if (ec)
+    Node* startContainer = r->startContainer();
+    int startOffset = r->startOffset();
+    Node* endContainer = r->endContainer();
+    int endOffset = r->endOffset();
+    if (!startContainer)
         return;
 
     // Callers should be handing us well-formed ranges. If we discover that this isn't
@@ -324,7 +351,13 @@ void TextIterator::handleTextBox()
         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {
-            emitCharacter(' ', m_node, 0, runStart, runStart);
+            if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {
+                unsigned spaceRunStart = runStart - 1;
+                while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')
+                    --spaceRunStart;
+                emitText(m_node, spaceRunStart, runStart);
+            } else
+                emitCharacter(' ', m_node, 0, runStart, runStart);
             return;
         }
         int textBoxEnd = textBoxStart + m_textBox->m_len;
@@ -749,18 +782,11 @@ SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range *r)
     if (!r)
         return;
 
-    int exception = 0;
-    Node *startNode = r->startContainer(exception);
-    if (exception)
-        return;
-    Node *endNode = r->endContainer(exception);
-    if (exception)
-        return;
-    int startOffset = r->startOffset(exception);
-    if (exception)
-        return;
-    int endOffset = r->endOffset(exception);
-    if (exception)
+    Node* startNode = r->startContainer();
+    Node* endNode = r->endContainer();
+    int startOffset = r->startOffset();
+    int endOffset = r->endOffset();
+    if (!startNode)
         return;
 
     if (!startNode->offsetInCharacters()) {
@@ -976,12 +1002,13 @@ PassRefPtr<Range> CharacterIterator::range() const
         if (m_textIterator.length() <= 1) {
             ASSERT(m_runOffset == 0);
         } else {
-            int exception = 0;
-            Node *n = r->startContainer(exception);
-            ASSERT(n == r->endContainer(exception));
-            int offset = r->startOffset(exception) + m_runOffset;
-            r->setStart(n, offset, exception);
-            r->setEnd(n, offset + 1, exception);
+            Node* n = r->startContainer();
+            ASSERT(n == r->endContainer());
+            int offset = r->startOffset() + m_runOffset;
+            ExceptionCode ec = 0;
+            r->setStart(n, offset, ec);
+            r->setEnd(n, offset + 1, ec);
+            ASSERT(!ec);
         }
     }
     return r.release();
@@ -1045,6 +1072,20 @@ String CharacterIterator::string(int numChars)
     return String::adopt(result);
 }
 
+static PassRefPtr<Range> characterSubrange(CharacterIterator& it, int offset, int length)
+{
+    it.advance(offset);
+    RefPtr<Range> start = it.range();
+
+    if (length > 1)
+        it.advance(length - 1);
+    RefPtr<Range> end = it.range();
+
+    return Range::create(start->startContainer()->document(), 
+        start->startContainer(), start->startOffset(), 
+        end->endContainer(), end->endOffset());
+}
+
 // --------
 
 WordAwareIterator::WordAwareIterator()
@@ -1113,7 +1154,7 @@ void WordAwareIterator::advance()
         }
         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
         int exception = 0;
-        m_range->setEnd(m_textIterator.range()->endContainer(exception), m_textIterator.range()->endOffset(exception), exception);
+        m_range->setEnd(m_textIterator.range()->endContainer(), m_textIterator.range()->endOffset(), exception);
     }
 }
 
@@ -1137,10 +1178,155 @@ const UChar* WordAwareIterator::characters() const
 
 // --------
 
-CircularSearchBuffer::CircularSearchBuffer(const String& s, bool isCaseSensitive)
-    : m_target(isCaseSensitive ? s : s.foldCase())
+#if HAVE(ICU_SEARCH)
+
+static const size_t minimumSearchBufferSize = 8192;
+
+#ifndef NDEBUG
+static bool searcherInUse;
+#endif
+
+static UStringSearch* createSearcher()
+{
+    // Provide a non-empty pattern and non-empty text so usearch_open will not fail,
+    // but it doesn't matter exactly what it is, since we don't perform any searches
+    // without setting both the pattern and the text.
+
+    // Pass empty string for the locale for now to get the Unicode Collation Algorithm,
+    // rather than something locale-specific.
+
+    UErrorCode status = U_ZERO_ERROR;
+    UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, "", 0, &status);
+    ASSERT(status == U_ZERO_ERROR);
+    return searcher;
+}
+
+static UStringSearch* searcher()
+{
+    static UStringSearch* searcher = createSearcher();
+    return searcher;
+}
+
+static inline void lockSearcher()
+{
+#ifndef NDEBUG
+    ASSERT(!searcherInUse);
+    searcherInUse = true;
+#endif
+}
+
+static inline void unlockSearcher()
+{
+#ifndef NDEBUG
+    ASSERT(searcherInUse);
+    searcherInUse = false;
+#endif
+}
+
+inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
+    : m_target(target)
+    , m_atBreak(true)
+{
+    ASSERT(!m_target.isEmpty());
+
+    size_t targetLength = target.length();
+    m_buffer.reserveCapacity(max(targetLength * 8, minimumSearchBufferSize));
+    m_overlap = m_buffer.capacity() / 4;
+
+    // Grab the single global searcher.
+    // If we ever have a reason to do more than once search buffer at once, we'll have
+    // to move to multiple searchers.
+    lockSearcher();
+
+    UStringSearch* searcher = WebCore::searcher();
+    UCollator* collator = usearch_getCollator(searcher);
+
+    UCollationStrength strength = isCaseSensitive ? UCOL_TERTIARY : UCOL_PRIMARY;
+    if (ucol_getStrength(collator) != strength) {
+        ucol_setStrength(collator, strength);
+        usearch_reset(searcher);
+    }
+
+    UErrorCode status = U_ZERO_ERROR;
+    usearch_setPattern(searcher, m_target.characters(), targetLength, &status);
+    ASSERT(status == U_ZERO_ERROR);
+}
+
+inline SearchBuffer::~SearchBuffer()
+{
+    unlockSearcher();
+}
+
+inline size_t SearchBuffer::append(const UChar* characters, size_t length)
+{
+    ASSERT(length);
+
+    if (m_atBreak) {
+        m_buffer.shrink(0);
+        m_atBreak = false;
+    } else if (m_buffer.size() == m_buffer.capacity()) {
+        memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap);
+        m_buffer.shrink(m_overlap);
+    }
+
+    size_t usableLength = min(m_buffer.capacity() - m_buffer.size(), length);
+    ASSERT(usableLength);
+    m_buffer.append(characters, usableLength);
+    return usableLength;
+}
+
+inline bool SearchBuffer::atBreak() const
+{
+    return m_atBreak;
+}
+
+inline void SearchBuffer::reachedBreak()
+{
+    m_atBreak = true;
+}
+
+inline size_t SearchBuffer::search(size_t& start)
+{
+    size_t size = m_buffer.size();
+    if (!m_atBreak && size < m_buffer.capacity())
+        return 0;
+
+    UStringSearch* searcher = WebCore::searcher();
+
+    UErrorCode status = U_ZERO_ERROR;
+    usearch_setText(searcher, m_buffer.data(), size, &status);
+    ASSERT(status == U_ZERO_ERROR);
+
+    int matchStart = usearch_first(searcher, &status);
+    ASSERT(status == U_ZERO_ERROR);
+    if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
+        ASSERT(matchStart == USEARCH_DONE);
+        return 0;
+    }
+
+    // Matches that start in the overlap area are only tentative.
+    // The same match may appear later, matching more characters,
+    // possibly including a combining character that's not yet in the buffer.
+    if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
+        memcpy(m_buffer.data(), m_buffer.data() + size - m_overlap, m_overlap);
+        m_buffer.shrink(m_overlap);
+        return 0;
+    }
+
+    size_t newSize = size - (matchStart + 1);
+    memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize);
+    m_buffer.shrink(newSize);
+
+    start = size - matchStart;
+    return usearch_getMatchedLength(searcher);
+}
+
+#else
+
+inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
+    : m_target(isCaseSensitive ? target : target.foldCase())
     , m_isCaseSensitive(isCaseSensitive)
-    , m_characterBuffer(m_target.length())
+    , m_buffer(m_target.length())
     , m_isCharacterStartBuffer(m_target.length())
     , m_isBufferFull(false)
     , m_cursor(0)
@@ -1149,9 +1335,24 @@ CircularSearchBuffer::CircularSearchBuffer(const String& s, bool isCaseSensitive
     m_target.replace(noBreakSpace, ' ');
 }
 
-inline void CircularSearchBuffer::append(UChar c, bool isStart)
+inline SearchBuffer::~SearchBuffer()
+{
+}
+
+inline void SearchBuffer::reachedBreak()
+{
+    m_cursor = 0;
+    m_isBufferFull = false;
+}
+
+inline bool SearchBuffer::atBreak() const
 {
-    m_characterBuffer[m_cursor] = c == noBreakSpace ? ' ' : c;
+    return !m_cursor && !m_isBufferFull;
+}
+
+inline void SearchBuffer::append(UChar c, bool isStart)
+{
+    m_buffer[m_cursor] = c == noBreakSpace ? ' ' : c;
     m_isCharacterStartBuffer[m_cursor] = isStart;
     if (++m_cursor == m_target.length()) {
         m_cursor = 0;
@@ -1159,16 +1360,17 @@ inline void CircularSearchBuffer::append(UChar c, bool isStart)
     }
 }
 
-inline void CircularSearchBuffer::append(UChar c)
+inline size_t SearchBuffer::append(const UChar* characters, size_t length)
 {
+    ASSERT(length);
     if (m_isCaseSensitive) {
-        append(c, true);
-        return;
+        append(characters[0], true);
+        return 1;
     }
     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
     UChar foldedCharacters[maxFoldedCharacters];
     bool error;
-    int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, &c, 1, &error);
+    int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, characters, 1, &error);
     ASSERT(!error);
     ASSERT(numFoldedCharacters);
     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
@@ -1178,34 +1380,40 @@ inline void CircularSearchBuffer::append(UChar c)
         for (int i = 1; i < numFoldedCharacters; ++i)
             append(foldedCharacters[i], false);
     }
+    return 1;
 }
 
-inline bool CircularSearchBuffer::isMatch() const
+inline size_t SearchBuffer::search(size_t& start)
 {
     if (!m_isBufferFull)
-        return false;
+        return 0;
     if (!m_isCharacterStartBuffer[m_cursor])
-        return false;
+        return 0;
 
-    unsigned tailSpace = m_target.length() - m_cursor;
-    return memcmp(&m_characterBuffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) == 0
-        && memcmp(&m_characterBuffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) == 0;
+    size_t tailSpace = m_target.length() - m_cursor;
+    if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0)
+        return 0;
+    if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0)
+        return 0;
+
+    start = length();
+    return start;
 }
 
 // Returns the number of characters that were appended to the buffer (what we are searching in).
 // That's not necessarily the same length as the passed-in target string, because case folding
 // can make two strings match even though they're not the same length.
-unsigned CircularSearchBuffer::length() const
+size_t SearchBuffer::length() const
 {
-    ASSERT(isMatch());
-
-    unsigned bufferSize = m_target.length();
-    unsigned length = 0;
-    for (unsigned i = 0; i < bufferSize; ++i)
+    size_t bufferSize = m_target.length();
+    size_t length = 0;
+    for (size_t i = 0; i < bufferSize; ++i)
         length += m_isCharacterStartBuffer[i];
     return length;
 }
 
+#endif
+
 // --------
 
 int TextIterator::rangeLength(const Range *r, bool forSelectionPreservation)
@@ -1219,23 +1427,8 @@ int TextIterator::rangeLength(const Range *r, bool forSelectionPreservation)
 
 PassRefPtr<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
 {
-    CharacterIterator chars(entireRange);
-
-    chars.advance(characterOffset);
-    RefPtr<Range> start = chars.range();
-
-    chars.advance(characterCount);
-    RefPtr<Range> end = chars.range();
-    
-    ExceptionCode ec = 0;
-    RefPtr<Range> result(Range::create(entireRange->ownerDocument(), 
-                                    start->startContainer(ec), 
-                                    start->startOffset(ec), 
-                                    end->startContainer(ec), 
-                                    end->startOffset(ec)));
-    ASSERT(!ec);
-    
-    return result.release();
+    CharacterIterator entireRangeIterator(entireRange);
+    return characterSubrange(entireRangeIterator, characterOffset, characterCount);
 }
 
 PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
@@ -1252,13 +1445,13 @@ PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int r
     
     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
     if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) {
-        int exception = 0;
         textRunRange = it.range();
         
-        resultRange->setStart(textRunRange->startContainer(exception), 0, exception);
-        ASSERT(exception == 0);
-        resultRange->setEnd(textRunRange->startContainer(exception), 0, exception);
-        ASSERT(exception == 0);
+        ExceptionCode ec = 0;
+        resultRange->setStart(textRunRange->startContainer(), 0, ec);
+        ASSERT(!ec);
+        resultRange->setEnd(textRunRange->startContainer(), 0, ec);
+        ASSERT(!ec);
         
         return resultRange.release();
     }
@@ -1275,12 +1468,13 @@ PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int r
         if (foundStart || foundEnd) {
             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
             // position for emitted '\n's.
-            if (len == 1 && it.characters()[0] == UChar('\n')) {
+            if (len == 1 && it.characters()[0] == '\n') {
                 Position runStart = textRunRange->startPosition();
                 Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
                 if (runEnd.isNotNull()) {
                     ExceptionCode ec = 0;
                     textRunRange->setEnd(runEnd.node(), runEnd.offset(), ec);
+                    ASSERT(!ec);
                 }
             }
         }
@@ -1288,27 +1482,27 @@ PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int r
         if (foundStart) {
             startRangeFound = true;
             int exception = 0;
-            if (textRunRange->startContainer(exception)->isTextNode()) {
+            if (textRunRange->startContainer()->isTextNode()) {
                 int offset = rangeLocation - docTextPosition;
-                resultRange->setStart(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
+                resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
             } else {
                 if (rangeLocation == docTextPosition)
-                    resultRange->setStart(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
+                    resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset(), exception);
                 else
-                    resultRange->setStart(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
+                    resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset(), exception);
             }
         }
 
         if (foundEnd) {
             int exception = 0;
-            if (textRunRange->startContainer(exception)->isTextNode()) {
+            if (textRunRange->startContainer()->isTextNode()) {
                 int offset = rangeEnd - docTextPosition;
-                resultRange->setEnd(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
+                resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
             } else {
                 if (rangeEnd == docTextPosition)
-                    resultRange->setEnd(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
+                    resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset(), exception);
                 else
-                    resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
+                    resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
             }
             docTextPosition += len;
             break;
@@ -1321,7 +1515,7 @@ PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int r
     
     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
         int exception = 0;
-        resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
+        resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
     }
     
     return resultRange.release();
@@ -1398,56 +1592,80 @@ String plainText(const Range* r)
     return result;
 }
 
-PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
+static inline bool isAllCollapsibleWhitespace(const String& string)
 {
-    // FIXME: Can we do Boyer-Moore or equivalent instead for speed?
+    const UChar* characters = string.characters();
+    unsigned length = string.length();
+    for (unsigned i = 0; i < length; ++i) {
+        if (!isCollapsibleWhitespace(characters[i]))
+            return false;
+    }
+    return true;
+}
 
+static PassRefPtr<Range> collapsedToBoundary(const Range* range, bool forward)
+{
     ExceptionCode ec = 0;
     RefPtr<Range> result = range->cloneRange(ec);
+    ASSERT(!ec);
     result->collapse(!forward, ec);
+    ASSERT(!ec);
+    return result.release();
+}
 
-    // FIXME: This code does not allow \n at the moment because of issues with <br>.
-    // Once we fix those, we can remove this check.
-    if (target.isEmpty() || target.find('\n') != -1)
-        return result.release();
-
-    unsigned matchStart = 0;
-    unsigned matchLength = 0;
-    {
-        CircularSearchBuffer searchBuffer(target, caseSensitive);
-        CharacterIterator it(range, false, true);
-        for (;;) {
-            if (searchBuffer.isMatch()) {
-                // Note that we found a match, and where we found it.
-                unsigned matchEnd = it.characterOffset();
-                matchLength = searchBuffer.length();
-                ASSERT(matchLength);
-                ASSERT(matchEnd >= matchLength);
-                matchStart = matchEnd - matchLength;
-                // If searching forward, stop on the first match.
-                // If searching backward, don't stop, so we end up with the last match.
-                if (forward)
-                    break;
-            }
-            if (it.atBreak()) {
-                if (it.atEnd())
-                    break;
-                searchBuffer.clear();
-            }
-            searchBuffer.append(it.characters()[0]);
-            it.advance(1);
+static size_t findPlainText(CharacterIterator& it, const String& target, bool forward, bool caseSensitive, size_t& matchStart)
+{
+    matchStart = 0;
+    size_t matchLength = 0;
+
+    SearchBuffer buffer(target, caseSensitive);
+
+    while (!it.atEnd()) {
+        it.advance(buffer.append(it.characters(), it.length()));
+tryAgain:
+        size_t matchStartOffset;
+        if (size_t newMatchLength = buffer.search(matchStartOffset)) {
+            // Note that we found a match, and where we found it.
+            size_t lastCharacterInBufferOffset = it.characterOffset();
+            ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
+            matchStart = lastCharacterInBufferOffset - matchStartOffset;
+            matchLength = newMatchLength;
+            // If searching forward, stop on the first match.
+            // If searching backward, don't stop, so we end up with the last match.
+            if (forward)
+                break;
+        }
+        if (it.atBreak() && !buffer.atBreak()) {
+            buffer.reachedBreak();
+            goto tryAgain;
         }
     }
 
-    if (matchLength) {
-        CharacterIterator it(range, false, true);
-        it.advance(matchStart);
-        result->setStart(it.range()->startContainer(ec), it.range()->startOffset(ec), ec);
-        it.advance(matchLength - 1);
-        result->setEnd(it.range()->endContainer(ec), it.range()->endOffset(ec), ec);
+    return matchLength;
+}
+
+PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
+{
+    // We can't search effectively for a string that's entirely made of collapsible
+    // whitespace, so we won't even try. This also takes care of the empty string case.
+    // FIXME: This code does not allow \n at the moment because of issues with <br>.
+    // Once we fix those, we can remove the specific check for \n.
+    if (isAllCollapsibleWhitespace(target) || target.contains('\n'))
+        return collapsedToBoundary(range, forward);
+
+    // First, find the text.
+    size_t matchStart;
+    size_t matchLength;
+    {
+        CharacterIterator findIterator(range, false, true);
+        matchLength = findPlainText(findIterator, target, forward, caseSensitive, matchStart);
+        if (!matchLength)
+            return collapsedToBoundary(range, forward);
     }
 
-    return result.release();
+    // Then, find the document position of the start and the end of the text.
+    CharacterIterator computeRangeIterator(range, false, true);
+    return characterSubrange(computeRangeIterator, matchStart, matchLength);
 }
 
 }
diff --git a/WebCore/icu/unicode/ucoleitr.h b/WebCore/icu/unicode/ucoleitr.h
new file mode 100644 (file)
index 0000000..7184e96
--- /dev/null
@@ -0,0 +1,268 @@
+/*
+*******************************************************************************
+*   Copyright (C) 2001-2004, International Business Machines
+*   Corporation and others.  All Rights Reserved.
+*******************************************************************************
+*
+* File ucoleitr.cpp
+*
+* Modification History:
+*
+* Date        Name        Description
+* 02/15/2001  synwee      Modified all methods to process its own function 
+*                         instead of calling the equivalent c++ api (coleitr.h)
+*******************************************************************************/
+
+#ifndef UCOLEITR_H
+#define UCOLEITR_H
+
+#include "unicode/utypes.h"
+
+#if !UCONFIG_NO_COLLATION
+
+/**  
+ * This indicates an error has occured during processing or if no more CEs is 
+ * to be returned.
+ * @stable ICU 2.0
+ */
+#define UCOL_NULLORDER        ((int32_t)0xFFFFFFFF)
+
+#include "unicode/ucol.h"
+
+/** 
+ * The UCollationElements struct.
+ * For usage in C programs.
+ * @stable ICU 2.0
+ */
+typedef struct UCollationElements UCollationElements;
+
+/**
+ * \file
+ * \brief C API: UCollationElements
+ *
+ * The UCollationElements API is used as an iterator to walk through each 
+ * character of an international string. Use the iterator to return the
+ * ordering priority of the positioned character. The ordering priority of a 
+ * character, which we refer to as a key, defines how a character is collated 
+ * in the given collation object.
+ * For example, consider the following in Spanish:
+ * <pre>
+ * .       "ca" -> the first key is key('c') and second key is key('a').
+ * .       "cha" -> the first key is key('ch') and second key is key('a').
+ * </pre>
+ * And in German,
+ * <pre>
+ * .       "<ae ligature>b"-> the first key is key('a'), the second key is key('e'), and
+ * .       the third key is key('b').
+ * </pre>
+ * <p>Example of the iterator usage: (without error checking)
+ * <pre>
+ * .  void CollationElementIterator_Example()
+ * .  {
+ * .      UChar *s;
+ * .      t_int32 order, primaryOrder;
+ * .      UCollationElements *c;
+ * .      UCollatorOld *coll;
+ * .      UErrorCode success = U_ZERO_ERROR;
+ * .      s=(UChar*)malloc(sizeof(UChar) * (strlen("This is a test")+1) );
+ * .      u_uastrcpy(s, "This is a test");
+ * .      coll = ucol_open(NULL, &success);
+ * .      c = ucol_openElements(coll, str, u_strlen(str), &status);
+ * .      order = ucol_next(c, &success);
+ * .      ucol_reset(c);
+ * .      order = ucol_prev(c, &success);
+ * .      free(s);
+ * .      ucol_close(coll);
+ * .      ucol_closeElements(c);
+ * .  }
+ * </pre>
+ * <p>
+ * ucol_next() returns the collation order of the next.
+ * ucol_prev() returns the collation order of the previous character.
+ * The Collation Element Iterator moves only in one direction between calls to
+ * ucol_reset. That is, ucol_next() and ucol_prev can not be inter-used. 
+ * Whenever ucol_prev is to be called after ucol_next() or vice versa, 
+ * ucol_reset has to be called first to reset the status, shifting pointers to 
+ * either the end or the start of the string. Hence at the next call of 
+ * ucol_prev or ucol_next, the first or last collation order will be returned. 
+ * If a change of direction is done without a ucol_reset, the result is 
+ * undefined.
+ * The result of a forward iterate (ucol_next) and reversed result of the  
+ * backward iterate (ucol_prev) on the same string are equivalent, if 
+ * collation orders with the value UCOL_IGNORABLE are ignored.
+ * Character based on the comparison level of the collator.  A collation order 
+ * consists of primary order, secondary order and tertiary order.  The data 
+ * type of the collation order is <strong>t_int32</strong>. 
+ *
+ * @see UCollator
+ */
+
+/**
+ * Open the collation elements for a string.
+ *
+ * @param coll The collator containing the desired collation rules.
+ * @param text The text to iterate over.
+ * @param textLength The number of characters in text, or -1 if null-terminated
+ * @param status A pointer to an UErrorCode to receive any errors.
+ * @return a struct containing collation element information
+ * @stable ICU 2.0
+ */
+U_STABLE UCollationElements* U_EXPORT2 
+ucol_openElements(const UCollator  *coll,
+                  const UChar      *text,
+                        int32_t    textLength,
+                        UErrorCode *status);
+
+/**
+ * get a hash code for a key... Not very useful!
+ * @param key    the given key.
+ * @param length the size of the key array.
+ * @return       the hash code.
+ * @stable ICU 2.0
+ */
+U_STABLE int32_t U_EXPORT2 
+ucol_keyHashCode(const uint8_t* key, int32_t length);
+
+/**
+ * Close a UCollationElements.
+ * Once closed, a UCollationElements may no longer be used.
+ * @param elems The UCollationElements to close.
+ * @stable ICU 2.0
+ */
+U_STABLE void U_EXPORT2 
+ucol_closeElements(UCollationElements *elems);
+
+/**
+ * Reset the collation elements to their initial state.
+ * This will move the 'cursor' to the beginning of the text.
+ * Property settings for collation will be reset to the current status.
+ * @param elems The UCollationElements to reset.
+ * @see ucol_next
+ * @see ucol_previous
+ * @stable ICU 2.0
+ */
+U_STABLE void U_EXPORT2 
+ucol_reset(UCollationElements *elems);
+
+/**
+ * Get the ordering priority of the next collation element in the text.
+ * A single character may contain more than one collation element.
+ * @param elems The UCollationElements containing the text.
+ * @param status A pointer to an UErrorCode to receive any errors.
+ * @return The next collation elements ordering, otherwise returns NULLORDER 
+ *         if an error has occured or if the end of string has been reached
+ * @stable ICU 2.0
+ */
+U_STABLE int32_t U_EXPORT2 
+ucol_next(UCollationElements *elems, UErrorCode *status);
+
+/**
+ * Get the ordering priority of the previous collation element in the text.
+ * A single character may contain more than one collation element.
+ * Note that internally a stack is used to store buffered collation elements. 
+ * It is very rare that the stack will overflow, however if such a case is 
+ * encountered, the problem can be solved by increasing the size 
+ * UCOL_EXPAND_CE_BUFFER_SIZE in ucol_imp.h.
+ * @param elems The UCollationElements containing the text.
+ * @param status A pointer to an UErrorCode to receive any errors. Noteably 
+ *               a U_BUFFER_OVERFLOW_ERROR is returned if the internal stack
+ *               buffer has been exhausted.
+ * @return The previous collation elements ordering, otherwise returns 
+ *         NULLORDER if an error has occured or if the start of string has 
+ *         been reached.
+ * @stable ICU 2.0
+ */
+U_STABLE int32_t U_EXPORT2 
+ucol_previous(UCollationElements *elems, UErrorCode *status);
+
+/**
+ * Get the maximum length of any expansion sequences that end with the 
+ * specified comparison order.
+ * This is useful for .... ?
+ * @param elems The UCollationElements containing the text.
+ * @param order A collation order returned by previous or next.
+ * @return maximum size of the expansion sequences ending with the collation 
+ *         element or 1 if collation element does not occur at the end of any 
+ *         expansion sequence
+ * @stable ICU 2.0
+ */
+U_STABLE int32_t U_EXPORT2 
+ucol_getMaxExpansion(const UCollationElements *elems, int32_t order);
+
+/**
+ * Set the text containing the collation elements.
+ * Property settings for collation will remain the same.
+ * In order to reset the iterator to the current collation property settings,
+ * the API reset() has to be called.
+ * @param elems The UCollationElements to set.
+ * @param text The source text containing the collation elements.
+ * @param textLength The length of text, or -1 if null-terminated.
+ * @param status A pointer to an UErrorCode to receive any errors.
+ * @see ucol_getText
+ * @stable ICU 2.0
+ */
+U_STABLE void U_EXPORT2 
+ucol_setText(      UCollationElements *elems, 
+             const UChar              *text,
+                   int32_t            textLength,
+                   UErrorCode         *status);
+
+/**
+ * Get the offset of the current source character.
+ * This is an offset into the text of the character containing the current
+ * collation elements.
+ * @param elems The UCollationElements to query.
+ * @return The offset of the current source character.
+ * @see ucol_setOffset
+ * @stable ICU 2.0
+ */
+U_STABLE int32_t U_EXPORT2 
+ucol_getOffset(const UCollationElements *elems);
+
+/**
+ * Set the offset of the current source character.
+ * This is an offset into the text of the character to be processed.
+ * Property settings for collation will remain the same.
+ * In order to reset the iterator to the current collation property settings,
+ * the API reset() has to be called.
+ * @param elems The UCollationElements to set.
+ * @param offset The desired character offset.
+ * @param status A pointer to an UErrorCode to receive any errors.
+ * @see ucol_getOffset
+ * @stable ICU 2.0
+ */
+U_STABLE void U_EXPORT2 
+ucol_setOffset(UCollationElements *elems,
+               int32_t        offset,
+               UErrorCode         *status);
+
+/**
+* Get the primary order of a collation order.
+* @param order the collation order
+* @return the primary order of a collation order.
+* @stable ICU 2.6
+*/
+U_STABLE int32_t U_EXPORT2
+ucol_primaryOrder (int32_t order); 
+
+/**
+* Get the secondary order of a collation order.
+* @param order the collation order
+* @return the secondary order of a collation order.
+* @stable ICU 2.6
+*/
+U_STABLE int32_t U_EXPORT2
+ucol_secondaryOrder (int32_t order); 
+
+/**
+* Get the tertiary order of a collation order.
+* @param order the collation order
+* @return the tertiary order of a collation order.
+* @stable ICU 2.6
+*/
+U_STABLE int32_t U_EXPORT2
+ucol_tertiaryOrder (int32_t order); 
+
+#endif /* #if !UCONFIG_NO_COLLATION */
+
+#endif
diff --git a/WebCore/icu/unicode/usearch.h b/WebCore/icu/unicode/usearch.h
new file mode 100644 (file)
index 0000000..64b9e45
--- /dev/null
@@ -0,0 +1,643 @@
+/*
+**********************************************************************
+*   Copyright (C) 2001-2005 IBM and others. All rights reserved.
+**********************************************************************
+*   Date        Name        Description
+*  06/28/2001   synwee      Creation.
+**********************************************************************
+*/
+#ifndef USEARCH_H
+#define USEARCH_H
+
+#include "unicode/utypes.h"
+
+#if !UCONFIG_NO_COLLATION
+
+#include "unicode/ucol.h"
+#include "unicode/ucoleitr.h"
+#include "unicode/ubrk.h"
+
+/**
+ * \file
+ * \brief C API: StringSearch
+ *
+ * C Apis for an engine that provides language-sensitive text searching based 
+ * on the comparison rules defined in a <tt>UCollator</tt> data struct,
+ * see <tt>ucol.h</tt>. This ensures that language eccentricity can be 
+ * handled, e.g. for the German collator, characters &szlig; and SS will be matched 
+ * if case is chosen to be ignored. 
+ * See the <a href="http://dev.icu-project.org/cgi-bin/viewcvs.cgi/~checkout~/icuhtml/design/collation/ICU_collation_design.htm">
+ * "ICU Collation Design Document"</a> for more information.
+ * <p> 
+ * The algorithm implemented is a modified form of the Boyer Moore's search.
+ * For more information  see 
+ * <a href="http://icu.sourceforge.net/docs/papers/efficient_text_searching_in_java.html">
+ * "Efficient Text Searching in Java"</a>, published in <i>Java Report</i> 
+ * in February, 1999, for further information on the algorithm.
+ * <p>
+ * There are 2 match options for selection:<br>
+ * Let S' be the sub-string of a text string S between the offsets start and 
+ * end <start, end>.
+ * <br>
+ * A pattern string P matches a text string S at the offsets <start, end> 
+ * if
+ * <pre> 
+ * option 1. Some canonical equivalent of P matches some canonical equivalent 
+ *           of S'
+ * option 2. P matches S' and if P starts or ends with a combining mark, 
+ *           there exists no non-ignorable combining mark before or after S' 
+ *           in S respectively. 
+ * </pre>
+ * Option 2. will be the default.
+ * <p>
+ * This search has APIs similar to that of other text iteration mechanisms 
+ * such as the break iterators in <tt>ubrk.h</tt>. Using these 
+ * APIs, it is easy to scan through text looking for all occurances of 
+ * a given pattern. This search iterator allows changing of direction by 
+ * calling a <tt>reset</tt> followed by a <tt>next</tt> or <tt>previous</tt>. 
+ * Though a direction change can occur without calling <tt>reset</tt> first,  
+ * this operation comes with some speed penalty.
+ * Generally, match results in the forward direction will match the result 
+ * matches in the backwards direction in the reverse order
+ * <p>
+ * <tt>usearch.h</tt> provides APIs to specify the starting position 
+ * within the text string to be searched, e.g. <tt>usearch_setOffset</tt>,
+ * <tt>usearch_preceding</tt> and <tt>usearch_following</tt>. Since the 
+ * starting position will be set as it is specified, please take note that 
+ * there are some dangerous positions which the search may render incorrect 
+ * results:
+ * <ul>
+ * <li> The midst of a substring that requires normalization.
+ * <li> If the following match is to be found, the position should not be the
+ *      second character which requires to be swapped with the preceding 
+ *      character. Vice versa, if the preceding match is to be found, 
+ *      position to search from should not be the first character which 
+ *      requires to be swapped with the next character. E.g certain Thai and
+ *      Lao characters require swapping.
+ * <li> If a following pattern match is to be found, any position within a 
+ *      contracting sequence except the first will fail. Vice versa if a 
+ *      preceding pattern match is to be found, a invalid starting point 
+ *      would be any character within a contracting sequence except the last.
+ * </ul>
+ * <p>
+ * A breakiterator can be used if only matches at logical breaks are desired.
+ * Using a breakiterator will only give you results that exactly matches the
+ * boundaries given by the breakiterator. For instance the pattern "e" will
+ * not be found in the string "\u00e9" if a character break iterator is used.
+ * <p>
+ * Options are provided to handle overlapping matches. 
+ * E.g. In English, overlapping matches produces the result 0 and 2 
+ * for the pattern "abab" in the text "ababab", where else mutually 
+ * exclusive matches only produce the result of 0.
+ * <p>
+ * Though collator attributes will be taken into consideration while 
+ * performing matches, there are no APIs here for setting and getting the 
+ * attributes. These attributes can be set by getting the collator
+ * from <tt>usearch_getCollator</tt> and using the APIs in <tt>ucol.h</tt>.
+ * Lastly to update String Search to the new collator attributes, 
+ * usearch_reset() has to be called.
+ * <p> 
+ * Restriction: <br>
+ * Currently there are no composite characters that consists of a
+ * character with combining class > 0 before a character with combining 
+ * class == 0. However, if such a character exists in the future, the 
+ * search mechanism does not guarantee the results for option 1.
+ * 
+ * <p>
+ * Example of use:<br>
+ * <pre><code>
+ * char *tgtstr = "The quick brown fox jumped over the lazy fox";
+ * char *patstr = "fox";
+ * UChar target[64];
+ * UChar pattern[16];
+ * UErrorCode status = U_ZERO_ERROR;
+ * u_uastrcpy(target, tgtstr);
+ * u_uastrcpy(pattern, patstr);
+ *
+ * UStringSearch *search = usearch_open(pattern, -1, target, -1, "en_US", 
+ *                                  &status);
+ * if (U_SUCCESS(status)) {
+ *     for (int pos = usearch_first(search, &status); 
+ *                                      pos != USEARCH_DONE; 
+ *                                      pos = usearch_next(search, &status)) {
+ *         printf("Found match at %d pos, length is %d\n", pos, 
+ *                                        usearch_getMatchLength(search));
+ *     }
+ * }
+ * </code></pre>
+ * @stable ICU 2.4
+ */
+
+/**
+* DONE is returned by previous() and next() after all valid matches have 
+* been returned, and by first() and last() if there are no matches at all.
+* @stable ICU 2.4
+*/
+#define USEARCH_DONE -1
+
+/**
+* Data structure for searching
+* @stable ICU 2.4
+*/
+struct UStringSearch;
+/**
+* Data structure for searching
+* @stable ICU 2.4
+*/
+typedef struct UStringSearch UStringSearch;
+
+/**
+* @stable ICU 2.4
+*/
+typedef enum {
+    /** Option for overlapping matches */
+    USEARCH_OVERLAP,
+    /** 
+    Option for canonical matches. option 1 in header documentation.
+    The default value will be USEARCH_OFF
+    */
+    USEARCH_CANONICAL_MATCH,
+    USEARCH_ATTRIBUTE_COUNT
+} USearchAttribute;
+
+/**
+* @stable ICU 2.4
+*/
+typedef enum {
+    /** default value for any USearchAttribute */
+    USEARCH_DEFAULT = -1,
+    /** value for USEARCH_OVERLAP and USEARCH_CANONICAL_MATCH */
+    USEARCH_OFF, 
+    /** value for USEARCH_OVERLAP and USEARCH_CANONICAL_MATCH */
+    USEARCH_ON,
+    USEARCH_ATTRIBUTE_VALUE_COUNT
+} USearchAttributeValue;
+
+/* open and close ------------------------------------------------------ */
+
+/**
+* Creating a search iterator data struct using the argument locale language
+* rule set. A collator will be created in the process, which will be owned by
+* this search and will be deleted in <tt>usearch_close</tt>.
+* @param pattern for matching
+* @param patternlength length of the pattern, -1 for null-termination
+* @param text text string
+* @param textlength length of the text string, -1 for null-termination
+* @param locale name of locale for the rules to be used
+* @param breakiter A BreakIterator that will be used to restrict the points
+*                  at which matches are detected. If a match is found, but 
+*                  the match's start or end index is not a boundary as 
+*                  determined by the <tt>BreakIterator</tt>, the match will 
+*                  be rejected and another will be searched for. 
+*                  If this parameter is <tt>NULL</tt>, no break detection is 
+*                  attempted.
+* @param status for errors if it occurs. If pattern or text is NULL, or if
+*               patternlength or textlength is 0 then an 
+*               U_ILLEGAL_ARGUMENT_ERROR is returned.
+* @return search iterator data structure, or NULL if there is an error.
+* @stable ICU 2.4
+*/
+U_STABLE UStringSearch * U_EXPORT2 usearch_open(const UChar          *pattern, 
+                                              int32_t         patternlength, 
+                                        const UChar          *text, 
+                                              int32_t         textlength,
+                                        const char           *locale,
+                                              UBreakIterator *breakiter,
+                                              UErrorCode     *status);
+
+/**
+* Creating a search iterator data struct using the argument collator language
+* rule set. Note, user retains the ownership of this collator, thus the 
+* responsibility of deletion lies with the user.
+* NOTE: string search cannot be instantiated from a collator that has 
+* collate digits as numbers (CODAN) turned on.
+* @param pattern for matching
+* @param patternlength length of the pattern, -1 for null-termination
+* @param text text string
+* @param textlength length of the text string, -1 for null-termination
+* @param collator used for the language rules
+* @param breakiter A BreakIterator that will be used to restrict the points
+*                  at which matches are detected. If a match is found, but 
+*                  the match's start or end index is not a boundary as 
+*                  determined by the <tt>BreakIterator</tt>, the match will 
+*                  be rejected and another will be searched for. 
+*                  If this parameter is <tt>NULL</tt>, no break detection is 
+*                  attempted.
+* @param status for errors if it occurs. If collator, pattern or text is NULL, 
+*               or if patternlength or textlength is 0 then an 
+*               U_ILLEGAL_ARGUMENT_ERROR is returned.
+* @return search iterator data structure, or NULL if there is an error.
+* @stable ICU 2.4
+*/
+U_STABLE UStringSearch * U_EXPORT2 usearch_openFromCollator(
+                                         const UChar *pattern, 
+                                               int32_t         patternlength,
+                                         const UChar          *text, 
+                                               int32_t         textlength,
+                                         const UCollator      *collator,
+                                               UBreakIterator *breakiter,
+                                               UErrorCode     *status);
+
+/**
+* Destroying and cleaning up the search iterator data struct.
+* If a collator is created in <tt>usearch_open</tt>, it will be destroyed here.
+* @param searchiter data struct to clean up
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_close(UStringSearch *searchiter);
+
+/* get and set methods -------------------------------------------------- */
+
+/**
+* Sets the current position in the text string which the next search will 
+* start from. Clears previous states. 
+* This method takes the argument index and sets the position in the text 
+* string accordingly without checking if the index is pointing to a 
+* valid starting point to begin searching. 
+* Search positions that may render incorrect results are highlighted in the
+* header comments
+* @param strsrch search iterator data struct
+* @param position position to start next search from. If position is less
+*          than or greater than the text range for searching, 
+*          an U_INDEX_OUTOFBOUNDS_ERROR will be returned
+* @param status error status if any.
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_setOffset(UStringSearch *strsrch, 
+                                        int32_t    position,
+                                        UErrorCode    *status);
+
+/**
+* Return the current index in the string text being searched.
+* If the iteration has gone past the end of the text (or past the beginning 
+* for a backwards search), <tt>USEARCH_DONE</tt> is returned.
+* @param strsrch search iterator data struct
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_getOffset(const UStringSearch *strsrch);
+    
+/**
+* Sets the text searching attributes located in the enum USearchAttribute
+* with values from the enum USearchAttributeValue.
+* <tt>USEARCH_DEFAULT</tt> can be used for all attributes for resetting.
+* @param strsrch search iterator data struct
+* @param attribute text attribute to be set
+* @param value text attribute value
+* @param status for errors if it occurs
+* @see #usearch_getAttribute
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_setAttribute(UStringSearch         *strsrch, 
+                                           USearchAttribute       attribute,
+                                           USearchAttributeValue  value,
+                                           UErrorCode            *status);
+
+/**    
+* Gets the text searching attributes.
+* @param strsrch search iterator data struct
+* @param attribute text attribute to be retrieve
+* @return text attribute value
+* @see #usearch_setAttribute
+* @stable ICU 2.4
+*/
+U_STABLE USearchAttributeValue U_EXPORT2 usearch_getAttribute(
+                                         const UStringSearch    *strsrch,
+                                               USearchAttribute  attribute);
+
+/**
+* Returns the index to the match in the text string that was searched.
+* This call returns a valid result only after a successful call to 
+* <tt>usearch_first</tt>, <tt>usearch_next</tt>, <tt>usearch_previous</tt>, 
+* or <tt>usearch_last</tt>.
+* Just after construction, or after a searching method returns 
+* <tt>USEARCH_DONE</tt>, this method will return <tt>USEARCH_DONE</tt>.
+* <p>
+* Use <tt>usearch_getMatchedLength</tt> to get the matched string length.
+* @param strsrch search iterator data struct
+* @return index to a substring within the text string that is being 
+*         searched.
+* @see #usearch_first
+* @see #usearch_next
+* @see #usearch_previous
+* @see #usearch_last
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_getMatchedStart(
+                                               const UStringSearch *strsrch);
+    
+/**
+* Returns the length of text in the string which matches the search pattern. 
+* This call returns a valid result only after a successful call to 
+* <tt>usearch_first</tt>, <tt>usearch_next</tt>, <tt>usearch_previous</tt>, 
+* or <tt>usearch_last</tt>.
+* Just after construction, or after a searching method returns 
+* <tt>USEARCH_DONE</tt>, this method will return 0.
+* @param strsrch search iterator data struct
+* @return The length of the match in the string text, or 0 if there is no 
+*         match currently.
+* @see #usearch_first
+* @see #usearch_next
+* @see #usearch_previous
+* @see #usearch_last
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_getMatchedLength(
+                                               const UStringSearch *strsrch);
+
+/**
+* Returns the text that was matched by the most recent call to 
+* <tt>usearch_first</tt>, <tt>usearch_next</tt>, <tt>usearch_previous</tt>, 
+* or <tt>usearch_last</tt>.
+* If the iterator is not pointing at a valid match (e.g. just after 
+* construction or after <tt>USEARCH_DONE</tt> has been returned, returns
+* an empty string. If result is not large enough to store the matched text,
+* result will be filled with the partial text and an U_BUFFER_OVERFLOW_ERROR 
+* will be returned in status. result will be null-terminated whenever 
+* possible. If the buffer fits the matched text exactly, a null-termination 
+* is not possible, then a U_STRING_NOT_TERMINATED_ERROR set in status.
+* Pre-flighting can be either done with length = 0 or the API 
+* <tt>usearch_getMatchLength</tt>.
+* @param strsrch search iterator data struct
+* @param result UChar buffer to store the matched string
+* @param resultCapacity length of the result buffer
+* @param status error returned if result is not large enough
+* @return exact length of the matched text, not counting the null-termination
+* @see #usearch_first
+* @see #usearch_next
+* @see #usearch_previous
+* @see #usearch_last
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_getMatchedText(const UStringSearch *strsrch, 
+                                            UChar         *result, 
+                                            int32_t        resultCapacity, 
+                                            UErrorCode    *status);
+
+#if !UCONFIG_NO_BREAK_ITERATION
+
+/**
+* Set the BreakIterator that will be used to restrict the points at which 
+* matches are detected.
+* @param strsrch search iterator data struct
+* @param breakiter A BreakIterator that will be used to restrict the points
+*                  at which matches are detected. If a match is found, but 
+*                  the match's start or end index is not a boundary as 
+*                  determined by the <tt>BreakIterator</tt>, the match will 
+*                  be rejected and another will be searched for. 
+*                  If this parameter is <tt>NULL</tt>, no break detection is 
+*                  attempted.
+* @param status for errors if it occurs
+* @see #usearch_getBreakIterator
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_setBreakIterator(UStringSearch  *strsrch, 
+                                               UBreakIterator *breakiter,
+                                               UErrorCode     *status);
+
+/**
+* Returns the BreakIterator that is used to restrict the points at which 
+* matches are detected. This will be the same object that was passed to the 
+* constructor or to <tt>usearch_setBreakIterator</tt>. Note that 
+* <tt>NULL</tt> 
+* is a legal value; it means that break detection should not be attempted.
+* @param strsrch search iterator data struct
+* @return break iterator used
+* @see #usearch_setBreakIterator
+* @stable ICU 2.4
+*/
+U_STABLE const UBreakIterator * U_EXPORT2 usearch_getBreakIterator(
+                                              const UStringSearch *strsrch);
+    
+#endif
+    
+/**
+* Set the string text to be searched. Text iteration will hence begin at the 
+* start of the text string. This method is useful if you want to re-use an 
+* iterator to search for the same pattern within a different body of text.
+* @param strsrch search iterator data struct
+* @param text new string to look for match
+* @param textlength length of the new string, -1 for null-termination
+* @param status for errors if it occurs. If text is NULL, or textlength is 0 
+*               then an U_ILLEGAL_ARGUMENT_ERROR is returned with no change
+*               done to strsrch.
+* @see #usearch_getText
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_setText(      UStringSearch *strsrch, 
+                                      const UChar         *text,
+                                            int32_t        textlength,
+                                            UErrorCode    *status);
+
+/**
+* Return the string text to be searched.
+* @param strsrch search iterator data struct
+* @param length returned string text length
+* @return string text 
+* @see #usearch_setText
+* @stable ICU 2.4
+*/
+U_STABLE const UChar * U_EXPORT2 usearch_getText(const UStringSearch *strsrch, 
+                                               int32_t       *length);
+
+/**
+* Gets the collator used for the language rules. 
+* <p>
+* Deleting the returned <tt>UCollator</tt> before calling 
+* <tt>usearch_close</tt> would cause the string search to fail.
+* <tt>usearch_close</tt> will delete the collator if this search owns it.
+* @param strsrch search iterator data struct
+* @return collator
+* @stable ICU 2.4
+*/
+U_STABLE UCollator * U_EXPORT2 usearch_getCollator(
+                                               const UStringSearch *strsrch);
+
+/**
+* Sets the collator used for the language rules. User retains the ownership 
+* of this collator, thus the responsibility of deletion lies with the user.
+* This method causes internal data such as Boyer-Moore shift tables to  
+* be recalculated, but the iterator's position is unchanged.
+* @param strsrch search iterator data struct
+* @param collator to be used
+* @param status for errors if it occurs
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_setCollator(      UStringSearch *strsrch, 
+                                          const UCollator     *collator,
+                                                UErrorCode    *status);
+
+/**
+* Sets the pattern used for matching.
+* Internal data like the Boyer Moore table will be recalculated, but the 
+* iterator's position is unchanged.
+* @param strsrch search iterator data struct
+* @param pattern string
+* @param patternlength pattern length, -1 for null-terminated string
+* @param status for errors if it occurs. If text is NULL, or textlength is 0 
+*               then an U_ILLEGAL_ARGUMENT_ERROR is returned with no change
+*               done to strsrch.
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_setPattern(      UStringSearch *strsrch, 
+                                         const UChar         *pattern,
+                                               int32_t        patternlength,
+                                               UErrorCode    *status);
+
+/**
+* Gets the search pattern
+* @param strsrch search iterator data struct
+* @param length return length of the pattern, -1 indicates that the pattern 
+*               is null-terminated
+* @return pattern string
+* @stable ICU 2.4
+*/
+U_STABLE const UChar * U_EXPORT2 usearch_getPattern(
+                                               const UStringSearch *strsrch, 
+                                                     int32_t       *length);
+
+/* methods ------------------------------------------------------------- */
+
+/**
+* Returns the first index at which the string text matches the search 
+* pattern.  
+* The iterator is adjusted so that its current index (as returned by 
+* <tt>usearch_getOffset</tt>) is the match position if one was found.
+* If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
+* the iterator will be adjusted to the index <tt>USEARCH_DONE</tt>.
+* @param strsrch search iterator data struct
+* @param status for errors if it occurs
+* @return The character index of the first match, or 
+* <tt>USEARCH_DONE</tt> if there are no matches.
+* @see #usearch_getOffset
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_first(UStringSearch *strsrch, 
+                                           UErrorCode    *status);
+
+/**
+* Returns the first index greater than <tt>position</tt> at which the string 
+* text 
+* matches the search pattern. The iterator is adjusted so that its current 
+* index (as returned by <tt>usearch_getOffset</tt>) is the match position if 
+* one was found.
+* If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
+* the iterator will be adjusted to the index <tt>USEARCH_DONE</tt>
+* <p>
+* Search positions that may render incorrect results are highlighted in the
+* header comments. If position is less than or greater than the text range 
+* for searching, an U_INDEX_OUTOFBOUNDS_ERROR will be returned
+* @param strsrch search iterator data struct
+* @param position to start the search at
+* @param status for errors if it occurs
+* @return The character index of the first match following <tt>pos</tt>,
+*         or <tt>USEARCH_DONE</tt> if there are no matches.
+* @see #usearch_getOffset
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_following(UStringSearch *strsrch, 
+                                               int32_t    position, 
+                                               UErrorCode    *status);
+    
+/**
+* Returns the last index in the target text at which it matches the search 
+* pattern. The iterator is adjusted so that its current 
+* index (as returned by <tt>usearch_getOffset</tt>) is the match position if 
+* one was found.
+* If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
+* the iterator will be adjusted to the index <tt>USEARCH_DONE</tt>.
+* @param strsrch search iterator data struct
+* @param status for errors if it occurs
+* @return The index of the first match, or <tt>USEARCH_DONE</tt> if there 
+*         are no matches.
+* @see #usearch_getOffset
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_last(UStringSearch *strsrch, 
+                                          UErrorCode    *status);
+
+/**
+* Returns the first index less than <tt>position</tt> at which the string text 
+* matches the search pattern. The iterator is adjusted so that its current 
+* index (as returned by <tt>usearch_getOffset</tt>) is the match position if 
+* one was found.
+* If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
+* the iterator will be adjusted to the index <tt>USEARCH_DONE</tt>
+* <p>
+* Search positions that may render incorrect results are highlighted in the
+* header comments. If position is less than or greater than the text range 
+* for searching, an U_INDEX_OUTOFBOUNDS_ERROR will be returned
+* @param strsrch search iterator data struct
+* @param position index position the search is to begin at
+* @param status for errors if it occurs
+* @return The character index of the first match preceding <tt>pos</tt>,
+*         or <tt>USEARCH_DONE</tt> if there are no matches.
+* @see #usearch_getOffset
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_preceding(UStringSearch *strsrch, 
+                                               int32_t    position, 
+                                               UErrorCode    *status);
+    
+/**
+* Returns the index of the next point at which the string text matches the
+* search pattern, starting from the current position.
+* The iterator is adjusted so that its current 
+* index (as returned by <tt>usearch_getOffset</tt>) is the match position if 
+* one was found.
+* If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
+* the iterator will be adjusted to the index <tt>USEARCH_DONE</tt>
+* @param strsrch search iterator data struct
+* @param status for errors if it occurs
+* @return The index of the next match after the current position, or 
+*         <tt>USEARCH_DONE</tt> if there are no more matches.
+* @see #usearch_first
+* @see #usearch_getOffset
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_next(UStringSearch *strsrch, 
+                                          UErrorCode    *status);
+
+/**
+* Returns the index of the previous point at which the string text matches
+* the search pattern, starting at the current position.
+* The iterator is adjusted so that its current 
+* index (as returned by <tt>usearch_getOffset</tt>) is the match position if 
+* one was found.
+* If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
+* the iterator will be adjusted to the index <tt>USEARCH_DONE</tt>
+* @param strsrch search iterator data struct
+* @param status for errors if it occurs
+* @return The index of the previous match before the current position,
+*         or <tt>USEARCH_DONE</tt> if there are no more matches.
+* @see #usearch_last
+* @see #usearch_getOffset
+* @see #USEARCH_DONE
+* @stable ICU 2.4
+*/
+U_STABLE int32_t U_EXPORT2 usearch_previous(UStringSearch *strsrch, 
+                                              UErrorCode    *status);
+    
+/** 
+* Reset the iteration.
+* Search will begin at the start of the text string if a forward iteration 
+* is initiated before a backwards iteration. Otherwise if a backwards 
+* iteration is initiated before a forwards iteration, the search will begin
+* at the end of the text string.
+* @param strsrch search iterator data struct
+* @see #usearch_first
+* @stable ICU 2.4
+*/
+U_STABLE void U_EXPORT2 usearch_reset(UStringSearch *strsrch);
+
+#endif /* #if !UCONFIG_NO_COLLATION */
+
+#endif