src/third_party/WebKit/Source/web/TextFinder.cpp

   1 /*
   2  * Copyright (C) 2009 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31
  32 #include "config.h"
  33 #include "web/TextFinder.h"
  34
  35 #include "core/dom/DocumentMarker.h"
  36 #include "core/dom/DocumentMarkerController.h"
  37 #include "core/dom/Range.h"
  38 #include "core/dom/shadow/ShadowRoot.h"
  39 #include "core/editing/Editor.h"
  40 #include "core/editing/TextIterator.h"
  41 #include "core/editing/VisibleSelection.h"
  42 #include "core/frame/FrameView.h"
  43 #include "platform/Timer.h"
  44 #include "public/platform/WebVector.h"
  45 #include "public/web/WebFindOptions.h"
  46 #include "public/web/WebFrameClient.h"
  47 #include "public/web/WebViewClient.h"
  48 #include "web/FindInPageCoordinates.h"
  49 #include "web/WebLocalFrameImpl.h"
  50 #include "web/WebViewImpl.h"
  51 #include "wtf/CurrentTime.h"
  52
  53 using namespace WebCore;
  54
  55 namespace blink {
  56
  57 TextFinder::FindMatch::FindMatch(PassRefPtrWillBeRawPtr<Range> range, int ordinal)
  58     : m_range(range)
  59     , m_ordinal(ordinal)
  60 {
  61 }
  62
  63 void TextFinder::FindMatch::trace(WebCore::Visitor* visitor)
  64 {
  65     visitor->trace(m_range);
  66 }
  67
  68 class TextFinder::DeferredScopeStringMatches {
  69 public:
  70     DeferredScopeStringMatches(TextFinder* textFinder, int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
  71         : m_timer(this, &DeferredScopeStringMatches::doTimeout)
  72         , m_textFinder(textFinder)
  73         , m_identifier(identifier)
  74         , m_searchText(searchText)
  75         , m_options(options)
  76         , m_reset(reset)
  77     {
  78         m_timer.startOneShot(0.0, FROM_HERE);
  79     }
  80
  81 private:
  82     void doTimeout(Timer<DeferredScopeStringMatches>*)
  83     {
  84         m_textFinder->callScopeStringMatches(this, m_identifier, m_searchText, m_options, m_reset);
  85     }
  86
  87     Timer<DeferredScopeStringMatches> m_timer;
  88     TextFinder* m_textFinder;
  89     const int m_identifier;
  90     const WebString m_searchText;
  91     const WebFindOptions m_options;
  92     const bool m_reset;
  93 };
  94
  95 bool TextFinder::find(int identifier, const WebString& searchText, const WebFindOptions& options, bool wrapWithinFrame, WebRect* selectionRect)
  96 {
  97     if (!m_ownerFrame.frame() || !m_ownerFrame.frame()->page())
  98         return false;
  99
 100     WebLocalFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
 101
 102     if (!options.findNext)
 103         m_ownerFrame.frame()->page()->unmarkAllTextMatches();
 104     else
 105         setMarkerActive(m_activeMatch.get(), false);
 106
 107     if (m_activeMatch && &m_activeMatch->ownerDocument() != m_ownerFrame.frame()->document())
 108         m_activeMatch = nullptr;
 109
 110     // If the user has selected something since the last Find operation we want
 111     // to start from there. Otherwise, we start searching from where the last Find
 112     // operation left off (either a Find or a FindNext operation).
 113     VisibleSelection selection(m_ownerFrame.frame()->selection().selection());
 114     bool activeSelection = !selection.isNone();
 115     if (activeSelection) {
 116         m_activeMatch = selection.firstRange().get();
 117         m_ownerFrame.frame()->selection().clear();
 118     }
 119
 120     ASSERT(m_ownerFrame.frame() && m_ownerFrame.frame()->view());
 121     const FindOptions findOptions = (options.forward ? 0 : Backwards)
 122         | (options.matchCase ? 0 : CaseInsensitive)
 123         | (wrapWithinFrame ? WrapAround : 0)
 124         | (options.wordStart ? AtWordStarts : 0)
 125         | (options.medialCapitalAsWordStart ? TreatMedialCapitalAsWordStart : 0)
 126         | (options.findNext ? 0 : StartInSelection);
 127     m_activeMatch = m_ownerFrame.frame()->editor().findStringAndScrollToVisible(searchText, m_activeMatch.get(), findOptions);
 128
 129     if (!m_activeMatch) {
 130         // If we're finding next the next active match might not be in the current frame.
 131         // In this case we don't want to clear the matches cache.
 132         if (!options.findNext)
 133             clearFindMatchesCache();
 134
 135         m_ownerFrame.invalidateAll();
 136         return false;
 137     }
 138
 139 #if OS(ANDROID)
 140     m_ownerFrame.viewImpl()->zoomToFindInPageRect(m_ownerFrame.frameView()->contentsToWindow(enclosingIntRect(RenderObject::absoluteBoundingBoxRectForRange(m_activeMatch.get()))));
 141 #endif
 142
 143     setMarkerActive(m_activeMatch.get(), true);
 144     WebLocalFrameImpl* oldActiveFrame = mainFrameImpl->ensureTextFinder().m_currentActiveMatchFrame;
 145     mainFrameImpl->ensureTextFinder().m_currentActiveMatchFrame = &m_ownerFrame;
 146
 147     // Make sure no node is focused. See http://crbug.com/38700.
 148     m_ownerFrame.frame()->document()->setFocusedElement(nullptr);
 149
 150     if (!options.findNext || activeSelection) {
 151         // This is either a Find operation or a Find-next from a new start point
 152         // due to a selection, so we set the flag to ask the scoping effort
 153         // to find the active rect for us and report it back to the UI.
 154         m_locatingActiveRect = true;
 155     } else {
 156         if (oldActiveFrame != &m_ownerFrame) {
 157             if (options.forward)
 158                 m_activeMatchIndexInCurrentFrame = 0;
 159             else
 160                 m_activeMatchIndexInCurrentFrame = m_lastMatchCount - 1;
 161         } else {
 162             if (options.forward)
 163                 ++m_activeMatchIndexInCurrentFrame;
 164             else
 165                 --m_activeMatchIndexInCurrentFrame;
 166
 167             if (m_activeMatchIndexInCurrentFrame + 1 > m_lastMatchCount)
 168                 m_activeMatchIndexInCurrentFrame = 0;
 169             if (m_activeMatchIndexInCurrentFrame == -1)
 170                 m_activeMatchIndexInCurrentFrame = m_lastMatchCount - 1;
 171         }
 172         if (selectionRect) {
 173             *selectionRect = m_ownerFrame.frameView()->contentsToWindow(m_activeMatch->boundingBox());
 174             reportFindInPageSelection(*selectionRect, m_activeMatchIndexInCurrentFrame + 1, identifier);
 175         }
 176     }
 177
 178     return true;
 179 }
 180
 181 void TextFinder::stopFindingAndClearSelection()
 182 {
 183     cancelPendingScopingEffort();
 184
 185     // Remove all markers for matches found and turn off the highlighting.
 186     m_ownerFrame.frame()->document()->markers().removeMarkers(DocumentMarker::TextMatch);
 187     m_ownerFrame.frame()->editor().setMarkedTextMatchesAreHighlighted(false);
 188     clearFindMatchesCache();
 189
 190     // Let the frame know that we don't want tickmarks or highlighting anymore.
 191     m_ownerFrame.invalidateAll();
 192 }
 193
 194 void TextFinder::scopeStringMatches(int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
 195 {
 196     if (reset) {
 197         // This is a brand new search, so we need to reset everything.
 198         // Scoping is just about to begin.
 199         m_scopingInProgress = true;
 200
 201         // Need to keep the current identifier locally in order to finish the
 202         // request in case the frame is detached during the process.
 203         m_findRequestIdentifier = identifier;
 204
 205         // Clear highlighting for this frame.
 206         LocalFrame* frame = m_ownerFrame.frame();
 207         if (frame && frame->page() && frame->editor().markedTextMatchesAreHighlighted())
 208             frame->page()->unmarkAllTextMatches();
 209
 210         // Clear the tickmarks and results cache.
 211         clearFindMatchesCache();
 212
 213         // Clear the counters from last operation.
 214         m_lastMatchCount = 0;
 215         m_nextInvalidateAfter = 0;
 216         m_resumeScopingFromRange = nullptr;
 217
 218         // The view might be null on detached frames.
 219         if (frame && frame->page())
 220             m_ownerFrame.viewImpl()->mainFrameImpl()->ensureTextFinder().m_framesScopingCount++;
 221
 222         // Now, defer scoping until later to allow find operation to finish quickly.
 223         scopeStringMatchesSoon(identifier, searchText, options, false); // false means just reset, so don't do it again.
 224         return;
 225     }
 226
 227     if (!shouldScopeMatches(searchText)) {
 228         // Note that we want to defer the final update when resetting even if shouldScopeMatches returns false.
 229         // This is done in order to prevent sending a final message based only on the results of the first frame
 230         // since m_framesScopingCount would be 0 as other frames have yet to reset.
 231         finishCurrentScopingEffort(identifier);
 232         return;
 233     }
 234
 235     WebLocalFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
 236     Position searchStart = firstPositionInNode(m_ownerFrame.frame()->document());
 237     Position searchEnd = lastPositionInNode(m_ownerFrame.frame()->document());
 238     ASSERT(searchStart.document() == searchEnd.document());
 239
 240     if (m_resumeScopingFromRange) {
 241         // This is a continuation of a scoping operation that timed out and didn't
 242         // complete last time around, so we should start from where we left off.
 243         ASSERT(m_resumeScopingFromRange->collapsed());
 244         searchStart = m_resumeScopingFromRange->startPosition().next();
 245         if (searchStart.document() != searchEnd.document())
 246             return;
 247     }
 248
 249     // This timeout controls how long we scope before releasing control. This
 250     // value does not prevent us from running for longer than this, but it is
 251     // periodically checked to see if we have exceeded our allocated time.
 252     const double maxScopingDuration = 0.1; // seconds
 253
 254     int matchCount = 0;
 255     bool timedOut = false;
 256     double startTime = currentTime();
 257     do {
 258         // Find next occurrence of the search string.
 259         // FIXME: (http://crbug.com/6818) This WebKit operation may run for longer
 260         // than the timeout value, and is not interruptible as it is currently
 261         // written. We may need to rewrite it with interruptibility in mind, or
 262         // find an alternative.
 263         Position resultStart;
 264         Position resultEnd;
 265         findPlainText(searchStart, searchEnd, searchText, options.matchCase ? 0 : CaseInsensitive, resultStart, resultEnd);
 266         if (resultStart == resultEnd) {
 267             // Not found.
 268             break;
 269         }
 270
 271         RefPtrWillBeRawPtr<Range> resultRange = Range::create(*resultStart.document(), resultStart, resultEnd);
 272         if (resultRange->collapsed()) {
 273             // resultRange will be collapsed if the matched text spans over multiple TreeScopes.
 274             // FIXME: Show such matches to users.
 275             searchStart = resultStart.next();
 276             continue;
 277         }
 278
 279         ++matchCount;
 280
 281         // Catch a special case where Find found something but doesn't know what
 282         // the bounding box for it is. In this case we set the first match we find
 283         // as the active rect.
 284         IntRect resultBounds = resultRange->boundingBox();
 285         IntRect activeSelectionRect;
 286         if (m_locatingActiveRect) {
 287             activeSelectionRect = m_activeMatch.get() ?
 288                 m_activeMatch->boundingBox() : resultBounds;
 289         }
 290
 291         // If the Find function found a match it will have stored where the
 292         // match was found in m_activeSelectionRect on the current frame. If we
 293         // find this rect during scoping it means we have found the active
 294         // tickmark.
 295         bool foundActiveMatch = false;
 296         if (m_locatingActiveRect && (activeSelectionRect == resultBounds)) {
 297             // We have found the active tickmark frame.
 298             mainFrameImpl->ensureTextFinder().m_currentActiveMatchFrame = &m_ownerFrame;
 299             foundActiveMatch = true;
 300             // We also know which tickmark is active now.
 301             m_activeMatchIndexInCurrentFrame = matchCount - 1;
 302             // To stop looking for the active tickmark, we set this flag.
 303             m_locatingActiveRect = false;
 304
 305             // Notify browser of new location for the selected rectangle.
 306             reportFindInPageSelection(
 307                 m_ownerFrame.frameView()->contentsToWindow(resultBounds),
 308                 m_activeMatchIndexInCurrentFrame + 1,
 309                 identifier);
 310         }
 311
 312         addMarker(resultRange.get(), foundActiveMatch);
 313
 314         m_findMatchesCache.append(FindMatch(resultRange.get(), m_lastMatchCount + matchCount));
 315
 316         // Set the new start for the search range to be the end of the previous
 317         // result range. There is no need to use a VisiblePosition here,
 318         // since findPlainText will use a TextIterator to go over the visible
 319         // text nodes.
 320         searchStart = resultStart.next();
 321
 322         m_resumeScopingFromRange = Range::create(*resultStart.document(), resultStart, resultStart);
 323         timedOut = (currentTime() - startTime) >= maxScopingDuration;
 324     } while (!timedOut);
 325
 326     // Remember what we search for last time, so we can skip searching if more
 327     // letters are added to the search string (and last outcome was 0).
 328     m_lastSearchString = searchText;
 329
 330     if (matchCount > 0) {
 331         m_ownerFrame.frame()->editor().setMarkedTextMatchesAreHighlighted(true);
 332
 333         m_lastMatchCount += matchCount;
 334
 335         // Let the mainframe know how much we found during this pass.
 336         mainFrameImpl->increaseMatchCount(matchCount, identifier);
 337     }
 338
 339     if (timedOut) {
 340         // If we found anything during this pass, we should redraw. However, we
 341         // don't want to spam too much if the page is extremely long, so if we
 342         // reach a certain point we start throttling the redraw requests.
 343         if (matchCount > 0)
 344             invalidateIfNecessary();
 345
 346         // Scoping effort ran out of time, lets ask for another time-slice.
 347         scopeStringMatchesSoon(
 348             identifier,
 349             searchText,
 350             options,
 351             false); // don't reset.
 352         return; // Done for now, resume work later.
 353     }
 354
 355     finishCurrentScopingEffort(identifier);
 356 }
 357
 358 void TextFinder::flushCurrentScopingEffort(int identifier)
 359 {
 360     if (!m_ownerFrame.frame() || !m_ownerFrame.frame()->page())
 361         return;
 362
 363     WebLocalFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
 364     mainFrameImpl->ensureTextFinder().decrementFramesScopingCount(identifier);
 365 }
 366
 367 void TextFinder::finishCurrentScopingEffort(int identifier)
 368 {
 369     flushCurrentScopingEffort(identifier);
 370
 371     m_scopingInProgress = false;
 372     m_lastFindRequestCompletedWithNoMatches = !m_lastMatchCount;
 373
 374     // This frame is done, so show any scrollbar tickmarks we haven't drawn yet.
 375     m_ownerFrame.invalidateScrollbar();
 376 }
 377
 378 void TextFinder::cancelPendingScopingEffort()
 379 {
 380     deleteAllValues(m_deferredScopingWork);
 381     m_deferredScopingWork.clear();
 382
 383     m_activeMatchIndexInCurrentFrame = -1;
 384
 385     // Last request didn't complete.
 386     if (m_scopingInProgress)
 387         m_lastFindRequestCompletedWithNoMatches = false;
 388
 389     m_scopingInProgress = false;
 390 }
 391
 392 void TextFinder::increaseMatchCount(int identifier, int count)
 393 {
 394     if (count)
 395         ++m_findMatchMarkersVersion;
 396
 397     m_totalMatchCount += count;
 398
 399     // Update the UI with the latest findings.
 400     if (m_ownerFrame.client())
 401         m_ownerFrame.client()->reportFindInPageMatchCount(identifier, m_totalMatchCount, !m_framesScopingCount);
 402 }
 403
 404 void TextFinder::reportFindInPageSelection(const WebRect& selectionRect, int activeMatchOrdinal, int identifier)
 405 {
 406     // Update the UI with the latest selection rect.
 407     if (m_ownerFrame.client())
 408         m_ownerFrame.client()->reportFindInPageSelection(identifier, ordinalOfFirstMatch() + activeMatchOrdinal, selectionRect);
 409 }
 410
 411 void TextFinder::resetMatchCount()
 412 {
 413     if (m_totalMatchCount > 0)
 414         ++m_findMatchMarkersVersion;
 415
 416     m_totalMatchCount = 0;
 417     m_framesScopingCount = 0;
 418 }
 419
 420 void TextFinder::clearFindMatchesCache()
 421 {
 422     if (!m_findMatchesCache.isEmpty())
 423         m_ownerFrame.viewImpl()->mainFrameImpl()->ensureTextFinder().m_findMatchMarkersVersion++;
 424
 425     m_findMatchesCache.clear();
 426     m_findMatchRectsAreValid = false;
 427 }
 428
 429 bool TextFinder::isActiveMatchFrameValid() const
 430 {
 431     WebLocalFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
 432     WebLocalFrameImpl* activeMatchFrame = mainFrameImpl->activeMatchFrame();
 433     return activeMatchFrame && activeMatchFrame->activeMatch() && activeMatchFrame->frame()->tree().isDescendantOf(mainFrameImpl->frame());
 434 }
 435
 436 void TextFinder::updateFindMatchRects()
 437 {
 438     IntSize currentContentsSize = m_ownerFrame.contentsSize();
 439     if (m_contentsSizeForCurrentFindMatchRects != currentContentsSize) {
 440         m_contentsSizeForCurrentFindMatchRects = currentContentsSize;
 441         m_findMatchRectsAreValid = false;
 442     }
 443
 444     size_t deadMatches = 0;
 445     for (Vector<FindMatch>::iterator it = m_findMatchesCache.begin(); it != m_findMatchesCache.end(); ++it) {
 446         if (!it->m_range->boundaryPointsValid() || !it->m_range->startContainer()->inDocument())
 447             it->m_rect = FloatRect();
 448         else if (!m_findMatchRectsAreValid)
 449             it->m_rect = findInPageRectFromRange(it->m_range.get());
 450
 451         if (it->m_rect.isEmpty())
 452             ++deadMatches;
 453     }
 454
 455     // Remove any invalid matches from the cache.
 456     if (deadMatches) {
 457         WillBeHeapVector<FindMatch> filteredMatches;
 458         filteredMatches.reserveCapacity(m_findMatchesCache.size() - deadMatches);
 459
 460         for (Vector<FindMatch>::const_iterator it = m_findMatchesCache.begin(); it != m_findMatchesCache.end(); ++it) {
 461             if (!it->m_rect.isEmpty())
 462                 filteredMatches.append(*it);
 463         }
 464
 465         m_findMatchesCache.swap(filteredMatches);
 466     }
 467
 468     // Invalidate the rects in child frames. Will be updated later during traversal.
 469     if (!m_findMatchRectsAreValid)
 470         for (WebFrame* child = m_ownerFrame.firstChild(); child; child = child->nextSibling())
 471             toWebLocalFrameImpl(child)->ensureTextFinder().m_findMatchRectsAreValid = false;
 472
 473     m_findMatchRectsAreValid = true;
 474 }
 475
 476 WebFloatRect TextFinder::activeFindMatchRect()
 477 {
 478     if (!isActiveMatchFrameValid())
 479         return WebFloatRect();
 480
 481     return WebFloatRect(findInPageRectFromRange(m_currentActiveMatchFrame->activeMatch()));
 482 }
 483
 484 void TextFinder::findMatchRects(WebVector<WebFloatRect>& outputRects)
 485 {
 486     Vector<WebFloatRect> matchRects;
 487     for (WebLocalFrameImpl* frame = &m_ownerFrame; frame; frame = toWebLocalFrameImpl(frame->traverseNext(false)))
 488         frame->ensureTextFinder().appendFindMatchRects(matchRects);
 489
 490     outputRects = matchRects;
 491 }
 492
 493 void TextFinder::appendFindMatchRects(Vector<WebFloatRect>& frameRects)
 494 {
 495     updateFindMatchRects();
 496     frameRects.reserveCapacity(frameRects.size() + m_findMatchesCache.size());
 497     for (Vector<FindMatch>::const_iterator it = m_findMatchesCache.begin(); it != m_findMatchesCache.end(); ++it) {
 498         ASSERT(!it->m_rect.isEmpty());
 499         frameRects.append(it->m_rect);
 500     }
 501 }
 502
 503 int TextFinder::selectNearestFindMatch(const WebFloatPoint& point, WebRect* selectionRect)
 504 {
 505     TextFinder* bestFinder = 0;
 506     int indexInBestFrame = -1;
 507     float distanceInBestFrame = FLT_MAX;
 508
 509     for (WebLocalFrameImpl* frame = &m_ownerFrame; frame; frame = toWebLocalFrameImpl(frame->traverseNext(false))) {
 510         float distanceInFrame;
 511         TextFinder& finder = frame->ensureTextFinder();
 512         int indexInFrame = finder.nearestFindMatch(point, distanceInFrame);
 513         if (distanceInFrame < distanceInBestFrame) {
 514             bestFinder = &finder;
 515             indexInBestFrame = indexInFrame;
 516             distanceInBestFrame = distanceInFrame;
 517         }
 518     }
 519
 520     if (indexInBestFrame != -1)
 521         return bestFinder->selectFindMatch(static_cast<unsigned>(indexInBestFrame), selectionRect);
 522
 523     return -1;
 524 }
 525
 526 int TextFinder::nearestFindMatch(const FloatPoint& point, float& distanceSquared)
 527 {
 528     updateFindMatchRects();
 529
 530     int nearest = -1;
 531     distanceSquared = FLT_MAX;
 532     for (size_t i = 0; i < m_findMatchesCache.size(); ++i) {
 533         ASSERT(!m_findMatchesCache[i].m_rect.isEmpty());
 534         FloatSize offset = point - m_findMatchesCache[i].m_rect.center();
 535         float width = offset.width();
 536         float height = offset.height();
 537         float currentDistanceSquared = width * width + height * height;
 538         if (currentDistanceSquared < distanceSquared) {
 539             nearest = i;
 540             distanceSquared = currentDistanceSquared;
 541         }
 542     }
 543     return nearest;
 544 }
 545
 546 int TextFinder::selectFindMatch(unsigned index, WebRect* selectionRect)
 547 {
 548     ASSERT_WITH_SECURITY_IMPLICATION(index < m_findMatchesCache.size());
 549
 550     RefPtrWillBeRawPtr<Range> range = m_findMatchesCache[index].m_range;
 551     if (!range->boundaryPointsValid() || !range->startContainer()->inDocument())
 552         return -1;
 553
 554     // Check if the match is already selected.
 555     TextFinder& mainFrameTextFinder = m_ownerFrame.viewImpl()->mainFrameImpl()->ensureTextFinder();
 556     WebLocalFrameImpl* activeMatchFrame = mainFrameTextFinder.m_currentActiveMatchFrame;
 557     if (&m_ownerFrame != activeMatchFrame || !m_activeMatch || !areRangesEqual(m_activeMatch.get(), range.get())) {
 558         if (isActiveMatchFrameValid())
 559             activeMatchFrame->ensureTextFinder().setMatchMarkerActive(false);
 560
 561         m_activeMatchIndexInCurrentFrame = m_findMatchesCache[index].m_ordinal - 1;
 562
 563         // Set this frame as the active frame (the one with the active highlight).
 564         mainFrameTextFinder.m_currentActiveMatchFrame = &m_ownerFrame;
 565         m_ownerFrame.viewImpl()->setFocusedFrame(&m_ownerFrame);
 566
 567         m_activeMatch = range.release();
 568         setMarkerActive(m_activeMatch.get(), true);
 569
 570         // Clear any user selection, to make sure Find Next continues on from the match we just activated.
 571         m_ownerFrame.frame()->selection().clear();
 572
 573         // Make sure no node is focused. See http://crbug.com/38700.
 574         m_ownerFrame.frame()->document()->setFocusedElement(nullptr);
 575     }
 576
 577     IntRect activeMatchRect;
 578     IntRect activeMatchBoundingBox = enclosingIntRect(RenderObject::absoluteBoundingBoxRectForRange(m_activeMatch.get()));
 579
 580     if (!activeMatchBoundingBox.isEmpty()) {
 581         if (m_activeMatch->firstNode() && m_activeMatch->firstNode()->renderer()) {
 582             m_activeMatch->firstNode()->renderer()->scrollRectToVisible(
 583                 activeMatchBoundingBox, ScrollAlignment::alignCenterIfNeeded, ScrollAlignment::alignCenterIfNeeded);
 584         }
 585
 586         // Zoom to the active match.
 587         activeMatchRect = m_ownerFrame.frameView()->contentsToWindow(activeMatchBoundingBox);
 588         m_ownerFrame.viewImpl()->zoomToFindInPageRect(activeMatchRect);
 589     }
 590
 591     if (selectionRect)
 592         *selectionRect = activeMatchRect;
 593
 594     return ordinalOfFirstMatch() + m_activeMatchIndexInCurrentFrame + 1;
 595 }
 596
 597 PassOwnPtr<TextFinder> TextFinder::create(WebLocalFrameImpl& ownerFrame)
 598 {
 599     return adoptPtr(new TextFinder(ownerFrame));
 600 }
 601
 602 TextFinder::TextFinder(WebLocalFrameImpl& ownerFrame)
 603     : m_ownerFrame(ownerFrame)
 604     , m_currentActiveMatchFrame(0)
 605     , m_activeMatchIndexInCurrentFrame(-1)
 606     , m_resumeScopingFromRange(nullptr)
 607     , m_lastMatchCount(-1)
 608     , m_totalMatchCount(-1)
 609     , m_framesScopingCount(-1)
 610     , m_findRequestIdentifier(-1)
 611     , m_nextInvalidateAfter(0)
 612     , m_findMatchMarkersVersion(0)
 613     , m_locatingActiveRect(false)
 614     , m_scopingInProgress(false)
 615     , m_lastFindRequestCompletedWithNoMatches(false)
 616     , m_findMatchRectsAreValid(false)
 617 {
 618 }
 619
 620 TextFinder::~TextFinder()
 621 {
 622     cancelPendingScopingEffort();
 623 }
 624
 625 void TextFinder::addMarker(Range* range, bool activeMatch)
 626 {
 627     m_ownerFrame.frame()->document()->markers().addTextMatchMarker(range, activeMatch);
 628 }
 629
 630 void TextFinder::setMarkerActive(Range* range, bool active)
 631 {
 632     if (!range || range->collapsed())
 633         return;
 634     m_ownerFrame.frame()->document()->markers().setMarkersActive(range, active);
 635 }
 636
 637 int TextFinder::ordinalOfFirstMatchForFrame(WebLocalFrameImpl* frame) const
 638 {
 639     int ordinal = 0;
 640     WebLocalFrameImpl* mainFrameImpl = m_ownerFrame.viewImpl()->mainFrameImpl();
 641     // Iterate from the main frame up to (but not including) |frame| and
 642     // add up the number of matches found so far.
 643     for (WebLocalFrameImpl* it = mainFrameImpl; it != frame; it = toWebLocalFrameImpl(it->traverseNext(true))) {
 644         TextFinder& finder = it->ensureTextFinder();
 645         if (finder.m_lastMatchCount > 0)
 646             ordinal += finder.m_lastMatchCount;
 647     }
 648     return ordinal;
 649 }
 650
 651 bool TextFinder::shouldScopeMatches(const String& searchText)
 652 {
 653     // Don't scope if we can't find a frame or a view.
 654     // The user may have closed the tab/application, so abort.
 655     // Also ignore detached frames, as many find operations report to the main frame.
 656     LocalFrame* frame = m_ownerFrame.frame();
 657     if (!frame || !frame->view() || !frame->page() || !m_ownerFrame.hasVisibleContent())
 658         return false;
 659
 660     ASSERT(frame->document() && frame->view());
 661
 662     // If the frame completed the scoping operation and found 0 matches the last
 663     // time it was searched, then we don't have to search it again if the user is
 664     // just adding to the search string or sending the same search string again.
 665     if (m_lastFindRequestCompletedWithNoMatches && !m_lastSearchString.isEmpty()) {
 666         // Check to see if the search string prefixes match.
 667         String previousSearchPrefix =
 668             searchText.substring(0, m_lastSearchString.length());
 669
 670         if (previousSearchPrefix == m_lastSearchString)
 671             return false; // Don't search this frame, it will be fruitless.
 672     }
 673
 674     return true;
 675 }
 676
 677 void TextFinder::scopeStringMatchesSoon(int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
 678 {
 679     m_deferredScopingWork.append(new DeferredScopeStringMatches(this, identifier, searchText, options, reset));
 680 }
 681
 682 void TextFinder::callScopeStringMatches(DeferredScopeStringMatches* caller, int identifier, const WebString& searchText, const WebFindOptions& options, bool reset)
 683 {
 684     m_deferredScopingWork.remove(m_deferredScopingWork.find(caller));
 685     scopeStringMatches(identifier, searchText, options, reset);
 686
 687     // This needs to happen last since searchText is passed by reference.
 688     delete caller;
 689 }
 690
 691 void TextFinder::invalidateIfNecessary()
 692 {
 693     if (m_lastMatchCount <= m_nextInvalidateAfter)
 694         return;
 695
 696     // FIXME: (http://b/1088165) Optimize the drawing of the tickmarks and
 697     // remove this. This calculation sets a milestone for when next to
 698     // invalidate the scrollbar and the content area. We do this so that we
 699     // don't spend too much time drawing the scrollbar over and over again.
 700     // Basically, up until the first 500 matches there is no throttle.
 701     // After the first 500 matches, we set set the milestone further and
 702     // further out (750, 1125, 1688, 2K, 3K).
 703     static const int startSlowingDownAfter = 500;
 704     static const int slowdown = 750;
 705
 706     int i = m_lastMatchCount / startSlowingDownAfter;
 707     m_nextInvalidateAfter += i * slowdown;
 708     m_ownerFrame.invalidateScrollbar();
 709 }
 710
 711 void TextFinder::flushCurrentScoping()
 712 {
 713     flushCurrentScopingEffort(m_findRequestIdentifier);
 714 }
 715
 716 void TextFinder::setMatchMarkerActive(bool active)
 717 {
 718     setMarkerActive(m_activeMatch.get(), active);
 719 }
 720
 721 void TextFinder::decrementFramesScopingCount(int identifier)
 722 {
 723     // This frame has no further scoping left, so it is done. Other frames might,
 724     // of course, continue to scope matches.
 725     --m_framesScopingCount;
 726
 727     // If this is the last frame to finish scoping we need to trigger the final
 728     // update to be sent.
 729     if (!m_framesScopingCount)
 730         m_ownerFrame.increaseMatchCount(0, identifier);
 731 }
 732
 733 int TextFinder::ordinalOfFirstMatch() const
 734 {
 735     return ordinalOfFirstMatchForFrame(&m_ownerFrame);
 736 }
 737
 738 } // namespace blink