1 files changed, 152 insertions, 31 deletions
diff --git a/chromium/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc b/chromium/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc
index 5f5e30e0ea6..864c63fcffc 100644
--- a/chromium/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc
+++ b/chromium/third_party/blink/renderer/core/page/scrolling/text_fragment_finder.cc
@@ -11,19 +11,145 @@
 #include "third_party/blink/renderer/core/dom/range.h"
 #include "third_party/blink/renderer/core/editing/ephemeral_range.h"
 #include "third_party/blink/renderer/core/editing/finder/find_buffer.h"
+#include "third_party/blink/renderer/core/editing/iterators/character_iterator.h"
 #include "third_party/blink/renderer/core/editing/position.h"
 #include "third_party/blink/renderer/core/page/scrolling/text_fragment_selector.h"
 
 namespace blink {
 
+namespace {
+
+const char kNoContext[] = "";
+
+EphemeralRangeInFlatTree FindMatchInRange(String search_text,
+                                          PositionInFlatTree search_start,
+                                          PositionInFlatTree search_end) {
+  const FindOptions find_options = kCaseInsensitive;
+  const EphemeralRangeInFlatTree search_range(search_start, search_end);
+  return FindBuffer::FindMatchInRange(search_range, search_text, find_options);
+}
+
+PositionInFlatTree NextTextPosition(PositionInFlatTree position,
+                                    PositionInFlatTree end_position) {
+  const TextIteratorBehavior options =
+      TextIteratorBehavior::Builder().SetEmitsSpaceForNbsp(true).Build();
+  CharacterIteratorInFlatTree char_it(position, end_position, options);
+
+  for (; char_it.length(); char_it.Advance(1)) {
+    if (!IsSpaceOrNewline(char_it.CharacterAt(0)))
+      return char_it.StartPosition();
+  }
+
+  return end_position;
+}
+
+// Find and return the range of |search_text| if the first text in the search
+// range is |search_text|, skipping over whitespace and element boundaries.
+EphemeralRangeInFlatTree FindImmediateMatch(String search_text,
+                                            PositionInFlatTree search_start,
+                                            PositionInFlatTree search_end) {
+  if (search_text.IsEmpty())
+    return EphemeralRangeInFlatTree();
+
+  search_start = NextTextPosition(search_start, search_end);
+  if (search_start == search_end)
+    return EphemeralRangeInFlatTree();
+
+  FindBuffer buffer(EphemeralRangeInFlatTree(search_start, search_end));
+  const FindOptions find_options = kCaseInsensitive;
+
+  std::unique_ptr<FindBuffer::Results> match_results =
+      buffer.FindMatches(search_text, find_options);
+
+  if (!match_results->IsEmpty() && match_results->front().start == 0u) {
+    FindBuffer::BufferMatchResult match = match_results->front();
+    return buffer.RangeFromBufferIndex(match.start, match.start + match.length);
+  }
+
+  return EphemeralRangeInFlatTree();
+}
+
+EphemeralRangeInFlatTree FindMatchInRangeWithContext(
+    const String& search_text,
+    const String& prefix,
+    const String& suffix,
+    PositionInFlatTree search_start,
+    PositionInFlatTree search_end) {
+  while (search_start != search_end) {
+    EphemeralRangeInFlatTree potential_match;
+
+    if (!prefix.IsEmpty()) {
+      EphemeralRangeInFlatTree prefix_match =
+          FindMatchInRange(prefix, search_start, search_end);
+
+      // No prefix_match in remaining range
+      if (prefix_match.IsNull())
+        return EphemeralRangeInFlatTree();
+
+      search_start = prefix_match.EndPosition();
+      potential_match =
+          FindImmediateMatch(search_text, search_start, search_end);
+
+      // No search_text match after current prefix_match
+      if (potential_match.IsNull())
+        continue;
+    } else {
+      potential_match = FindMatchInRange(search_text, search_start, search_end);
+
+      // No search_text match in remaining range
+      if (potential_match.IsNull())
+        return EphemeralRangeInFlatTree();
+    }
+
+    DCHECK(potential_match.IsNotNull());
+    search_start = potential_match.EndPosition();
+    if (!suffix.IsEmpty()) {
+      EphemeralRangeInFlatTree suffix_match =
+          FindImmediateMatch(suffix, search_start, search_end);
+
+      // No suffix match after current potential_match
+      if (suffix_match.IsNull())
+        continue;
+    }
+
+    // If we reach here without a return or continue, we have a full match.
+    return potential_match;
+  }
+
+  return EphemeralRangeInFlatTree();
+}
+
+}  // namespace
+
 TextFragmentFinder::TextFragmentFinder(Client& client,
                                        const TextFragmentSelector& selector)
-    : client_(client), selector_(selector) {}
+    : client_(client), selector_(selector) {
+  DCHECK(!selector_.Start().IsEmpty());
+}
 
 void TextFragmentFinder::FindMatch(Document& document) {
   PositionInFlatTree search_start =
       PositionInFlatTree::FirstPositionInNode(document);
 
+  EphemeralRangeInFlatTree match =
+      FindMatchFromPosition(document, search_start);
+
+  if (match.IsNotNull()) {
+    client_.DidFindMatch(match);
+
+    // Continue searching to see if we have an ambiguous selector.
+    // TODO(crbug.com/919204): This is temporary and only for measuring
+    // ambiguous matching during prototyping.
+    EphemeralRangeInFlatTree ambiguous_match =
+        FindMatchFromPosition(document, match.EndPosition());
+    if (ambiguous_match.IsNotNull())
+      client_.DidFindAmbiguousMatch();
+  }
+}
+
+EphemeralRangeInFlatTree TextFragmentFinder::FindMatchFromPosition(
+    Document& document,
+    PositionInFlatTree search_start) {
   PositionInFlatTree search_end;
   if (document.documentElement() && document.documentElement()->lastChild()) {
     search_end =
@@ -32,39 +158,34 @@ void TextFragmentFinder::FindMatch(Document& document) {
     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);
-
-    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;
-    }
+  // TODO(crbug.com/930156): Make FindMatch work asynchronously.
+  EphemeralRangeInFlatTree match;
+  if (selector_.Type() == TextFragmentSelector::kExact) {
+    match = FindMatchInRangeWithContext(selector_.Start(), selector_.Prefix(),
+                                        selector_.Suffix(), search_start,
+                                        search_end);
+  } else {
+    EphemeralRangeInFlatTree start_match =
+        FindMatchInRangeWithContext(selector_.Start(), selector_.Prefix(),
+                                    kNoContext, search_start, search_end);
+    if (start_match.IsNull())
+      return start_match;
 
-    // At this point, all text in the block collected above has been
-    // processed. Now we move to the next block if there's any,
-    // otherwise we should stop.
-    search_start = buffer.PositionAfterBlock();
-    if (search_start.IsNull())
-      break;
+    // 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.
+    search_start = start_match.EndPosition();
+    EphemeralRangeInFlatTree end_match = FindMatchInRangeWithContext(
+        selector_.End(), kNoContext, selector_.Suffix(), search_start,
+        search_end);
+    if (end_match.IsNotNull()) {
+      match = EphemeralRangeInFlatTree(start_match.StartPosition(),
+                                       end_match.EndPosition());
+    }
   }
-}
-
-PositionInFlatTree TextFragmentFinder::FindStart() {
-  return PositionInFlatTree();
-}
 
-PositionInFlatTree TextFragmentFinder::FindEnd() {
-  return PositionInFlatTree();
+  return match;
 }
 
 }  // namespace blink