Implement range matching for TextUrlFragments

Implement range matching in TextFragmentFinder. The parsing of the
endText string is already implemented. TextFragmentFinder now
checks if the end text is present in the TextFragmentSelector,
searches for the first occurrence after it finds the start text,
and returns the total range.

Bug: 924964
Change-Id: Ifa913d1aef8d3406c1133608842c5a7d710f9f14
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/1573814
Reviewed-by: David Bokan <bokan@chromium.org>
Commit-Queue: Nick Burris <nburris@chromium.org>
Cr-Commit-Position: refs/heads/master@{#654134}
diff --git a/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor.cc b/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor.cc
index aa93dc0..10c3a1f 100644
--- a/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor.cc
+++ b/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor.cc
@@ -136,12 +136,14 @@
     node.GetLayoutObject()->ScrollRectToVisible(
         bounding_box,
         WebScrollIntoViewParams(ScrollAlignment::kAlignCenterIfNeeded,
-                                ScrollAlignment::kAlignCenterIfNeeded,
+                                ScrollAlignment::kAlignToEdgeIfNeeded,
                                 kProgrammaticScroll));
   }
   EphemeralRange dom_range =
       EphemeralRange(ToPositionInDOMTree(range.StartPosition()),
                      ToPositionInDOMTree(range.EndPosition()));
+  // TODO(nburris): Determine what we should do with overlapping text matches.
+  // Currently, AddTextMatchMarker will crash when adding an overlapping marker.
   frame_->GetDocument()->Markers().AddTextMatchMarker(
       dom_range, TextMatchMarker::MatchStatus::kActive);
   frame_->GetEditor().SetMarkedTextMatchesAreHighlighted(true);
diff --git a/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor_test.cc b/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor_test.cc
index 3ca3d08..0526d49 100644
--- a/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor_test.cc
+++ b/third_party/blink/renderer/core/page/scrolling/text_fragment_anchor_test.cc
@@ -389,6 +389,227 @@
   EXPECT_TRUE(GetDocument().Markers().Markers().IsEmpty());
 }
 
