[WIP] Find LayoutSelection start/end w/o VisibleSelection.

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

Index: third_party/WebKit/Source/core/editing/LayoutSelection.cpp
diff --git a/third_party/WebKit/Source/core/editing/LayoutSelection.cpp b/third_party/WebKit/Source/core/editing/LayoutSelection.cpp
index 8d87696471ccc12588e00077d133d8478233925b..6b93bc89dfa9700d94f9f58e27bf821efef544ef 100644
--- a/third_party/WebKit/Source/core/editing/LayoutSelection.cpp
+++ b/third_party/WebKit/Source/core/editing/LayoutSelection.cpp
@@ -27,6 +27,8 @@
 #include "core/editing/VisiblePosition.h"
 #include "core/editing/VisibleUnits.h"
 #include "core/html/TextControlElement.h"
+#include "core/layout/LayoutBlock.h"
+#include "core/layout/LayoutObject.h"
 #include "core/layout/LayoutView.h"
 #include "core/paint/PaintLayer.h"
 
@@ -109,31 +111,488 @@ LayoutSelection::LayoutSelection(FrameSelection& frame_selection)
       has_pending_selection_(false),
       paint_range_(SelectionPaintRange()) {}
 
+static bool IsSelectionAtomicAndVisible(LayoutObject* layout_object) {
+  if (!layout_object)
+    return false;
+  // return true;/*
+  if (layout_object->CanBeSelectionLeaf())
+    return true;
+  if (layout_object->IsImage() || layout_object->IsLayoutEmbeddedContent())
+    return true;
+  Node* node = layout_object->GetNode();
+  if (!node || !node->IsHTMLElement())
+    return false;
+  if (isHTMLTableElement(node))
+    return true;
+  if (IsHTMLFormControlElement(ToHTMLElement(*node)) ||
+      isHTMLLegendElement(ToHTMLElement(*node)) ||
+      isHTMLImageElement(ToHTMLElement(*node)) ||
+      isHTMLMeterElement(ToHTMLElement(*node)) ||
+      isHTMLProgressElement(ToHTMLElement(*node)))
+    return true;
+  return false;  //*/
+}
+
+static Vector<LayoutObject*> GetAncestors(LayoutObject* layout_object) {
+  Vector<LayoutObject*> ancestors;
+  for (LayoutObject* runner = layout_object; runner;) {
+    ancestors.push_back(runner);
+    LayoutObject* next = runner->Parent();
+    if (runner == next)
+      break;
+    runner = next;
+  }
+  return std::move(ancestors);
+}
+
+static Optional<int> compare(LayoutObject* a, LayoutObject* b) {
+  if (a == b)
+    return {0};
+  const Vector<LayoutObject*>& a_ancestors = GetAncestors(a);
+  const Vector<LayoutObject*>& b_ancestors = GetAncestors(b);
+  if (a_ancestors[a_ancestors.size() - 1] !=
+      b_ancestors[b_ancestors.size() - 1])
+    return {};
+  LayoutObject* recentAncestor = a_ancestors[a_ancestors.size() - 1];
+  size_t i = 0;
+  for (; i < std::min(a_ancestors.size(), b_ancestors.size()); ++i) {
+    if (a_ancestors[a_ancestors.size() - 1 - i] !=
+        b_ancestors[b_ancestors.size() - 1 - i])
+      break;
+    recentAncestor = a_ancestors[a_ancestors.size() - 1 - i];
+  }
+
+  if (i == a_ancestors.size())
+    return {-1};  // a is ancestor of b
+  if (i == b_ancestors.size())
+    return {1};  // b is ancestor of a
+  LayoutObject* const a_child_of_RA = a_ancestors[a_ancestors.size() - 1 - i];
+  LayoutObject* const b_child_of_RA = b_ancestors[b_ancestors.size() - 1 - i];
+  for (LayoutObject* runner = a_child_of_RA; runner;
+       runner = runner->NextSibling()) {
+    if (runner == b_child_of_RA)
+      return {-1};
+  }
+  return {1};
+}
+
+struct SelectionPosition {
+  STACK_ALLOCATED();
+
+  SelectionPosition() : SelectionPosition(nullptr, -1) {}
+  SelectionPosition(LayoutObject* layout_object, int offset)
+      : layout_object_(layout_object), offset_(offset) {}
+
+  SelectionPosition(const PositionInFlatTree& position) : SelectionPosition() {
+    if (position.IsNull())
+      return;
+    layout_object_ = position.AnchorNode()->GetLayoutObject();
+    offset_ = position.ComputeEditingOffset();
+  }
+
+  bool IsNull() const { return !layout_object_; }
+  PositionInFlatTree ToPositionInFlatTree() const {
+    if (IsNull())
+      return PositionInFlatTree();
+    return PositionInFlatTree(layout_object_->GetNode(), offset_);
+  }
+
+  LayoutObject* layout_object_;
+  int offset_;
+
+  bool operator==(const SelectionPosition& other) const {
+    return layout_object_ == other.layout_object_ && offset_ == other.offset_;
+  }
+  bool operator!=(const SelectionPosition& other) const {
+    return !operator==(other);
+  }
+};
+
+Node* ComputeNodeAfterPosition(const PositionInFlatTree& position) {
+  if (!position.AnchorNode())
+    return 0;
+
+  switch (position.AnchorType()) {
+    case PositionAnchorType::kBeforeChildren: {
+      if (Node* first_child =
+              FlatTreeTraversal::FirstChild(*position.AnchorNode()))
+        return first_child;
+      FlatTreeTraversal::NextSkippingChildren(*position.AnchorNode());
+    }
+    case PositionAnchorType::kAfterChildren:
+      return FlatTreeTraversal::NextSkippingChildren(*position.AnchorNode());
+    case PositionAnchorType::kOffsetInAnchor: {
+      if (position.AnchorNode()->IsCharacterDataNode())
+        return FlatTreeTraversal::Next(*position.AnchorNode());
+      if (Node* child_at = FlatTreeTraversal::ChildAt(
+              *position.AnchorNode(), position.OffsetInContainerNode()))
+        return child_at;
+      return FlatTreeTraversal::Next(*position.AnchorNode());
+    }
+    case PositionAnchorType::kBeforeAnchor:
+      return position.AnchorNode();
+    case PositionAnchorType::kAfterAnchor:
+      return FlatTreeTraversal::NextSkippingChildren(*position.AnchorNode());
+  }
+  NOTREACHED();
+  return 0;
+}
+
+static SelectionPosition FirstLayoutPosition(const PositionInFlatTree& start) {
+  if (start.AnchorNode()->IsTextNode() &&
+      start.AnchorNode()->GetLayoutObject()) {
+    return start;
+  }
+
+  LayoutObject* first_layout_object = nullptr;
+  for (Node* runner = ComputeNodeAfterPosition(start); runner;
+       runner = FlatTreeTraversal::Next(*runner)) {
+    if ((first_layout_object = runner->GetLayoutObject()))
+      break;
+  }
+  if (!first_layout_object)
+    return {};
+
+  for (LayoutObject* runner = first_layout_object; runner;
+       runner = runner->NextInPreOrder()) {
+    if (!IsSelectionAtomicAndVisible(runner))
+      continue;
+
+    return {runner, 0};
+  }
+  return {};
+}
+
+// Traverse FlatTree parent first backward.
+// It looks mirror of Next().
+static Node* Previous(const Node& node) {
+  if (FlatTreeTraversal::FirstChild(node))
+    return FlatTreeTraversal::LastWithin(node);
+  return FlatTreeTraversal::PreviousSkippingChildren(node);
+}
+
+// Traverse FlatTree parent first backward.
+// It looks mirror of Next().
+static LayoutObject* Previous(const LayoutObject& layout_object) {
+  if (LayoutObject* last_child = layout_object.SlowLastChild())
+    return last_child;
+  if (LayoutObject* previous_sibling = layout_object.PreviousSibling())
+    return previous_sibling;
+  for (LayoutObject* ancestor = layout_object.Parent(); ancestor;) {
+    LayoutObject* ancestor_prev_sib = ancestor->PreviousSibling();
+    if (ancestor_prev_sib)
+      return ancestor_prev_sib;
+    LayoutObject* parent = layout_object.Parent();
+    // LayoutTests/paint/invalidation/text-selection-rect-in-overflow-2.html
+    // makes infinite self-parent loop. Strange.
+    if (parent == ancestor)
+      return nullptr;
+    ancestor = parent;
+  }
+  return nullptr;
+}
+
+static Node* ComputeNodeBeforePosition(const PositionInFlatTree& position) {
+  if (!position.AnchorNode())
+    return nullptr;
+  switch (position.AnchorType()) {
+    case PositionAnchorType::kBeforeChildren:
+      return Previous(*position.AnchorNode());
+    case PositionAnchorType::kAfterChildren: {
+      if (Node* last_child =
+              FlatTreeTraversal::LastChild(*position.AnchorNode()))
+        return last_child;
+      return Previous(*position.AnchorNode());
+    }
+    case PositionAnchorType::kOffsetInAnchor: {
+      if (position.AnchorNode()->IsCharacterDataNode())
+        return Previous(*position.AnchorNode());
+      if (position.OffsetInContainerNode() == 0)
+        return Previous(*position.AnchorNode());
+      Node* child_before_offset = FlatTreeTraversal::ChildAt(
+          *position.AnchorNode(), position.OffsetInContainerNode() - 1);
+      return child_before_offset;
+    }
+    case PositionAnchorType::kBeforeAnchor:
+      return Previous(*position.AnchorNode());
+    case PositionAnchorType::kAfterAnchor:
+      return position.AnchorNode();
+  }
+  NOTREACHED();
+  return 0;
+}
+
+static SelectionPosition LastLayoutPosition(const PositionInFlatTree& end) {
+  if (end.AnchorNode()->IsTextNode() && end.AnchorNode()->GetLayoutObject()) {
+    return end;
+  }
+
+  LayoutObject* last_layout_object = nullptr;
+  for (Node* runner = ComputeNodeBeforePosition(end); runner;
+       runner = Previous(*runner)) {
+    if ((last_layout_object = runner->GetLayoutObject()))
+      break;
+  }
+  if (!last_layout_object)
+    return {};
+
+  for (LayoutObject* runner = last_layout_object; runner;
+       runner = Previous(*runner)) {
+    if (!IsSelectionAtomicAndVisible(runner))
+      continue;
+    if (Node* node = runner->GetNode()) {
+      if (node->IsTextNode()) {
+        return {runner, (int)ToText(runner->GetNode())->data().length()};
+      }
+    }
+
+    return {runner, 1};
+  }
+  return PositionInFlatTree();
+}
+
+static SelectionPosition ComputeStartRespectingGranularity(
+    const PositionInFlatTree passed_start,
+    TextGranularity granularity) {
+  DCHECK(passed_start.IsNotNull());
+
+  switch (granularity) {
+    case kCharacterGranularity:
+      // Don't do any expansion.
+      return FirstLayoutPosition(passed_start);
+    case kWordGranularity: {
+      // General case: Select the word the caret is positioned inside of.
+      // If the caret is on the word boundary, select the word according to
+      // |wordSide|.
+      // Edge case: If the caret is after the last word in a soft-wrapped line
+      // or the last word in the document, select that last word
+      // (LeftWordIfOnBoundary).
+      // Edge case: If the caret is after the last word in a paragraph, select
+      // from the the end of the last word to the line break (also
+      // RightWordIfOnBoundary);
+      const VisiblePositionInFlatTree& visible_start =
+          CreateVisiblePosition(passed_start);
+      if (IsEndOfEditableOrNonEditableContent(visible_start) ||
+          (IsEndOfLine(visible_start) && !IsStartOfLine(visible_start) &&
+           !IsEndOfParagraph(visible_start))) {
+        return StartOfWord(visible_start, kLeftWordIfOnBoundary)
+            .DeepEquivalent();
+      }
+      return StartOfWord(visible_start, kRightWordIfOnBoundary)
+          .DeepEquivalent();
+    }
+    case kLineGranularity:
+      return StartOfLine(CreateVisiblePosition(passed_start)).DeepEquivalent();
+    case kParagraphGranularity: {
+      const VisiblePositionInFlatTree pos = CreateVisiblePosition(passed_start);
+      if (IsStartOfLine(pos) && IsEndOfEditableOrNonEditableContent(pos))
+        return StartOfParagraph(PreviousPositionOf(pos)).DeepEquivalent();
+      return StartOfParagraph(pos).DeepEquivalent();
+    }
+    default:
+      break;
+  }
+
+  NOTREACHED();
+  return PositionInFlatTree();
+}
+
+static SelectionPosition ComputeEndRespectingGranularity(
+    const PositionInFlatTree& start,
+    const PositionInFlatTree& passed_end,
+    TextGranularity granularity) {
+  DCHECK(passed_end.IsNotNull());
+
+  switch (granularity) {
+    case kCharacterGranularity:
+      // Don't do any expansion.
+      return LastLayoutPosition(passed_end);
+    case kWordGranularity: {
+      // General case: Select the word the caret is positioned inside of.
+      // If the caret is on the word boundary, select the word according to
+      // |wordSide|.
+      // Edge case: If the caret is after the last word in a soft-wrapped line
+      // or the last word in the document, select that last word
+      // (|LeftWordIfOnBoundary|).
+      // Edge case: If the caret is after the last word in a paragraph, select
+      // from the the end of the last word to the line break (also
+      // |RightWordIfOnBoundary|);
+      const VisiblePositionInFlatTree& original_end =
+          CreateVisiblePosition(passed_end);
+      EWordSide side = kRightWordIfOnBoundary;
+      if (IsEndOfEditableOrNonEditableContent(original_end) ||
+          (IsEndOfLine(original_end) && !IsStartOfLine(original_end) &&
+           !IsEndOfParagraph(original_end)))
+        side = kLeftWordIfOnBoundary;
+
+      const VisiblePositionInFlatTree& word_end = EndOfWord(original_end, side);
+      if (!IsEndOfParagraph(original_end))
+        return word_end.DeepEquivalent();
+      if (IsEmptyTableCell(start.AnchorNode()))
+        return word_end.DeepEquivalent();
+
+      // Select the paragraph break (the space from the end of a paragraph
+      // to the start of the next one) to match TextEdit.
+      const VisiblePositionInFlatTree& end = NextPositionOf(word_end);
+      Element* const table = TableElementJustBefore(end);
+      if (!table) {
+        if (end.IsNull())
+          return word_end.DeepEquivalent();
+        return end.DeepEquivalent();
+      }
+
+      if (!IsEnclosingBlock(table))
+        return word_end.DeepEquivalent();
+
+      // The paragraph break after the last paragraph in the last cell
+      // of a block table ends at the start of the paragraph after the
+      // table.
+      const VisiblePositionInFlatTree next =
+          NextPositionOf(end, kCannotCrossEditingBoundary);
+      if (next.IsNull())
+        return word_end.DeepEquivalent();
+      return next.DeepEquivalent();
+    }
+    case kLineGranularity: {
+      const VisiblePositionInFlatTree& end =
+          EndOfLine(CreateVisiblePosition(passed_end));
+      if (!IsEndOfParagraph(end))
+        return end.DeepEquivalent();
+      // If the end of this line is at the end of a paragraph, include the
+      // space after the end of the line in the selection.
+      const VisiblePositionInFlatTree& next = NextPositionOf(end);
+      if (next.IsNull())
+        return end.DeepEquivalent();
+      return next.DeepEquivalent();
+    }
+    case kParagraphGranularity: {
+      const VisiblePositionInFlatTree& visible_paragraph_end =
+          EndOfParagraph(CreateVisiblePosition(passed_end));
+
+      // Include the "paragraph break" (the space from the end of this
+      // paragraph to the start of the next one) in the selection.
+      const VisiblePositionInFlatTree& end =
+          NextPositionOf(visible_paragraph_end);
+
+      Element* const table = TableElementJustBefore(end);
+      if (!table) {
+        if (end.IsNull())
+          return visible_paragraph_end.DeepEquivalent();
+        return end.DeepEquivalent();
+      }
+
+      if (!IsEnclosingBlock(table)) {
+        // There is no paragraph break after the last paragraph in the
+        // last cell of an inline table.
+        return visible_paragraph_end.DeepEquivalent();
+      }
+
+      // The paragraph break after the last paragraph in the last cell of
+      // a block table ends at the start of the paragraph after the table,
+      // not at the position just after the table.
+      const VisiblePositionInFlatTree& next =
+          NextPositionOf(end, kCannotCrossEditingBoundary);
+      if (next.IsNull())
+        return visible_paragraph_end.DeepEquivalent();
+      return next.DeepEquivalent();
+    }
+    default:
+      break;
+  }
+  NOTREACHED();
+  return PositionInFlatTree();
+}
+
 static bool ShouldShowBlockCursor(const FrameSelection& frame_selection,
-                                  const VisibleSelectionInFlatTree& selection) {
+                                  const SelectionPosition& start,
+                                  const SelectionPosition& end) {
   if (!frame_selection.ShouldShowBlockCursor())
     return false;
-  if (selection.GetSelectionType() != SelectionType::kCaretSelection)
+  if (start != end)
     return false;
-  if (IsLogicalEndOfLine(selection.VisibleEnd()))
+  if (IsLogicalEndOfLine(CreateVisiblePosition(start.ToPositionInFlatTree())))
     return false;
   return true;
 }
 
