[WIP][b:eae_mywip_paint] Paint Selection NG.

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

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights
  * reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
@@ skipping 10 matching lines @@
 
 #include "core/editing/LayoutSelection.h"
 
 #include "core/dom/Document.h"
 #include "core/editing/EditingUtilities.h"
 #include "core/editing/FrameSelection.h"
 #include "core/editing/VisiblePosition.h"
 #include "core/editing/VisibleUnits.h"
 #include "core/html/TextControlElement.h"
 #include "core/layout/LayoutView.h"
+#include "core/layout/ng/inline/ng_inline_items_builder.h"
+#include "core/layout/ng/inline/ng_inline_node.h"
+#include "core/layout/ng/inline/ng_inline_node_data.h"
+#include "core/layout/ng/layout_ng_block_flow.h"
 #include "core/paint/PaintLayer.h"
 
 namespace blink {
 
 SelectionPaintRange::SelectionPaintRange(LayoutObject* start_layout_object,
                                          int start_offset,
                                          LayoutObject* end_layout_object,
                                          int end_offset)
     : start_layout_object_(start_layout_object),
       start_offset_(start_offset),
       end_layout_object_(end_layout_object),
       end_offset_(end_offset) {
   DCHECK(start_layout_object_);
   DCHECK(end_layout_object_);
   if (start_layout_object_ != end_layout_object_)
     return;
   DCHECK_LT(start_offset_, end_offset_);
 }
 
 bool SelectionPaintRange::operator==(const SelectionPaintRange& other) const {
   return start_layout_object_ == other.start_layout_object_ &&
          start_offset_ == other.start_offset_ &&
          end_layout_object_ == other.end_layout_object_ &&
          end_offset_ == other.end_offset_;
 }
 
 LayoutObject* SelectionPaintRange::StartLayoutObject() const {
-  DCHECK(!IsNull());
   return start_layout_object_;
 }
 
 int SelectionPaintRange::StartOffset() const {
-  DCHECK(!IsNull());
   return start_offset_;
 }
 
 LayoutObject* SelectionPaintRange::EndLayoutObject() const {
-  DCHECK(!IsNull());
   return end_layout_object_;
 }
 
 int SelectionPaintRange::EndOffset() const {
-  DCHECK(!IsNull());
   return end_offset_;
 }
 
 LayoutSelection::LayoutSelection(FrameSelection& frame_selection)
     : frame_selection_(&frame_selection),
       has_pending_selection_(false),
-      paint_range_(SelectionPaintRange()) {}
+      paint_range_(nullptr) {}
 
 static SelectionInFlatTree CalcSelection(
     const VisibleSelectionInFlatTree& original_selection,
     bool should_show_blok_cursor) {
   const PositionInFlatTree& start = original_selection.Start();
   const PositionInFlatTree& end = original_selection.End();
   SelectionType selection_type = original_selection.GetSelectionType();
   const TextAffinity affinity = original_selection.Affinity();
 
   bool paint_block_cursor =
@@ skipping 72 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(SelectedMap);
 };
 
 enum class CollectSelectedMapOption {
   kCollectBlock,
   kNotCollectBlock,
 };
 
 static SelectedMap CollectSelectedMap(const SelectionPaintRange& range,
                                       CollectSelectedMapOption option) {
-  if (range.IsNull())
-    return SelectedMap();
-
   SelectedMap selected_map;
 
   LayoutObject* const stop =
       LayoutObjectAfterPosition(range.EndLayoutObject(), range.EndOffset());
   for (LayoutObject* runner = range.StartLayoutObject();
        runner && (runner != stop); runner = runner->NextInPreOrder()) {
     if (!runner->CanBeSelectionLeaf() && runner != range.StartLayoutObject() &&
         runner != range.EndLayoutObject())
       continue;
     if (runner->GetSelectionState() == SelectionState::kNone)
@@ skipping 11 matching lines @@
           break;
         containing_block = containing_block->ContainingBlock();
       }
     }
   }
   return selected_map;
 }
 
 // Update the selection status of all LayoutObjects between |start| and |end|.
 static void SetSelectionState(const SelectionPaintRange& range) {
-  if (range.IsNull())
-    return;
-
   if (range.StartLayoutObject() == range.EndLayoutObject()) {
     range.StartLayoutObject()->SetSelectionStateIfNeeded(
         SelectionState::kStartAndEnd);
   } else {
     range.StartLayoutObject()->SetSelectionStateIfNeeded(
         SelectionState::kStart);
     range.EndLayoutObject()->SetSelectionStateIfNeeded(SelectionState::kEnd);
   }
 
   LayoutObject* const stop =
       LayoutObjectAfterPosition(range.EndLayoutObject(), range.EndOffset());
   for (LayoutObject* runner = range.StartLayoutObject();
        runner && runner != stop; runner = runner->NextInPreOrder()) {
     if (runner != range.StartLayoutObject() &&
         runner != range.EndLayoutObject() && runner->CanBeSelectionLeaf())
       runner->SetSelectionStateIfNeeded(SelectionState::kInside);
   }
 }
 
 // Set SetSelectionState and ShouldInvalidateSelection flag of LayoutObjects
 // comparing them in |new_range| and |old_range|.
 static void UpdateLayoutObjectState(const SelectionPaintRange& new_range,
-                                    const SelectionPaintRange& old_range) {
+                                    const SelectionPaintRange* old_range) {
   SelectedMap old_selected_map =
-      CollectSelectedMap(old_range, CollectSelectedMapOption::kCollectBlock);
+      old_range ? CollectSelectedMap(*old_range,
+                                     CollectSelectedMapOption::kCollectBlock)
+                : SelectedMap();
 
   // Now clear the selection.
   for (auto layout_object : old_selected_map.object_map.Keys())
     layout_object->SetSelectionStateIfNeeded(SelectionState::kNone);
 
   SetSelectionState(new_range);
 
   // Now that the selection state has been updated for the new objects, walk
   // them again and put them in the new objects list.
   // TODO(editing-dev): |new_selected_map| doesn't really need to store the
   // SelectionState, it's just more convenient to have it use the same data
   // structure as |old_selected_map|.
   SelectedMap new_selected_map =
       CollectSelectedMap(new_range, CollectSelectedMapOption::kCollectBlock);
 
   // Have any of the old selected objects changed compared to the new selection?
   for (const auto& pair : old_selected_map.object_map) {
     LayoutObject* obj = pair.key;
     SelectionState new_selection_state = obj->GetSelectionState();
     SelectionState old_selection_state = pair.value;
     if (new_selection_state != old_selection_state ||
         (new_range.StartLayoutObject() == obj &&
-         new_range.StartOffset() != old_range.StartOffset()) ||
+         new_range.StartOffset() != old_range->StartOffset()) ||
         (new_range.EndLayoutObject() == obj &&
-         new_range.EndOffset() != old_range.EndOffset())) {
+         new_range.EndOffset() != old_range->EndOffset())) {
       obj->SetShouldInvalidateSelection();
       new_selected_map.object_map.erase(obj);
     }
   }
 
   // Any new objects that remain were not found in the old objects dict, and so
   // they need to be updated.
   for (auto layout_object : new_selected_map.object_map.Keys())
     layout_object->SetShouldInvalidateSelection();
 
   // Have any of the old blocks changed?
   for (const auto& pair : old_selected_map.block_map) {
     LayoutBlock* block = pair.key;
     SelectionState new_selection_state = block->GetSelectionState();
     SelectionState old_selection_state = pair.value;
     if (new_selection_state != old_selection_state) {
       block->SetShouldInvalidateSelection();
       new_selected_map.block_map.erase(block);
     }
   }
 
   // Any new blocks that remain were not found in the old blocks dict, and so
   // they need to be updated.
   for (auto layout_object : new_selected_map.block_map.Keys())
     layout_object->SetShouldInvalidateSelection();
 }
 