+// Test matching a text range within the same element
+TEST_F(TextFragmentAnchorTest, SameElementTextRange) {
+  SimRequest request("https://example.com/test.html#targetText=this,page",
+                     "text/html");
+  LoadURL("https://example.com/test.html#targetText=this,page");
+  request.Complete(R"HTML(
+    <!DOCTYPE html>
+    <style>
+      body {
+        height: 1200px;
+      }
+      p {
+        position: absolute;
+        top: 1000px;
+      }
+    </style>
+    <p id="text">This is a test page</p>
+  )HTML");
+  Compositor().BeginFrame();
+
+  RunAsyncMatchingTasks();
+
+  EXPECT_EQ(1u, GetDocument().Markers().Markers().size());
+
+  // Expect marker on "This is a test page".
+  Text* text = ToText(GetDocument().getElementById("text")->firstChild());
+  DocumentMarkerVector markers = GetDocument().Markers().MarkersFor(
+      *text, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(1u, markers.size());
+  EXPECT_EQ(0u, markers.at(0)->StartOffset());
+  EXPECT_EQ(19u, markers.at(0)->EndOffset());
+}
+
+// Test matching a text range across two neighboring elements
+TEST_F(TextFragmentAnchorTest, NeighboringElementTextRange) {
+  SimRequest request("https://example.com/test.html#targetText=test,paragraph",
+                     "text/html");
+  LoadURL("https://example.com/test.html#targetText=test,paragraph");
+  request.Complete(R"HTML(
+    <!DOCTYPE html>
+    <style>
+      body {
+        height: 1200px;
+      }
+      p {
+        position: absolute;
+        top: 1000px;
+      }
+    </style>
+    <p id="text1">This is a test page</p>
+    <p id="text2">with another paragraph of text</p>
+  )HTML");
+  Compositor().BeginFrame();
+
+  RunAsyncMatchingTasks();
+
+  EXPECT_EQ(2u, GetDocument().Markers().Markers().size());
+
+  // Expect marker on "test page"
+  Text* text1 = ToText(GetDocument().getElementById("text1")->firstChild());
+  DocumentMarkerVector markers = GetDocument().Markers().MarkersFor(
+      *text1, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(1u, markers.size());
+  EXPECT_EQ(10u, markers.at(0)->StartOffset());
+  EXPECT_EQ(19u, markers.at(0)->EndOffset());
+
+  // Expect marker on "with another paragraph"
+  Text* text2 = ToText(GetDocument().getElementById("text2")->firstChild());
+  markers = GetDocument().Markers().MarkersFor(
+      *text2, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(1u, markers.size());
+  EXPECT_EQ(0u, markers.at(0)->StartOffset());
+  EXPECT_EQ(22u, markers.at(0)->EndOffset());
+}
+
+// Test matching a text range from an element to a deeper nested element
+TEST_F(TextFragmentAnchorTest, DifferentDepthElementTextRange) {
+  SimRequest request("https://example.com/test.html#targetText=test,paragraph",
+                     "text/html");
+  LoadURL("https://example.com/test.html#targetText=test,paragraph");
+  request.Complete(R"HTML(
+    <!DOCTYPE html>
+    <style>
+      body {
+        height: 1200px;
+      }
+      p {
+        position: absolute;
+        top: 1000px;
+      }
+    </style>
+    <p id="text1">This is a test page</p>
+    <div>
+      <p id="text2">with another paragraph of text</p>
+    </div>
+  )HTML");
+  Compositor().BeginFrame();
+
+  RunAsyncMatchingTasks();
+
+  EXPECT_EQ(2u, GetDocument().Markers().Markers().size());
+
+  // Expect marker on "test page"
+  Text* text1 = ToText(GetDocument().getElementById("text1")->firstChild());
+  DocumentMarkerVector markers = GetDocument().Markers().MarkersFor(
+      *text1, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(1u, markers.size());
+  EXPECT_EQ(10u, markers.at(0)->StartOffset());
+  EXPECT_EQ(19u, markers.at(0)->EndOffset());
+
+  // Expect marker on "with another paragraph"
+  Text* text2 = ToText(GetDocument().getElementById("text2")->firstChild());
+  markers = GetDocument().Markers().MarkersFor(
+      *text2, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(1u, markers.size());
+  EXPECT_EQ(0u, markers.at(0)->StartOffset());
+  EXPECT_EQ(22u, markers.at(0)->EndOffset());
+}
+
+// Ensure that we don't match anything if endText is not found.
+TEST_F(TextFragmentAnchorTest, TextRangeEndTextNotFound) {
+  SimRequest request("https://example.com/test.html#targetText=test,cat",
+                     "text/html");
+  LoadURL("https://example.com/test.html#targetText=test,cat");
+  request.Complete(R"HTML(
+    <!DOCTYPE html>
+    <style>
+      body {
+        height: 1200px;
+      }
+      p {
+        position: absolute;
+        top: 1000px;
+      }
+    </style>
+    <p id="text">This is a test page</p>
+  )HTML");
+  Compositor().BeginFrame();
+
+  RunAsyncMatchingTasks();
+
+  EXPECT_EQ(0u, GetDocument().Markers().Markers().size());
+  EXPECT_EQ(ScrollOffset(), LayoutViewport()->GetScrollOffset());
+}
+
+// Test matching multiple text ranges
+TEST_F(TextFragmentAnchorTest, MultipleTextRanges) {
+  SimRequest request(
+      "https://example.com/"
+      "test.html#targetText=test,with&targetText=paragraph,text",
+      "text/html");
+  LoadURL(
+      "https://example.com/"
+      "test.html#targetText=test,with&targetText=paragraph,text");
+  request.Complete(R"HTML(
+    <!DOCTYPE html>
+    <style>
+      body {
+        height: 1200px;
+      }
+      p {
+        position: absolute;
+        top: 1000px;
+      }
+    </style>
+    <p id="text1">This is a test page</p>
+    <div>
+      <p id="text2">with another paragraph of text</p>
+    </div>
+  )HTML");
+  Compositor().BeginFrame();
+
+  RunAsyncMatchingTasks();
+
+  EXPECT_EQ(3u, GetDocument().Markers().Markers().size());
+
+  // Expect marker on "test page"
+  Text* text1 = ToText(GetDocument().getElementById("text1")->firstChild());
+  DocumentMarkerVector markers = GetDocument().Markers().MarkersFor(
+      *text1, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(1u, markers.size());
+  EXPECT_EQ(10u, markers.at(0)->StartOffset());
+  EXPECT_EQ(19u, markers.at(0)->EndOffset());
+
+  // Expect markers on "with" and "paragraph of text"
+  Text* text2 = ToText(GetDocument().getElementById("text2")->firstChild());
+  markers = GetDocument().Markers().MarkersFor(
+      *text2, DocumentMarker::MarkerTypes::TextMatch());
+  EXPECT_EQ(2u, markers.size());
+  EXPECT_EQ(0u, markers.at(0)->StartOffset());
+  EXPECT_EQ(4u, markers.at(0)->EndOffset());
+  EXPECT_EQ(13u, markers.at(1)->StartOffset());
+  EXPECT_EQ(30u, markers.at(1)->EndOffset());
+}
+
+// Ensure we scroll to the beginning of a text range larger than the viewport.
+TEST_F(TextFragmentAnchorTest, DistantElementTextRange) {
+  SimRequest request("https://example.com/test.html#targetText=test,paragraph",
+                     "text/html");
+  LoadURL("https://example.com/test.html#targetText=test,paragraph");
+  request.Complete(R"HTML(
+    <!DOCTYPE html>
+    <style>
+      p {
+        margin-top: 3000px;
+      }
+    </style>
+    <p id="text">This is a test page</p>
+    <p>with another paragraph of text</p>
+  )HTML");
+  Compositor().BeginFrame();
+
+  RunAsyncMatchingTasks();
+
+  Element& p = *GetDocument().getElementById("text");
+  EXPECT_TRUE(ViewportRect().Contains(BoundingRectInFrame(p)))
+      << "<p> Element wasn't scrolled into view, viewport's scroll offset: "
+      << LayoutViewport()->GetScrollOffset().ToString();
+  EXPECT_EQ(2u, GetDocument().Markers().Markers().size());
+}
+
 }  // namespace
 
 }  // namespace blink
diff --git a/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc b/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc
index 5f5e30e..d19e159 100644
--- a/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc
+++ b/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc
@@ -16,13 +16,14 @@
 
 namespace blink {
 
-TextFragmentFinder::TextFragmentFinder(Client& client,
-                                       const TextFragmentSelector& selector)
-    : client_(client), selector_(selector) {}
+namespace {
 
-void TextFragmentFinder::FindMatch(Document& document) {
-  PositionInFlatTree search_start =
-      PositionInFlatTree::FirstPositionInNode(document);
+EphemeralRangeInFlatTree FindMatchFromPosition(
+    String search_text,
+    Document& document,
+    PositionInFlatTree search_start) {
+  if (search_text.IsEmpty())
+    return EphemeralRangeInFlatTree();
 
   PositionInFlatTree search_end;
   if (document.documentElement() && document.documentElement()->lastChild()) {
@@ -32,22 +33,18 @@
     search_end = PositionInFlatTree::LastPositionInNode(document);
   }
 
-  // TODO(bokan): Make FindMatch work asynchronously. https://crbug.com/930156.
   while (search_start != search_end) {
     // Find in the whole block.
     FindBuffer buffer(EphemeralRangeInFlatTree(search_start, search_end));
     const FindOptions find_options = kCaseInsensitive;
-    // TODO(bokan): We need to add the capability to match a snippet based on
-    // it's start and end. https://crbug.com/924964.
+
     std::unique_ptr<FindBuffer::Results> match_results =
-        buffer.FindMatches(selector_.Start(), find_options);
+        buffer.FindMatches(search_text, find_options);
 
     if (!match_results->IsEmpty()) {
       FindBuffer::BufferMatchResult match = match_results->front();
-      const EphemeralRangeInFlatTree ephemeral_match_range =
-          buffer.RangeFromBufferIndex(match.start, match.start + match.length);
-      client_.DidFindMatch(ephemeral_match_range);
-      break;
+      return buffer.RangeFromBufferIndex(match.start,
+                                         match.start + match.length);
     }
 
     // At this point, all text in the block collected above has been
@@ -57,14 +54,40 @@
     if (search_start.IsNull())
       break;
   }
+
+  return EphemeralRangeInFlatTree();
 }
 
-PositionInFlatTree TextFragmentFinder::FindStart() {
-  return PositionInFlatTree();
+}  // namespace
+
+TextFragmentFinder::TextFragmentFinder(Client& client,
+                                       const TextFragmentSelector& selector)
+    : client_(client), selector_(selector) {
+  DCHECK(!selector_.Start().IsEmpty());
 }
 
-PositionInFlatTree TextFragmentFinder::FindEnd() {
-  return PositionInFlatTree();
+void TextFragmentFinder::FindMatch(Document& document) {
+  // TODO(crbug.com/930156): Make FindMatch work asynchronously.
+  EphemeralRangeInFlatTree start_match =
+      FindMatchFromPosition(selector_.Start(), document,
+                            PositionInFlatTree::FirstPositionInNode(document));
+  if (start_match.IsNull())
+    return;
+
+  if (selector_.End().IsEmpty()) {
+    client_.DidFindMatch(start_match);
+  } else {
+    // TODO(crbug.com/924964): Determine what we should do if the start text and
+    // end text are the same (and there are no context terms). This
+    // implementation continues searching for the next instance of the text,
+    // from the end of the first instance.
+    EphemeralRangeInFlatTree end_match = FindMatchFromPosition(
+        selector_.End(), document, start_match.EndPosition());
+    if (!end_match.IsNull()) {
+      client_.DidFindMatch(EphemeralRangeInFlatTree(start_match.StartPosition(),
+                                                    end_match.EndPosition()));
+    }
+  }
 }
 
 }  // namespace blink
diff --git a/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.h b/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.h
index 207dd4fc..b833f44 100644
--- a/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.h
+++ b/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.h
@@ -34,9 +34,6 @@
  private:
   Client& client_;
   const TextFragmentSelector selector_;
-
-  PositionInFlatTree FindStart();
-  PositionInFlatTree FindEnd();
 };
 
 }  // namespace blink