-static VisibleSelectionInFlatTree CalcSelection(
+#define MYDEBUG
+
+#ifdef MYDEBUG
+static VisibleSelectionInFlatTree createFromDOM(
+    const SelectionInDOMTree& selection_) {
+  SelectionInFlatTree::Builder builder;
+  const PositionInFlatTree& base = ToPositionInFlatTree(selection_.Base());
+  const PositionInFlatTree& extent = ToPositionInFlatTree(selection_.Extent());
+  if (base.IsNotNull() && extent.IsNotNull())
+    builder.SetBaseAndExtent(base, extent);
+  else if (base.IsNotNull())
+    builder.Collapse(base);
+  else if (extent.IsNotNull())
+    builder.Collapse(extent);
+  builder.SetAffinity(selection_.Affinity())
+      .SetHasTrailingWhitespace(selection_.HasTrailingWhitespace())
+      .SetGranularity(selection_.Granularity())
+      .SetIsDirectional(selection_.IsDirectional());
+  return CreateVisibleSelection(builder.Build());
+}
+#endif
+
+static std::pair<SelectionPosition, SelectionPosition> CalcSelection(
     const FrameSelection& frame_selection) {
+  const SelectionInDOMTree& selection_in_dom =
+      frame_selection.GetSelectionInDOMTree();
+#ifdef MYDEBUG
   const VisibleSelectionInFlatTree& original_selection =
-      frame_selection.ComputeVisibleSelectionInFlatTree();
-
-  if (!ShouldShowBlockCursor(frame_selection, original_selection))
-    return original_selection;
-
-  const PositionInFlatTree end_position = NextPositionOf(
-      original_selection.Start(), PositionMoveType::kGraphemeCluster);
-  return CreateVisibleSelection(
-      SelectionInFlatTree::Builder()
-          .SetBaseAndExtent(original_selection.Start(), end_position)
-          .Build());
+      createFromDOM(selection_in_dom);
+  const SelectionPosition original_start = original_selection.Start();
+  const SelectionPosition original_end = original_selection.End();
+  DCHECK(original_start.IsNull() || original_end.IsNull() ||
+         original_selection.IsNone() || true);
+#endif
+
+  const PositionInFlatTree& base =
+      ToPositionInFlatTree(selection_in_dom.Base());
+  const PositionInFlatTree& extent =
+      ToPositionInFlatTree(selection_in_dom.Extent());
+  const bool is_base_first = base <= extent;
+  const PositionInFlatTree& start = is_base_first ? base : extent;
+  const PositionInFlatTree& end = is_base_first ? extent : base;
+  DCHECK_LE(start, end);
+  if (start.IsNull() || end.IsNull())
+    return {PositionInFlatTree(), PositionInFlatTree()};
+
+  SelectionPosition start_mod_granularity = start;
+  SelectionPosition end_mod_granularity = end;
+  if (selection_in_dom.Granularity() != kCharacterGranularity || start != end) {
+    start_mod_granularity = ComputeStartRespectingGranularity(
+        start, selection_in_dom.Granularity());
+    end_mod_granularity = ComputeEndRespectingGranularity(
+        start, end, selection_in_dom.Granularity());
+  }
+// #define USE_ORIGINAL
+#ifdef USE_ORIGINAL
+  start_mod_granularity = original_start;
+  end_mod_granularity = original_end;
+#else
+  if (start_mod_granularity.IsNull() || end_mod_granularity.IsNull())
+    return {PositionInFlatTree(), PositionInFlatTree()};
+  Optional<int> comp = compare(start_mod_granularity.layout_object_,
+                               end_mod_granularity.layout_object_);
+  DCHECK(comp.has_value());
+  if (comp.value() > 0)
+    end_mod_granularity = start_mod_granularity;
+#endif
+  // DCHECK_LE(start_mod_granularity, end_mod_granularity);
+  /*const PositionInFlatTree& start_most_forward =
+  MostForwardCaretPosition(start_mod_granularity); const PositionInFlatTree&
+  end_most_backward = MostBackwardCaretPosition(end_mod_granularity);*/
+  if (!ShouldShowBlockCursor(frame_selection, start_mod_granularity,
+                             end_mod_granularity))
+    return {start_mod_granularity, end_mod_granularity};
+
+  const PositionInFlatTree end_position =
+      NextPositionOf(start, PositionMoveType::kGraphemeCluster);
+  return {start, end_position};
 }
 
 // Objects each have a single selection rect to examine.
@@ -297,23 +756,22 @@ static SelectionPaintRange CalcSelectionPaintRange(
   if (selection_in_dom.IsNone())
     return SelectionPaintRange();
 
-  const VisibleSelectionInFlatTree& selection = CalcSelection(frame_selection);
-  if (!selection.IsRange() || frame_selection.IsHidden())
+  const std::pair<SelectionPosition, SelectionPosition>& selection =
+      CalcSelection(frame_selection);
+  const SelectionPosition& start_pos = selection.first;
+  const SelectionPosition& end_pos = selection.second;
+  if (start_pos == end_pos || frame_selection.IsHidden())
     return SelectionPaintRange();
 
-  DCHECK(!selection.IsNone());
-  const PositionInFlatTree start_pos = selection.Start();
-  const PositionInFlatTree end_pos = selection.End();
-  DCHECK_LE(start_pos, end_pos);
-  LayoutObject* start_layout_object = start_pos.AnchorNode()->GetLayoutObject();
-  LayoutObject* end_layout_object = end_pos.AnchorNode()->GetLayoutObject();
+  // DCHECK_LE(start_pos, end_pos);
+  LayoutObject* start_layout_object = start_pos.layout_object_;
+  LayoutObject* end_layout_object = end_pos.layout_object_;
   DCHECK(start_layout_object);
   DCHECK(end_layout_object);
   DCHECK(start_layout_object->View() == end_layout_object->View());
 
-  return SelectionPaintRange(start_layout_object,
-                             start_pos.ComputeEditingOffset(),
-                             end_layout_object, end_pos.ComputeEditingOffset());
+  return SelectionPaintRange(start_layout_object, start_pos.offset_,
+                             end_layout_object, end_pos.offset_);
 }
 
 void LayoutSelection::Commit() {