+static LayoutBlockFlow* MostRecentLayoutBlockFlow(LayoutObject* layout_object) {
+  for (LayoutObject* runner = layout_object; runner && !runner->IsLayoutView();
+       runner = runner->ContainingBlock()) {

[kojii, 2017/06/16 11:25:56]

why ContainingBlock(), not Parent()?

[yoichio, 2017/06/21 08:16:43]

Perhaps its my misunderstanding. If LayoutBlockFlow is not only 
  LayoutBlock, it should be |Parent()|.

+    if (runner->IsLayoutBlockFlow())
+      return ToLayoutBlockFlow(runner);
+  }
+  return nullptr;
+}
+
+static int GetOffsetInMixedTree(Node* node,
+                                LayoutObject* layout_object,
+                                int offset) {
+  LayoutBlockFlow* start_block_flow = MostRecentLayoutBlockFlow(layout_object);
+  if (!start_block_flow || !start_block_flow->IsLayoutNGBlockFlow())
+    return offset;  // Legay. Return DOM offset;

[yosin_UTC9, 2017/06/16 02:04:20]

nit: s/Legay/Legacy/

+
+  // TODO(yoichio): How about caching? Create takes
+  // O(<LayoutNGBlockflow.Data.text_content_>).
+  const NGTextOffsetMap& offset_map =
+      NGTextOffsetMap::Create(*ToLayoutNGBlockFlowOrDie(start_block_flow));
+  const Optional<int> ng_offset = offset_map.Get(node, offset);
+  return ng_offset.value();
+}
+
 std::pair<int, int> LayoutSelection::SelectionStartEnd() {
   Commit();
-  if (paint_range_.IsNull())
+  if (!paint_range_)
     return std::make_pair(-1, -1);
-  return std::make_pair(paint_range_.StartOffset(), paint_range_.EndOffset());
+  if (!RuntimeEnabledFeatures::LayoutNGEnabled()) {
+    return std::make_pair(paint_range_->StartOffset(),
+                          paint_range_->EndOffset());
+  }
+  // Layout NG mapping
+  const int start_offset_mixed = GetOffsetInMixedTree(
+      paint_range_->StartNode(), paint_range_->StartLayoutObject(),
+      paint_range_->StartOffset());
+  const int end_offset_mixed = GetOffsetInMixedTree(
+      paint_range_->EndNode(), paint_range_->EndLayoutObject(),
+      paint_range_->EndOffset());
+  return std::make_pair(start_offset_mixed, end_offset_mixed);
 }
 
 void LayoutSelection::ClearSelection() {
   // For querying Layer::compositingState()
   // This is correct, since destroying layout objects needs to cause eager paint
   // invalidations.
   DisableCompositingQueryAsserts disabler;
 
   // Just return if the selection is already empty.
-  if (paint_range_.IsNull())
+  if (!paint_range_)
     return;
 
   const SelectedMap& old_selected_map = CollectSelectedMap(
-      paint_range_, CollectSelectedMapOption::kNotCollectBlock);
+      *paint_range_, CollectSelectedMapOption::kNotCollectBlock);
   // Clear SelectionState and invalidation.
   for (auto layout_object : old_selected_map.object_map.Keys()) {
     const SelectionState old_state = layout_object->GetSelectionState();
     layout_object->SetSelectionStateIfNeeded(SelectionState::kNone);
     if (layout_object->GetSelectionState() == old_state)
       continue;
     layout_object->SetShouldInvalidateSelection();
   }
 
   // Reset selection.
