Move "word" granularity related functions to VisibleUnitWord.cpp

third_party/WebKit/Source/core/editing/VisibleUnitsWord.cpp

+/*
+ * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple 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:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``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 APPLE COMPUTER, INC. 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.
+ */
+
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "core/editing/VisibleUnits.h"
+
+#include "core/editing/EditingUtilities.h"
+#include "core/editing/iterators/BackwardsCharacterIterator.h"
+#include "core/editing/iterators/BackwardsTextBuffer.h"
+#include "core/editing/iterators/CharacterIterator.h"
+#include "core/editing/iterators/ForwardsTextBuffer.h"
+#include "core/editing/iterators/SimplifiedBackwardsTextIterator.h"
+#include "platform/instrumentation/tracing/TraceEvent.h"
+#include "platform/text/TextBoundaries.h"
+#include "platform/text/TextBreakIterator.h"
+
+namespace blink {
+
+namespace {
+
+template <typename Strategy>
+ContainerNode* NonShadowBoundaryParentNode(Node* node) {
+  ContainerNode* parent = Strategy::Parent(*node);
+  return parent && !parent->IsShadowRoot() ? parent : nullptr;
+}
+
+template <typename Strategy>
+Node* ParentEditingBoundary(const PositionTemplate<Strategy>& position) {
+  Node* const anchor_node = position.AnchorNode();
+  if (!anchor_node)
+    return nullptr;
+
+  Node* document_element = anchor_node->GetDocument().documentElement();
+  if (!document_element)
+    return nullptr;
+
+  Node* boundary = position.ComputeContainerNode();
+  while (boundary != document_element &&
+         NonShadowBoundaryParentNode<Strategy>(boundary) &&
+         HasEditableStyle(*anchor_node) ==
+             HasEditableStyle(*Strategy::Parent(*boundary)))
+    boundary = NonShadowBoundaryParentNode<Strategy>(boundary);
+
+  return boundary;
+}
+
+template <typename Strategy>
+PositionTemplate<Strategy> PreviousBoundaryAlgorithm(
+    const VisiblePositionTemplate<Strategy>& c,
+    BoundarySearchFunction search_function) {
+  DCHECK(c.IsValid()) << c;
+  const PositionTemplate<Strategy> pos = c.DeepEquivalent();
+  Node* boundary = ParentEditingBoundary(pos);
+  if (!boundary)
+    return PositionTemplate<Strategy>();
+
+  const PositionTemplate<Strategy> start =
+      PositionTemplate<Strategy>::EditingPositionOf(boundary, 0)
+          .ParentAnchoredEquivalent();
+  const PositionTemplate<Strategy> end = pos.ParentAnchoredEquivalent();
+
+  ForwardsTextBuffer suffix_string;
+  if (RequiresContextForWordBoundary(CharacterBefore(c))) {
+    TextIteratorAlgorithm<Strategy> forwards_iterator(
+        end, PositionTemplate<Strategy>::AfterNode(boundary));
+    while (!forwards_iterator.AtEnd()) {
+      forwards_iterator.CopyTextTo(&suffix_string);
+      int context_end_index = EndOfFirstWordBoundaryContext(
+          suffix_string.Data() + suffix_string.Size() -
+              forwards_iterator.length(),
+          forwards_iterator.length());
+      if (context_end_index < forwards_iterator.length()) {
+        suffix_string.Shrink(forwards_iterator.length() - context_end_index);
+        break;
+      }
+      forwards_iterator.Advance();
+    }
+  }
+
+  unsigned suffix_length = suffix_string.Size();
+  BackwardsTextBuffer string;
+  string.PushRange(suffix_string.Data(), suffix_string.Size());
+
+  SimplifiedBackwardsTextIteratorAlgorithm<Strategy> it(start, end);
+  int remaining_length = 0;
+  unsigned next = 0;
+  bool need_more_context = false;
+  while (!it.AtEnd()) {
+    bool in_text_security_mode = it.IsInTextSecurityMode();
+    // iterate to get chunks until the searchFunction returns a non-zero
+    // value.
+    if (!in_text_security_mode) {
+      int run_offset = 0;
+      do {
+        run_offset += it.CopyTextTo(&string, run_offset, string.Capacity());
+        // TODO(xiaochengh): The following line takes O(string.size()) time,
+        // which makes quadratic overall running time in the worst case.
+        // Should improve it in some way.
+        next = search_function(string.Data(), string.Size(),
+                               string.Size() - suffix_length,
+                               kMayHaveMoreContext, need_more_context);
+      } while (!next && run_offset < it.length());
+      if (next) {
+        remaining_length = it.length() - run_offset;
+        break;
+      }
+    } else {
+      // Treat bullets used in the text security mode as regular
+      // characters when looking for boundaries
+      string.PushCharacters('x', it.length());
+      next = 0;
+    }
+    it.Advance();
+  }
+  if (need_more_context) {
+    // The last search returned the beginning of the buffer and asked for
+    // more context, but there is no earlier text. Force a search with
+    // what's available.
+    // TODO(xiaochengh): Do we have to search the whole string?
+    next = search_function(string.Data(), string.Size(),
+                           string.Size() - suffix_length, kDontHaveMoreContext,
+                           need_more_context);
+    DCHECK(!need_more_context);
+  }
+
+  if (!next)
+    return it.AtEnd() ? it.StartPosition() : pos;
+
+  Node* node = it.StartContainer();
+  int boundary_offset = remaining_length + next;
+  if (node->IsTextNode() && boundary_offset <= node->MaxCharacterOffset()) {
+    // The next variable contains a usable index into a text node
+    return PositionTemplate<Strategy>(node, boundary_offset);
+  }
+
+  // Use the character iterator to translate the next value into a DOM
+  // position.
+  BackwardsCharacterIteratorAlgorithm<Strategy> char_it(start, end);
+  char_it.Advance(string.Size() - suffix_length - next);
+  // TODO(yosin) charIt can get out of shadow host.
+  return char_it.EndPosition();
+}
+
+template <typename Strategy>
+PositionTemplate<Strategy> NextBoundaryAlgorithm(
+    const VisiblePositionTemplate<Strategy>& c,
+    BoundarySearchFunction search_function) {
+  DCHECK(c.IsValid()) << c;
+  PositionTemplate<Strategy> pos = c.DeepEquivalent();
+  Node* boundary = ParentEditingBoundary(pos);
+  if (!boundary)
+    return PositionTemplate<Strategy>();
+
+  Document& d = boundary->GetDocument();
+  const PositionTemplate<Strategy> start(pos.ParentAnchoredEquivalent());
+
+  BackwardsTextBuffer prefix_string;
+  if (RequiresContextForWordBoundary(CharacterAfter(c))) {
+    SimplifiedBackwardsTextIteratorAlgorithm<Strategy> backwards_iterator(
+        PositionTemplate<Strategy>::FirstPositionInNode(&d), start);
+    while (!backwards_iterator.AtEnd()) {
+      backwards_iterator.CopyTextTo(&prefix_string);
+      int context_start_index = StartOfLastWordBoundaryContext(
+          prefix_string.Data(), backwards_iterator.length());
+      if (context_start_index > 0) {
+        prefix_string.Shrink(context_start_index);
+        break;
+      }
+      backwards_iterator.Advance();
+    }
+  }
+
+  unsigned prefix_length = prefix_string.Size();
+  ForwardsTextBuffer string;
+  string.PushRange(prefix_string.Data(), prefix_string.Size());
+
+  const PositionTemplate<Strategy> search_start =
+      PositionTemplate<Strategy>::EditingPositionOf(
+          start.AnchorNode(), start.OffsetInContainerNode());
+  const PositionTemplate<Strategy> search_end =
+      PositionTemplate<Strategy>::LastPositionInNode(boundary);
+  TextIteratorAlgorithm<Strategy> it(
+      search_start, search_end,
+      TextIteratorBehavior::Builder()
+          .SetEmitsCharactersBetweenAllVisiblePositions(true)
+          .Build());
+  const unsigned kInvalidOffset = static_cast<unsigned>(-1);
+  unsigned next = kInvalidOffset;
+  unsigned offset = prefix_length;
+  bool need_more_context = false;
+  while (!it.AtEnd()) {
+    // Keep asking the iterator for chunks until the search function
+    // returns an end value not equal to the length of the string passed to
+    // it.
+    bool in_text_security_mode = it.IsInTextSecurityMode();
+    if (!in_text_security_mode) {
+      int run_offset = 0;
+      do {
+        run_offset += it.CopyTextTo(&string, run_offset, string.Capacity());
+        next = search_function(string.Data(), string.Size(), offset,
+                               kMayHaveMoreContext, need_more_context);
+        if (!need_more_context) {
+          // When the search does not need more context, skip all examined
+          // characters except the last one, in case it is a boundary.
+          offset = string.Size();
+          U16_BACK_1(string.Data(), 0, offset);
+        }
+      } while (next == string.Size() && run_offset < it.length());
+      if (next != string.Size())
+        break;
+    } else {
+      // Treat bullets used in the text security mode as regular
+      // characters when looking for boundaries
+      string.PushCharacters('x', it.length());
+      next = string.Size();
+    }
+    it.Advance();
+  }
+  if (need_more_context) {
+    // The last search returned the end of the buffer and asked for more
+    // context, but there is no further text. Force a search with what's
+    // available.
+    // TODO(xiaochengh): Do we still have to search the whole string?
+    next = search_function(string.Data(), string.Size(), prefix_length,
+                           kDontHaveMoreContext, need_more_context);
+    DCHECK(!need_more_context);
+  }
+
+  if (it.AtEnd() && next == string.Size()) {
+    pos = it.StartPositionInCurrentContainer();
+  } else if (next != kInvalidOffset && next != prefix_length) {
+    // Use the character iterator to translate the next value into a DOM
+    // position.
+    CharacterIteratorAlgorithm<Strategy> char_it(
+        search_start, search_end,
+        TextIteratorBehavior::Builder()
+            .SetEmitsCharactersBetweenAllVisiblePositions(true)
+            .Build());
+    char_it.Advance(next - prefix_length - 1);
+    pos = char_it.EndPosition();
+
+    if (char_it.CharacterAt(0) == '\n') {
+      // TODO(yosin) workaround for collapsed range (where only start
+      // position is correct) emitted for some emitted newlines
+      // (see rdar://5192593)
+      const VisiblePositionTemplate<Strategy> vis_pos =
+          CreateVisiblePosition(pos);
+      if (vis_pos.DeepEquivalent() ==
+          CreateVisiblePosition(char_it.StartPosition()).DeepEquivalent()) {
+        char_it.Advance(1);
+        pos = char_it.StartPosition();
+      }
+    }
+  }
+
+  return pos;
+}
+
+unsigned StartWordBoundary(
+    const UChar* characters,
+    unsigned length,
+    unsigned offset,
+    BoundarySearchContextAvailability may_have_more_context,
+    bool& need_more_context) {
+  TRACE_EVENT0("blink", "startWordBoundary");
+  DCHECK(offset);
+  if (may_have_more_context &&
+      !StartOfLastWordBoundaryContext(characters, offset)) {
+    need_more_context = true;
+    return 0;
+  }
+  need_more_context = false;
+  int start, end;
+  U16_BACK_1(characters, 0, offset);
+  FindWordBoundary(characters, length, offset, &start, &end);
+  return start;
+}
+
+template <typename Strategy>
+PositionTemplate<Strategy> StartOfWordAlgorithm(
+    const VisiblePositionTemplate<Strategy>& c,
+    EWordSide side) {
+  DCHECK(c.IsValid()) << c;
+  // TODO(yosin) This returns a null VP for c at the start of the document
+  // and |side| == |LeftWordIfOnBoundary|
+  VisiblePositionTemplate<Strategy> p = c;
+  if (side == kRightWordIfOnBoundary) {
+    // at paragraph end, the startofWord is the current position
+    if (IsEndOfParagraph(c))
+      return c.DeepEquivalent();
+
+    p = NextPositionOf(c);
+    if (p.IsNull())
+      return c.DeepEquivalent();
+  }
+  return PreviousBoundary(p, StartWordBoundary);
+}
+
+unsigned EndWordBoundary(
+    const UChar* characters,
+    unsigned length,
+    unsigned offset,
+    BoundarySearchContextAvailability may_have_more_context,
+    bool& need_more_context) {
+  DCHECK_LE(offset, length);
+  if (may_have_more_context &&
+      EndOfFirstWordBoundaryContext(characters + offset, length - offset) ==
+          static_cast<int>(length - offset)) {
+    need_more_context = true;
+    return length;
+  }
+  need_more_context = false;
+  return FindWordEndBoundary(characters, length, offset);
+}
+
+template <typename Strategy>
+PositionTemplate<Strategy> EndOfWordAlgorithm(
+    const VisiblePositionTemplate<Strategy>& c,
+    EWordSide side) {
+  DCHECK(c.IsValid()) << c;
+  VisiblePositionTemplate<Strategy> p = c;
+  if (side == kLeftWordIfOnBoundary) {
+    if (IsStartOfParagraph(c))
+      return c.DeepEquivalent();
+
+    p = PreviousPositionOf(c);
+    if (p.IsNull())
+      return c.DeepEquivalent();
+  } else if (IsEndOfParagraph(c)) {
+    return c.DeepEquivalent();
+  }
+
+  return NextBoundary(p, EndWordBoundary);
+}
+
+unsigned PreviousWordPositionBoundary(
+    const UChar* characters,
+    unsigned length,
+    unsigned offset,
+    BoundarySearchContextAvailability may_have_more_context,
+    bool& need_more_context) {
+  if (may_have_more_context &&
+      !StartOfLastWordBoundaryContext(characters, offset)) {
+    need_more_context = true;
+    return 0;
+  }
+  need_more_context = false;
+  return FindNextWordFromIndex(characters, length, offset, false);
+}
+
+unsigned NextWordPositionBoundary(
+    const UChar* characters,
+    unsigned length,
+    unsigned offset,
+    BoundarySearchContextAvailability may_have_more_context,
+    bool& need_more_context) {
+  if (may_have_more_context &&
+      EndOfFirstWordBoundaryContext(characters + offset, length - offset) ==
+          static_cast<int>(length - offset)) {
+    need_more_context = true;
+    return length;
+  }
+  need_more_context = false;
+  return FindNextWordFromIndex(characters, length, offset, true);
+}
+
+}  // namespace
+
+Position EndOfWordPosition(const VisiblePosition& position, EWordSide side) {
+  return EndOfWordAlgorithm<EditingStrategy>(position, side);
+}
+
+VisiblePosition EndOfWord(const VisiblePosition& position, EWordSide side) {
+  return CreateVisiblePosition(EndOfWordPosition(position, side),
+                               VP_UPSTREAM_IF_POSSIBLE);
+}
+
+PositionInFlatTree EndOfWordPosition(const VisiblePositionInFlatTree& position,
+                                     EWordSide side) {
+  return EndOfWordAlgorithm<EditingInFlatTreeStrategy>(position, side);
+}
+
+VisiblePositionInFlatTree EndOfWord(const VisiblePositionInFlatTree& position,
+                                    EWordSide side) {
+  return CreateVisiblePosition(EndOfWordPosition(position, side),
+                               VP_UPSTREAM_IF_POSSIBLE);
+}
+
+Position NextBoundary(const VisiblePosition& visible_position,
+                      BoundarySearchFunction search_function) {
+  return NextBoundaryAlgorithm(visible_position, search_function);
+}
+
+PositionInFlatTree NextBoundary(
+    const VisiblePositionInFlatTree& visible_position,
+    BoundarySearchFunction search_function) {
+  return NextBoundaryAlgorithm(visible_position, search_function);
+}
+
+VisiblePosition NextWordPosition(const VisiblePosition& c) {
+  DCHECK(c.IsValid()) << c;
+  VisiblePosition next = CreateVisiblePosition(
+      NextBoundary(c, NextWordPositionBoundary), VP_UPSTREAM_IF_POSSIBLE);
+  return HonorEditingBoundaryAtOrAfter(next, c.DeepEquivalent());
+}
+
+Position PreviousBoundary(const VisiblePosition& visible_position,
+                          BoundarySearchFunction search_function) {
+  return PreviousBoundaryAlgorithm(visible_position, search_function);
+}
+
+PositionInFlatTree PreviousBoundary(
+    const VisiblePositionInFlatTree& visible_position,
+    BoundarySearchFunction search_function) {
+  return PreviousBoundaryAlgorithm(visible_position, search_function);
+}
+
+VisiblePosition PreviousWordPosition(const VisiblePosition& c) {
+  DCHECK(c.IsValid()) << c;
+  VisiblePosition prev =
+      CreateVisiblePosition(PreviousBoundary(c, PreviousWordPositionBoundary));
+  return HonorEditingBoundaryAtOrBefore(prev, c.DeepEquivalent());
+}
+
+Position StartOfWordPosition(const VisiblePosition& position, EWordSide side) {
+  return StartOfWordAlgorithm<EditingStrategy>(position, side);
+}
+
+VisiblePosition StartOfWord(const VisiblePosition& position, EWordSide side) {
+  return CreateVisiblePosition(StartOfWordPosition(position, side));
+}
+
+PositionInFlatTree StartOfWordPosition(
+    const VisiblePositionInFlatTree& position,
+    EWordSide side) {
+  return StartOfWordAlgorithm<EditingInFlatTreeStrategy>(position, side);
+}
+
+VisiblePositionInFlatTree StartOfWord(const VisiblePositionInFlatTree& position,
+                                      EWordSide side) {
+  return CreateVisiblePosition(StartOfWordPosition(position, side));
+}
+
+}  // namespace blink