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