root/Source/web/TextFinder.cpp

DEFINITIONS

1. m_ordinal
2. trace
3. m_reset
4. doTimeout
5. find
6. stopFindingAndClearSelection
7. scopeStringMatches
8. flushCurrentScopingEffort
9. finishCurrentScopingEffort
10. cancelPendingScopingEffort
11. increaseMatchCount
12. reportFindInPageSelection
13. resetMatchCount
14. clearFindMatchesCache
15. isActiveMatchFrameValid
16. updateFindMatchRects
17. activeFindMatchRect
18. findMatchRects
19. appendFindMatchRects
20. selectNearestFindMatch
21. nearestFindMatch
22. selectFindMatch
23. create
24. m_findMatchRectsAreValid
25. addMarker
26. setMarkerActive
27. ordinalOfFirstMatchForFrame
28. shouldScopeMatches
29. scopeStringMatchesSoon
30. callScopeStringMatches
31. invalidateIfNecessary
32. flushCurrentScoping
33. setMatchMarkerActive
34. decrementFramesScopingCount
35. ordinalOfFirstMatch

/*
 * Copyright (C) 2009 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


#include "config.h"
#include "TextFinder.h"

#include "FindInPageCoordinates.h"
#include "WebFindOptions.h"
#include "WebFrameClient.h"
#include "WebFrameImpl.h"
#include "WebViewClient.h"
#include "WebViewImpl.h"
#include "core/dom/DocumentMarker.h"
#include "core/dom/DocumentMarkerController.h"
#include "core/dom/Range.h"
#include "core/dom/shadow/ShadowRoot.h"
#include "core/editing/Editor.h"
#include "core/editing/TextIterator.h"
#include "core/editing/VisibleSelection.h"
#include "core/frame/FrameView.h"
#include "platform/Timer.h"
#include "public/platform/WebVector.h"
#include "wtf/CurrentTime.h"

using namespace WebCore;

namespace blink {

TextFinder::FindMatch::FindMatch(PassRefPtrWillBeRawPtr<Range> range, int ordinal)
    : m_range(range)
    , m_ordinal(ordinal)
{
}

void TextFinder::FindMatch::trace(WebCore::Visitor* visitor)
{
    visitor->trace(m_range);
}

class TextFinder::DeferredScopeStringMatches {
public:
    DeferredScopeStringMatches(TextFinder* textFinder, int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
        : m_timer(this, &DeferredScopeStringMatches::doTimeout)
        , m_textFinder(textFinder)
        , m_identifier(identifier)
        , m_searchText(searchText)
        , m_options(options)
        , m_reset(reset)
    {
        m_timer.startOneShot(0.0, FROM_HERE);
    }

private:
    void doTimeout(Timer<DeferredScopeStringMatches>*)
    {
        m_textFinder->callScopeStringMatches(this, m_identifier, m_searchText, m_options, m_reset);
    }

    Timer<DeferredScopeStringMatches> m_timer;
    TextFinder* m_textFinder;
    const int m_identifier;
    const WebString m_searchText;
    const WebFindOptions m_options;
    const bool m_reset;
};

bool TextFinder::find(int identifier, const WebString& searchText, const WebFindOptions& options, bool wrapWithinFrame, WebRect* selectionRect)
{
    if (!m_ownerFrame.frame() || !m_ownerFrame.frame()->page())
        return false;

    WebFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();

    if (!options.findNext)
        m_ownerFrame.frame()->page()->unmarkAllTextMatches();
    else
        setMarkerActive(m_activeMatch.get(), false);

    if (m_activeMatch && &m_activeMatch->ownerDocument() != m_ownerFrame.frame()->document())
        m_activeMatch = nullptr;

    // If the user has selected something since the last Find operation we want
    // to start from there. Otherwise, we start searching from where the last Find
    // operation left off (either a Find or a FindNext operation).
    VisibleSelection selection(m_ownerFrame.frame()->selection().selection());
    bool activeSelection = !selection.isNone();
    if (activeSelection) {
        m_activeMatch = selection.firstRange().get();
        m_ownerFrame.frame()->selection().clear();
    }

    ASSERT(m_ownerFrame.frame() && m_ownerFrame.frame()->view());
    const FindOptions findOptions = (options.forward ? 0 : Backwards)
        | (options.matchCase ? 0 : CaseInsensitive)
        | (wrapWithinFrame ? WrapAround : 0)
        | (options.wordStart ? AtWordStarts : 0)
        | (options.medialCapitalAsWordStart ? TreatMedialCapitalAsWordStart : 0)
        | (options.findNext ? 0 : StartInSelection);
    m_activeMatch = m_ownerFrame.frame()->editor().findStringAndScrollToVisible(searchText, m_activeMatch.get(), findOptions);

    if (!m_activeMatch) {
        // If we're finding next the next active match might not be in the current frame.
        // In this case we don't want to clear the matches cache.
        if (!options.findNext)
            clearFindMatchesCache();

        m_ownerFrame.invalidateAll();
        return false;
    }

#if OS(ANDROID)
    m_ownerFrame.viewImpl()->zoomToFindInPageRect(m_ownerFrame.frameView()->contentsToWindow(enclosingIntRect(RenderObject::absoluteBoundingBoxRectForRange(m_activeMatch.get()))));
#endif

    setMarkerActive(m_activeMatch.get(), true);
    WebFrameImpl* oldActiveFrame = mainFrameImpl->ensureTextFinder().m_currentActiveMatchFrame;
    mainFrameImpl->ensureTextFinder().m_currentActiveMatchFrame = &m_ownerFrame;

    // Make sure no node is focused. See http://crbug.com/38700.
    m_ownerFrame.frame()->document()->setFocusedElement(nullptr);

    if (!options.findNext || activeSelection) {
        // This is either a Find operation or a Find-next from a new start point
        // due to a selection, so we set the flag to ask the scoping effort
        // to find the active rect for us and report it back to the UI.
        m_locatingActiveRect = true;
    } else {
        if (oldActiveFrame != &m_ownerFrame) {
            if (options.forward)
                m_activeMatchIndexInCurrentFrame = 0;
            else
                m_activeMatchIndexInCurrentFrame = m_lastMatchCount - 1;
        } else {
            if (options.forward)
                ++m_activeMatchIndexInCurrentFrame;
            else
                --m_activeMatchIndexInCurrentFrame;

            if (m_activeMatchIndexInCurrentFrame + 1 > m_lastMatchCount)
                m_activeMatchIndexInCurrentFrame = 0;
            if (m_activeMatchIndexInCurrentFrame == -1)
                m_activeMatchIndexInCurrentFrame = m_lastMatchCount - 1;
        }
        if (selectionRect) {
            *selectionRect = m_ownerFrame.frameView()->contentsToWindow(m_activeMatch->boundingBox());
            reportFindInPageSelection(*selectionRect, m_activeMatchIndexInCurrentFrame + 1, identifier);
        }
    }

    return true;
}

void TextFinder::stopFindingAndClearSelection()
{
    cancelPendingScopingEffort();

    // Remove all markers for matches found and turn off the highlighting.
    m_ownerFrame.frame()->document()->markers().removeMarkers(DocumentMarker::TextMatch);
    m_ownerFrame.frame()->editor().setMarkedTextMatchesAreHighlighted(false);
    clearFindMatchesCache();

    // Let the frame know that we don't want tickmarks or highlighting anymore.
    m_ownerFrame.invalidateAll();
}

void TextFinder::scopeStringMatches(int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
{
    if (reset) {
        // This is a brand new search, so we need to reset everything.
        // Scoping is just about to begin.
        m_scopingInProgress = true;

        // Need to keep the current identifier locally in order to finish the
        // request in case the frame is detached during the process.
        m_findRequestIdentifier = identifier;

        // Clear highlighting for this frame.
        LocalFrame* frame = m_ownerFrame.frame();
        if (frame && frame->page() && frame->editor().markedTextMatchesAreHighlighted())
            frame->page()->unmarkAllTextMatches();

        // Clear the tickmarks and results cache.
        clearFindMatchesCache();

        // Clear the counters from last operation.
        m_lastMatchCount = 0;
        m_nextInvalidateAfter = 0;
        m_resumeScopingFromRange = nullptr;

        // The view might be null on detached frames.
        if (frame && frame->page())
            m_ownerFrame.viewImpl()->mainFrameImpl()->ensureTextFinder().m_framesScopingCount++;

        // Now, defer scoping until later to allow find operation to finish quickly.
        scopeStringMatchesSoon(identifier, searchText, options, false); // false means just reset, so don't do it again.
        return;
    }

    if (!shouldScopeMatches(searchText)) {
        // Note that we want to defer the final update when resetting even if shouldScopeMatches returns false.
        // This is done in order to prevent sending a final message based only on the results of the first frame
        // since m_framesScopingCount would be 0 as other frames have yet to reset.
        finishCurrentScopingEffort(identifier);
        return;
    }

    WebFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
    RefPtrWillBeRawPtr<Range> searchRange(rangeOfContents(m_ownerFrame.frame()->document()));

    Node* originalEndContainer = searchRange->endContainer();
    int originalEndOffset = searchRange->endOffset();

    TrackExceptionState exceptionState, exceptionState2;
    if (m_resumeScopingFromRange) {
        // This is a continuation of a scoping operation that timed out and didn't
        // complete last time around, so we should start from where we left off.
        searchRange->setStart(m_resumeScopingFromRange->startContainer(), m_resumeScopingFromRange->startOffset(exceptionState2) + 1, exceptionState);
        if (exceptionState.hadException() || exceptionState2.hadException()) {
            if (exceptionState2.hadException()) // A non-zero |exceptionState| happens when navigating during search.
                ASSERT_NOT_REACHED();
            return;
        }
    }

    // This timeout controls how long we scope before releasing control. This
    // value does not prevent us from running for longer than this, but it is
    // periodically checked to see if we have exceeded our allocated time.
    const double maxScopingDuration = 0.1; // seconds

    int matchCount = 0;
    bool timedOut = false;
    double startTime = currentTime();
    do {
        // Find next occurrence of the search string.
        // FIXME: (http://b/1088245) This WebKit operation may run for longer
        // than the timeout value, and is not interruptible as it is currently
        // written. We may need to rewrite it with interruptibility in mind, or
        // find an alternative.
        RefPtrWillBeRawPtr<Range> resultRange(findPlainText(
            searchRange.get(), searchText, options.matchCase ? 0 : CaseInsensitive));
        if (resultRange->collapsed(exceptionState)) {
            if (!resultRange->startContainer()->isInShadowTree())
                break;

            searchRange->setStartAfter(
                resultRange->startContainer()->deprecatedShadowAncestorNode(), exceptionState);
            searchRange->setEnd(originalEndContainer, originalEndOffset, exceptionState);
            continue;
        }

        ++matchCount;

        // Catch a special case where Find found something but doesn't know what
        // the bounding box for it is. In this case we set the first match we find
        // as the active rect.
        IntRect resultBounds = resultRange->boundingBox();
        IntRect activeSelectionRect;
        if (m_locatingActiveRect) {
            activeSelectionRect = m_activeMatch.get() ?
                m_activeMatch->boundingBox() : resultBounds;
        }

        // If the Find function found a match it will have stored where the
        // match was found in m_activeSelectionRect on the current frame. If we
        // find this rect during scoping it means we have found the active
        // tickmark.
        bool foundActiveMatch = false;
        if (m_locatingActiveRect && (activeSelectionRect == resultBounds)) {
            // We have found the active tickmark frame.
            mainFrameImpl->ensureTextFinder().m_currentActiveMatchFrame = &m_ownerFrame;
            foundActiveMatch = true;
            // We also know which tickmark is active now.
            m_activeMatchIndexInCurrentFrame = matchCount - 1;
            // To stop looking for the active tickmark, we set this flag.
            m_locatingActiveRect = false;

            // Notify browser of new location for the selected rectangle.
            reportFindInPageSelection(
                m_ownerFrame.frameView()->contentsToWindow(resultBounds),
                m_activeMatchIndexInCurrentFrame + 1,
                identifier);
        }

        addMarker(resultRange.get(), foundActiveMatch);

        m_findMatchesCache.append(FindMatch(resultRange.get(), m_lastMatchCount + matchCount));

        // Set the new start for the search range to be the end of the previous
        // result range. There is no need to use a VisiblePosition here,
        // since findPlainText will use a TextIterator to go over the visible
        // text nodes.
        searchRange->setStart(resultRange->endContainer(exceptionState), resultRange->endOffset(exceptionState), exceptionState);

        Node* shadowTreeRoot = searchRange->shadowRoot();
        if (searchRange->collapsed(exceptionState) && shadowTreeRoot)
            searchRange->setEnd(shadowTreeRoot, shadowTreeRoot->countChildren(), exceptionState);

        m_resumeScopingFromRange = resultRange;
        timedOut = (currentTime() - startTime) >= maxScopingDuration;
    } while (!timedOut);

    // Remember what we search for last time, so we can skip searching if more
    // letters are added to the search string (and last outcome was 0).
    m_lastSearchString = searchText;

    if (matchCount > 0) {
        m_ownerFrame.frame()->editor().setMarkedTextMatchesAreHighlighted(true);

        m_lastMatchCount += matchCount;

        // Let the mainframe know how much we found during this pass.
        mainFrameImpl->increaseMatchCount(matchCount, identifier);
    }

    if (timedOut) {
        // If we found anything during this pass, we should redraw. However, we
        // don't want to spam too much if the page is extremely long, so if we
        // reach a certain point we start throttling the redraw requests.
        if (matchCount > 0)
            invalidateIfNecessary();

        // Scoping effort ran out of time, lets ask for another time-slice.
        scopeStringMatchesSoon(
            identifier,
            searchText,
            options,
            false); // don't reset.
        return; // Done for now, resume work later.
    }

    finishCurrentScopingEffort(identifier);
}

void TextFinder::flushCurrentScopingEffort(int identifier)
{
    if (!m_ownerFrame.frame() || !m_ownerFrame.frame()->page())
        return;

    WebFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
    mainFrameImpl->ensureTextFinder().decrementFramesScopingCount(identifier);
}

void TextFinder::finishCurrentScopingEffort(int identifier)
{
    flushCurrentScopingEffort(identifier);

    m_scopingInProgress = false;
    m_lastFindRequestCompletedWithNoMatches = !m_lastMatchCount;

    // This frame is done, so show any scrollbar tickmarks we haven't drawn yet.
    m_ownerFrame.invalidateScrollbar();
}

void TextFinder::cancelPendingScopingEffort()
{
    deleteAllValues(m_deferredScopingWork);
    m_deferredScopingWork.clear();

    m_activeMatchIndexInCurrentFrame = -1;

    // Last request didn't complete.
    if (m_scopingInProgress)
        m_lastFindRequestCompletedWithNoMatches = false;

    m_scopingInProgress = false;
}

void TextFinder::increaseMatchCount(int identifier, int count)
{
    if (count)
        ++m_findMatchMarkersVersion;

    m_totalMatchCount += count;

    // Update the UI with the latest findings.
    if (m_ownerFrame.client())
        m_ownerFrame.client()->reportFindInPageMatchCount(identifier, m_totalMatchCount, !m_framesScopingCount);
}

void TextFinder::reportFindInPageSelection(const WebRect& selectionRect, int activeMatchOrdinal, int identifier)
{
    // Update the UI with the latest selection rect.
    if (m_ownerFrame.client())
        m_ownerFrame.client()->reportFindInPageSelection(identifier, ordinalOfFirstMatch() + activeMatchOrdinal, selectionRect);
}

void TextFinder::resetMatchCount()
{
    if (m_totalMatchCount > 0)
        ++m_findMatchMarkersVersion;

    m_totalMatchCount = 0;
    m_framesScopingCount = 0;
}

void TextFinder::clearFindMatchesCache()
{
    if (!m_findMatchesCache.isEmpty())
        m_ownerFrame.viewImpl()->mainFrameImpl()->ensureTextFinder().m_findMatchMarkersVersion++;

    m_findMatchesCache.clear();
    m_findMatchRectsAreValid = false;
}

bool TextFinder::isActiveMatchFrameValid() const
{
    WebFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
    WebFrameImpl* activeMatchFrame = mainFrameImpl->activeMatchFrame();
    return activeMatchFrame && activeMatchFrame->activeMatch() && activeMatchFrame->frame()->tree().isDescendantOf(mainFrameImpl->frame());
}

void TextFinder::updateFindMatchRects()
{
    IntSize currentContentsSize = m_ownerFrame.contentsSize();
    if (m_contentsSizeForCurrentFindMatchRects != currentContentsSize) {
        m_contentsSizeForCurrentFindMatchRects = currentContentsSize;
        m_findMatchRectsAreValid = false;
    }

    size_t deadMatches = 0;
    for (Vector<FindMatch>::iterator it = m_findMatchesCache.begin(); it != m_findMatchesCache.end(); ++it) {
        if (!it->m_range->boundaryPointsValid() || !it->m_range->startContainer()->inDocument())
            it->m_rect = FloatRect();
        else if (!m_findMatchRectsAreValid)
            it->m_rect = findInPageRectFromRange(it->m_range.get());

        if (it->m_rect.isEmpty())
            ++deadMatches;
    }

    // Remove any invalid matches from the cache.
    if (deadMatches) {
        WillBeHeapVector<FindMatch> filteredMatches;
        filteredMatches.reserveCapacity(m_findMatchesCache.size() - deadMatches);

        for (Vector<FindMatch>::const_iterator it = m_findMatchesCache.begin(); it != m_findMatchesCache.end(); ++it) {
            if (!it->m_rect.isEmpty())
                filteredMatches.append(*it);
        }

        m_findMatchesCache.swap(filteredMatches);
    }

    // Invalidate the rects in child frames. Will be updated later during traversal.
    if (!m_findMatchRectsAreValid)
        for (WebFrame* child = m_ownerFrame.firstChild(); child; child = child->nextSibling())
            toWebFrameImpl(child)->ensureTextFinder().m_findMatchRectsAreValid = false;

    m_findMatchRectsAreValid = true;
}

WebFloatRect TextFinder::activeFindMatchRect()
{
    if (!isActiveMatchFrameValid())
        return WebFloatRect();

    return WebFloatRect(findInPageRectFromRange(m_currentActiveMatchFrame->activeMatch()));
}

void TextFinder::findMatchRects(WebVector<WebFloatRect>& outputRects)
{
    Vector<WebFloatRect> matchRects;
    for (WebFrameImpl* frame = &m_ownerFrame; frame; frame = toWebFrameImpl(frame->traverseNext(false)))
        frame->ensureTextFinder().appendFindMatchRects(matchRects);

    outputRects = matchRects;
}

void TextFinder::appendFindMatchRects(Vector<WebFloatRect>& frameRects)
{
    updateFindMatchRects();
    frameRects.reserveCapacity(frameRects.size() + m_findMatchesCache.size());
    for (Vector<FindMatch>::const_iterator it = m_findMatchesCache.begin(); it != m_findMatchesCache.end(); ++it) {
        ASSERT(!it->m_rect.isEmpty());
        frameRects.append(it->m_rect);
    }
}

int TextFinder::selectNearestFindMatch(const WebFloatPoint& point, WebRect* selectionRect)
{
    TextFinder* bestFinder = 0;
    int indexInBestFrame = -1;
    float distanceInBestFrame = FLT_MAX;

    for (WebFrameImpl* frame = &m_ownerFrame; frame; frame = toWebFrameImpl(frame->traverseNext(false))) {
        float distanceInFrame;
        TextFinder& finder = frame->ensureTextFinder();
        int indexInFrame = finder.nearestFindMatch(point, distanceInFrame);
        if (distanceInFrame < distanceInBestFrame) {
            bestFinder = &finder;
            indexInBestFrame = indexInFrame;
            distanceInBestFrame = distanceInFrame;
        }
    }

    if (indexInBestFrame != -1)
        return bestFinder->selectFindMatch(static_cast<unsigned>(indexInBestFrame), selectionRect);

    return -1;
}

int TextFinder::nearestFindMatch(const FloatPoint& point, float& distanceSquared)
{
    updateFindMatchRects();

    int nearest = -1;
    distanceSquared = FLT_MAX;
    for (size_t i = 0; i < m_findMatchesCache.size(); ++i) {
        ASSERT(!m_findMatchesCache[i].m_rect.isEmpty());
        FloatSize offset = point - m_findMatchesCache[i].m_rect.center();
        float width = offset.width();
        float height = offset.height();
        float currentDistanceSquared = width * width + height * height;
        if (currentDistanceSquared < distanceSquared) {
            nearest = i;
            distanceSquared = currentDistanceSquared;
        }
    }
    return nearest;
}

int TextFinder::selectFindMatch(unsigned index, WebRect* selectionRect)
{
    ASSERT_WITH_SECURITY_IMPLICATION(index < m_findMatchesCache.size());

    RefPtrWillBeRawPtr<Range> range = m_findMatchesCache[index].m_range;
    if (!range->boundaryPointsValid() || !range->startContainer()->inDocument())
        return -1;

    // Check if the match is already selected.
    TextFinder& mainFrameTextFinder = m_ownerFrame.viewImpl()->mainFrameImpl()->ensureTextFinder();
    WebFrameImpl* activeMatchFrame = mainFrameTextFinder.m_currentActiveMatchFrame;
    if (&m_ownerFrame != activeMatchFrame || !m_activeMatch || !areRangesEqual(m_activeMatch.get(), range.get())) {
        if (isActiveMatchFrameValid())
            activeMatchFrame->ensureTextFinder().setMatchMarkerActive(false);

        m_activeMatchIndexInCurrentFrame = m_findMatchesCache[index].m_ordinal - 1;

        // Set this frame as the active frame (the one with the active highlight).
        mainFrameTextFinder.m_currentActiveMatchFrame = &m_ownerFrame;
        m_ownerFrame.viewImpl()->setFocusedFrame(&m_ownerFrame);

        m_activeMatch = range.release();
        setMarkerActive(m_activeMatch.get(), true);

        // Clear any user selection, to make sure Find Next continues on from the match we just activated.
        m_ownerFrame.frame()->selection().clear();

        // Make sure no node is focused. See http://crbug.com/38700.
        m_ownerFrame.frame()->document()->setFocusedElement(nullptr);
    }

    IntRect activeMatchRect;
    IntRect activeMatchBoundingBox = enclosingIntRect(RenderObject::absoluteBoundingBoxRectForRange(m_activeMatch.get()));

    if (!activeMatchBoundingBox.isEmpty()) {
        if (m_activeMatch->firstNode() && m_activeMatch->firstNode()->renderer()) {
            m_activeMatch->firstNode()->renderer()->scrollRectToVisible(
                activeMatchBoundingBox, ScrollAlignment::alignCenterIfNeeded, ScrollAlignment::alignCenterIfNeeded);
        }

        // Zoom to the active match.
        activeMatchRect = m_ownerFrame.frameView()->contentsToWindow(activeMatchBoundingBox);
        m_ownerFrame.viewImpl()->zoomToFindInPageRect(activeMatchRect);
    }

    if (selectionRect)
        *selectionRect = activeMatchRect;

    return ordinalOfFirstMatch() + m_activeMatchIndexInCurrentFrame + 1;
}

PassOwnPtr<TextFinder> TextFinder::create(WebFrameImpl& ownerFrame)
{
    return adoptPtr(new TextFinder(ownerFrame));
}

TextFinder::TextFinder(WebFrameImpl& ownerFrame)
    : m_ownerFrame(ownerFrame)
    , m_currentActiveMatchFrame(0)
    , m_activeMatchIndexInCurrentFrame(-1)
    , m_resumeScopingFromRange(nullptr)
    , m_lastMatchCount(-1)
    , m_totalMatchCount(-1)
    , m_framesScopingCount(-1)
    , m_findRequestIdentifier(-1)
    , m_nextInvalidateAfter(0)
    , m_findMatchMarkersVersion(0)
    , m_locatingActiveRect(false)
    , m_scopingInProgress(false)
    , m_lastFindRequestCompletedWithNoMatches(false)
    , m_findMatchRectsAreValid(false)
{
}

TextFinder::~TextFinder()
{
    cancelPendingScopingEffort();
}

void TextFinder::addMarker(Range* range, bool activeMatch)
{
    m_ownerFrame.frame()->document()->markers().addTextMatchMarker(range, activeMatch);
}

void TextFinder::setMarkerActive(Range* range, bool active)
{
    if (!range || range->collapsed(IGNORE_EXCEPTION))
        return;
    m_ownerFrame.frame()->document()->markers().setMarkersActive(range, active);
}

int TextFinder::ordinalOfFirstMatchForFrame(WebFrameImpl* frame) const
{
    int ordinal = 0;
    WebFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
    // Iterate from the main frame up to (but not including) |frame| and
    // add up the number of matches found so far.
    for (WebFrameImpl* it = mainFrameImpl; it != frame; it = toWebFrameImpl(it->traverseNext(true))) {
        TextFinder& finder = it->ensureTextFinder();
        if (finder.m_lastMatchCount > 0)
            ordinal += finder.m_lastMatchCount;
    }
    return ordinal;
}

bool TextFinder::shouldScopeMatches(const String& searchText)
{
    // Don't scope if we can't find a frame or a view.
    // The user may have closed the tab/application, so abort.
    // Also ignore detached frames, as many find operations report to the main frame.
    LocalFrame* frame = m_ownerFrame.frame();
    if (!frame || !frame->view() || !frame->page() || !m_ownerFrame.hasVisibleContent())
        return false;

    ASSERT(frame->document() && frame->view());

    // If the frame completed the scoping operation and found 0 matches the last
    // time it was searched, then we don't have to search it again if the user is
    // just adding to the search string or sending the same search string again.
    if (m_lastFindRequestCompletedWithNoMatches && !m_lastSearchString.isEmpty()) {
        // Check to see if the search string prefixes match.
        String previousSearchPrefix =
            searchText.substring(0, m_lastSearchString.length());

        if (previousSearchPrefix == m_lastSearchString)
            return false; // Don't search this frame, it will be fruitless.
    }

    return true;
}

void TextFinder::scopeStringMatchesSoon(int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
{
    m_deferredScopingWork.append(new DeferredScopeStringMatches(this, identifier, searchText, options, reset));
}

void TextFinder::callScopeStringMatches(DeferredScopeStringMatches* caller, int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
{
    m_deferredScopingWork.remove(m_deferredScopingWork.find(caller));
    scopeStringMatches(identifier, searchText, options, reset);

    // This needs to happen last since searchText is passed by reference.
    delete caller;
}

void TextFinder::invalidateIfNecessary()
{
    if (m_lastMatchCount <= m_nextInvalidateAfter)
        return;

    // FIXME: (http://b/1088165) Optimize the drawing of the tickmarks and
    // remove this. This calculation sets a milestone for when next to
    // invalidate the scrollbar and the content area. We do this so that we
    // don't spend too much time drawing the scrollbar over and over again.
    // Basically, up until the first 500 matches there is no throttle.
    // After the first 500 matches, we set set the milestone further and
    // further out (750, 1125, 1688, 2K, 3K).
    static const int startSlowingDownAfter = 500;
    static const int slowdown = 750;

    int i = m_lastMatchCount / startSlowingDownAfter;
    m_nextInvalidateAfter += i * slowdown;
    m_ownerFrame.invalidateScrollbar();
}

void TextFinder::flushCurrentScoping()
{
    flushCurrentScopingEffort(m_findRequestIdentifier);
}

void TextFinder::setMatchMarkerActive(bool active)
{
    setMarkerActive(m_activeMatch.get(), active);
}

void TextFinder::decrementFramesScopingCount(int identifier)
{
    // This frame has no further scoping left, so it is done. Other frames might,
    // of course, continue to scope matches.
    --m_framesScopingCount;

    // If this is the last frame to finish scoping we need to trigger the final
    // update to be sent.
    if (!m_framesScopingCount)
        m_ownerFrame.increaseMatchCount(0, identifier);
}

int TextFinder::ordinalOfFirstMatch() const
{
    return ordinalOfFirstMatchForFrame(&m_ownerFrame);
}

} // namespace blink