-  paint_range_ = SelectionPaintRange();
+  paint_range_ = nullptr;
 }
 
-static SelectionPaintRange CalcSelectionPaintRange(
+static SelectionPaintRange* CalcSelectionNG(

[yosin_UTC9, 2017/06/15 09:51:27]

If this function traverse flat tree and works on legacy tree, it is nice and we
can replace current implementation.

[yoichio, 2017/06/21 08:16:42]

I will rewrite w/o most.*CaretPosition() functions.

     const FrameSelection& frame_selection) {
+  const SelectionInDOMTree& selection_in_dom =
+      frame_selection.GetSelectionInDOMTree();
+  if (selection_in_dom.IsNone())
+    return nullptr;
+
+  // yoichio: Tthis should be on FlatTree.
+  const Position& start = selection_in_dom.ComputeStartPosition();

[yosin_UTC9, 2017/06/15 09:39:02]

Why don't you use flat tree version?

+  const Position& end = selection_in_dom.ComputeEndPosition();
+  LayoutObject* const start_layout_object =

[yosin_UTC9, 2017/06/16 02:04:20]

|start_layout_object| can be nullptr.
So, we need to find boundary layout object from start to end.

+      start.AnchorNode()->GetLayoutObject();
+  LayoutObject* const end_layout_object = end.AnchorNode()->GetLayoutObject();

[yosin_UTC9, 2017/06/16 02:04:20]

|end_layout_object_| can be nullptr.
So, we need to find boundary layout from end to start.

+
+  Node* start_node = nullptr;
+  LayoutObject* paint_range_start = nullptr;
+  int paint_range_start_offset = -1;
+  // Seek the first text node.
+  for (LayoutObject* runner = start_layout_object;
+       runner && runner != end_layout_object->NextInPreOrder();
+       runner = runner->NextInPreOrder()) {
+    if (runner->IsText() && runner->GetNode()->IsTextNode()) {
+      start_node = runner->GetNode();
+      paint_range_start = runner;
+      if (runner == start_layout_object) {
+        paint_range_start_offset = start.ComputeEditingOffset();
+        break;
+      }
+      paint_range_start_offset = 0;
+      break;
+    }
+  }
+  DCHECK(paint_range_start);
+  // Should consider block cursor painting.
+  Node* end_node = nullptr;
+  LayoutObject* paint_range_end = nullptr;
+  int paint_range_end_offset = -1;
+  for (LayoutObject* runner = end_layout_object;
+       runner && runner != start_layout_object->PreviousInPreOrder();
+       runner = runner->PreviousInPreOrder()) {
+    if (runner->IsText() && runner->GetNode()->IsTextNode()) {
+      end_node = runner->GetNode();
+      paint_range_end = runner;
+      if (runner == end_layout_object) {
+        paint_range_end_offset = end.ComputeEditingOffset();
+        break;
+      }
+      LayoutText* text = ToLayoutText(runner);
+      paint_range_end_offset = text->TextLength();
+      break;
+    }
+  }
+  DCHECK(paint_range_end);
+
+  return new SelectionPaintRange(start_node, paint_range_start,
+                                 paint_range_start_offset, end_node,
+                                 paint_range_end, paint_range_end_offset);
+}
+// if(RuntimeEnabledFeatures::LayoutNGEnabled()) {
+
+static SelectionPaintRange* CalcSelectionPaintRange(
+    const FrameSelection& frame_selection) {
+  if (RuntimeEnabledFeatures::LayoutNGEnabled())
+    return CalcSelectionNG(frame_selection);

[yosin_UTC9, 2017/06/15 09:39:02]

So, for painting selection, we need to have NG version of:
- VisibleSelection
- MostBackwardCaretPosition()
- MostForwardCaretPosition()

+
+  // NGMemo: ComputeVisibleSelectionInFlatTree depends on offsetmapping from
+  // DOM->NG.
   const VisibleSelectionInFlatTree& original_selection =
       frame_selection.ComputeVisibleSelectionInFlatTree();
   // Construct a new VisibleSolution, since visibleSelection() is not
   // necessarily valid, and the following steps assume a valid selection. See
   // <https://bugs.webkit.org/show_bug.cgi?id=69563> and
   // <rdar://problem/10232866>.
   const SelectionInFlatTree& new_selection = CalcSelection(
       original_selection, frame_selection.ShouldShowBlockCursor());
   const VisibleSelectionInFlatTree& selection =
       CreateVisibleSelection(new_selection);
 
   if (!selection.IsRange() || frame_selection.IsHidden())
-    return SelectionPaintRange();
+    return nullptr;
 
   DCHECK(!selection.IsNone());
   // Use the rightmost candidate for the start of the selection, and the
   // leftmost candidate for the end of the selection. Example: foo <a>bar</a>.
   // Imagine that a line wrap occurs after 'foo', and that 'bar' is selected.
   // If we pass [foo, 3] as the start of the selection, the selection painting
   // code will think that content on the line containing 'foo' is selected
   // and will fill the gap before 'bar'.
   PositionInFlatTree start_pos = selection.Start();
   const PositionInFlatTree most_forward_start =
       MostForwardCaretPosition(start_pos);
   if (IsVisuallyEquivalentCandidate(most_forward_start))
     start_pos = most_forward_start;
   PositionInFlatTree end_pos = selection.End();
   const PositionInFlatTree most_backward = MostBackwardCaretPosition(end_pos);
   if (IsVisuallyEquivalentCandidate(most_backward))
     end_pos = most_backward;
 
   DCHECK(start_pos.IsNotNull());
   DCHECK(end_pos.IsNotNull());
   DCHECK_LE(start_pos, end_pos);
   LayoutObject* start_layout_object = start_pos.AnchorNode()->GetLayoutObject();
   LayoutObject* end_layout_object = end_pos.AnchorNode()->GetLayoutObject();
   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 new SelectionPaintRange(
+      start_layout_object, start_pos.ComputeEditingOffset(), end_layout_object,
+      end_pos.ComputeEditingOffset());
 }
 
 void LayoutSelection::Commit() {
   if (!HasPendingSelection())
     return;
   has_pending_selection_ = false;
 
-  const SelectionPaintRange& new_range =
-      CalcSelectionPaintRange(*frame_selection_);
-  if (new_range.IsNull()) {
+  SelectionPaintRange* new_range = CalcSelectionPaintRange(*frame_selection_);
+  if (!new_range) {
     ClearSelection();
     return;
   }
   // Just return if the selection hasn't changed.
-  if (paint_range_ == new_range)
+  if (paint_range_ && *paint_range_ == *new_range)
     return;
 
   DCHECK(frame_selection_->GetDocument().GetLayoutView()->GetFrameView());
   DCHECK(!frame_selection_->GetDocument().NeedsLayoutTreeUpdate());
-  UpdateLayoutObjectState(new_range, paint_range_);
+  UpdateLayoutObjectState(*new_range, paint_range_);
   paint_range_ = new_range;
 }
 
 void LayoutSelection::OnDocumentShutdown() {
   has_pending_selection_ = false;
-  paint_range_ = SelectionPaintRange();
+  paint_range_ = nullptr;
 }
 
 static LayoutRect SelectionRectForLayoutObject(const LayoutObject* object) {
   if (!object->IsRooted())
     return LayoutRect();
 
   if (!object->CanUpdateSelectionOnRootLineBoxes())
     return LayoutRect();
 
   return object->SelectionRectInViewCoordinates();
 }
 
 IntRect LayoutSelection::SelectionBounds() {
   // Now create a single bounding box rect that encloses the whole selection.
   LayoutRect sel_rect;
 
   typedef HashSet<const LayoutBlock*> VisitedContainingBlockSet;
   VisitedContainingBlockSet visited_containing_blocks;
 
   Commit();
-  if (paint_range_.IsNull())
+  if (!paint_range_)
     return IntRect();
 
-  LayoutObject* os = paint_range_.StartLayoutObject();
-  LayoutObject* stop = LayoutObjectAfterPosition(paint_range_.EndLayoutObject(),
-                                                 paint_range_.EndOffset());
+  LayoutObject* os = paint_range_->StartLayoutObject();
+  LayoutObject* stop = LayoutObjectAfterPosition(
+      paint_range_->EndLayoutObject(), paint_range_->EndOffset());
   while (os && os != stop) {
-    if ((os->CanBeSelectionLeaf() || os == paint_range_.StartLayoutObject() ||
-         os == paint_range_.EndLayoutObject()) &&
+    if ((os->CanBeSelectionLeaf() || os == paint_range_->StartLayoutObject() ||
+         os == paint_range_->EndLayoutObject()) &&
         os->GetSelectionState() != SelectionState::kNone) {
       // Blocks are responsible for painting line gaps and margin gaps. They
       // must be examined as well.
       sel_rect.Unite(SelectionRectForLayoutObject(os));
       const LayoutBlock* cb = os->ContainingBlock();
       while (cb && !cb->IsLayoutView()) {
         sel_rect.Unite(SelectionRectForLayoutObject(cb));
         VisitedContainingBlockSet::AddResult add_result =
             visited_containing_blocks.insert(cb);
         if (!add_result.is_new_entry)
           break;
         cb = cb->ContainingBlock();
       }
     }
 
     os = os->NextInPreOrder();
   }
 
   return PixelSnappedIntRect(sel_rect);
 }
 
 void LayoutSelection::InvalidatePaintForSelection() {
-  if (paint_range_.IsNull())
+  if (!paint_range_)
     return;
 
-  LayoutObject* end = LayoutObjectAfterPosition(paint_range_.EndLayoutObject(),
-                                                paint_range_.EndOffset());
-  for (LayoutObject* o = paint_range_.StartLayoutObject(); o && o != end;
+  LayoutObject* end = LayoutObjectAfterPosition(paint_range_->EndLayoutObject(),
+                                                paint_range_->EndOffset());
+  for (LayoutObject* o = paint_range_->StartLayoutObject(); o && o != end;
        o = o->NextInPreOrder()) {
-    if (!o->CanBeSelectionLeaf() && o != paint_range_.StartLayoutObject() &&
-        o != paint_range_.EndLayoutObject())
+    if (!o->CanBeSelectionLeaf() && o != paint_range_->StartLayoutObject() &&
+        o != paint_range_->EndLayoutObject())
       continue;
     if (o->GetSelectionState() == SelectionState::kNone)
       continue;
 
     o->SetShouldInvalidateSelection();
   }
 }
 
 DEFINE_TRACE(LayoutSelection) {
   visitor->Trace(frame_selection_);
+  visitor->Trace(paint_range_);
+}
+
+NGTextOffsetMap::Builder::Builder() : offset_map_(new NGTextOffsetMap) {}

[kojii, 2017/06/16 11:25:56]

so this part will be removed and not for review, correct?

+
+void NGTextOffsetMap::Builder::Add(Node* node,
+                                   int dom_offset,
+                                   int layout_offset) {
+  DCHECK(node);
+  offset_map_->node_to_offset_map_.Set(std::make_pair(node, dom_offset),
+                                       layout_offset);
+}
+
+NGTextOffsetMap NGTextOffsetMap::Builder::Build() {
+  return std::move(*offset_map_);
+}
+
+Optional<int> NGTextOffsetMap::Get(Node* node, int dom_offset) const {
+  if (!node)
+    return Optional<int>();
+  auto iterator = node_to_offset_map_.find(std::make_pair(node, dom_offset));
+  if (iterator == node_to_offset_map_.end())
+    return Optional<int>();
+  return iterator->value;
+}
+
+NGTextOffsetMap NGTextOffsetMap::Create(
+    const LayoutNGBlockFlow& ng_block_flow) {
+  NGTextOffsetMap::Builder builder;
+  Vector<NGInlineItem> pseudo_items;
+  Vector<int> offset_mapping;
+  offset_mapping.push_back(0);
+  NGInlineItemsBuilder items_builder(&pseudo_items, &offset_mapping);
+
+  LayoutObject* last_object = nullptr;
+  for (const auto& item : ng_block_flow.GetNGInlineNodeData().items_) {
+    LayoutObject* layout_object = item.GetLayoutObject();
+    if (!layout_object || !layout_object->IsText() ||
+        layout_object == last_object)
+      continue;
+
+    Text* text = ToText(layout_object->GetNode());
+    size_t begin = offset_mapping.size();
+    items_builder.Append(text->textContent(), layout_object->Style(),
+                         layout_object);
+    size_t end = offset_mapping.size();
+    for (size_t i = 0; i < end - begin + 1; i++) {
+      int ng_offset = offset_mapping[begin + i - 1];
+      builder.Add(text, i, ng_offset);
+    }
+
+    last_object = layout_object;
+  }
+  return builder.Build();
 }
 
 }  // namespace blink