Implement collection of out-of-flow descendants

third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h

Index: third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h
diff --git a/third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h b/third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h
index 5b1a1f14a45407523f45b47e291a92e618ff25d8..a4b1dda9c5cff885d296a142f6283d577dca88b1 100644
--- a/third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h
+++ b/third_party/WebKit/Source/core/layout/ng/ng_fragment_builder.h
@@ -28,8 +28,46 @@ class CORE_EXPORT NGFragmentBuilder final
 
   NGFragmentBuilder& AddChild(NGFragmentBase*, NGLogicalOffset);
 
-  NGFragmentBuilder& SetOutOfFlowDescendants(WeakBoxList&,
-                                             Vector<NGLogicalOffset>&);
+  // Builder has non-trivial out-of-flow descendant methods.
+  // These methods are building blocks for implementation of
+  // out-of-flow descendants by layout algorithms.
+  //
+  // They are intended to be used by layout algorithm like this:
+  //
+  // Part 1: layout algorithm positions in-flow children.
+  //   out-of-flow children, and out-of-flow descendants of fragments
+  //   are stored inside builder.
+  //
+  // for (child : children)
+  //   if (child->position == (Absolute or Fixed))
+  //     builder->AddOutOfFlowChildCandidate(child);
+  //   else
+  //     fragment = child->Layout()
+  //     builder->AddChild(fragment)
+  // end
+  //
+  // Part 2: layout algorithm positions out-of-flow descendants.
+  //
+  // builder->SetInlineSize/SetBlockSize
+  // builder->GetOutOfFlowDescendantCandidates(oof_candidates)
+  // while (oof_candidates.size() > 0)
+  // {
+  //   canditate = oof_candidates.shift()

[cbiesinger, 2016/12/02 22:37:03]

typo: candidate

[atotic, 2016/12/02 23:08:44]

done

+  //   if (CanPosition(candidate))
+  //     fragment = candidate->Layout();
+  //     builder->AddChild(fragment);
+  //     builder->GetOutOfFlowDescendantCandidates(child_oof_candidates)
+  //     oof_candidates.prepend(child_oof_candidates)
+  //   else
+  //     builder->AddOutOfFlowDescendant();
+  // }
+  NGFragmentBuilder& AddOutOfFlowChildCandidate(NGBlockNode*, NGLogicalOffset);
+
+  void GetOutOfFlowDescendantCandidates(WeakBoxList*,

[cbiesinger, 2016/12/02 22:37:03]

Maybe better to return a vector of pairs (or, a struct with the two values)?

I suppose the point is that you want a weak list for the boxes, but you could
just define your own typedef for that

as a side note, I just noticed that this is a hash set. I'm not sure that's a
good idea, doesn't it have to be ordered for correct painting order?

[atotic, 2016/12/02 23:08:44]

I also dislike objects being split between two collections, it makes traversal
awkward. Oilpan forces this separation right now, because WeakMembers cannot be
a member of a struct stored inside a collection. When boxes move away from
Oilpan, I'll redo all of these as proper structs.
Not a hash set, a HeapLinkedHashSet. This is the only ordered GC collection that
will accept WeakMembers.

+                                        Vector<NGStaticPosition>*);
+
+  NGFragmentBuilder& AddOutOfFlowDescendant(NGBlockNode*,
+                                            const NGStaticPosition&);
 
   // Sets MarginStrut for the resultant fragment.
   NGFragmentBuilder& SetMarginStrutBlockStart(const NGMarginStrut& from);
@@ -44,6 +82,24 @@ class CORE_EXPORT NGFragmentBuilder final
   DECLARE_VIRTUAL_TRACE();
 
  private:
+  // Out-of-flow descendant placement information.
+  // The generated fragment must compute NGStaticPosition for all
+  // out-of-flow descendants.
+  // The resulting NGStaticPosition gets derived from:
+  // 1. The offset of fragment's child.
+  // 2. The static position of descendant wrt child.
+  //
+  // A child can be:
+  // 1. A descendant itself. In this case, descendant position is (0,0).

[cbiesinger, 2016/12/02 22:37:03]

descendant -> direct child, I think?

[atotic, 2016/12/02 23:08:44]

It does. The comment repeats this information because it is a bit confusing.
Here we have two objects: child, and descendant, and sometimes child is also the
descendant, and sometimes descendant is a descendant of a child.

+  // 2. A fragment containing a descendant.
+  //
+  // child_offset is stored as NGLogicalOffset because physical offset cannot
+  // be computed until we know fragment's size.
+  struct OutOfFlowPlacement {
+    NGLogicalOffset child_offset;
+    NGStaticPosition descendant_position;
+  };
+
   NGPhysicalFragmentBase::NGFragmentType type_;
   NGWritingMode writing_mode_;
   TextDirection direction_;
@@ -55,8 +111,12 @@ class CORE_EXPORT NGFragmentBuilder final
 
   HeapVector<Member<NGPhysicalFragmentBase>> children_;
   Vector<NGLogicalOffset> offsets_;
+
+  WeakBoxList out_of_flow_descendant_candidates_;
+  Vector<OutOfFlowPlacement> out_of_flow_candidate_placements_;
+
   WeakBoxList out_of_flow_descendants_;
-  Vector<NGLogicalOffset> out_of_flow_offsets_;
+  Vector<NGStaticPosition> out_of_flow_positions_;
 };
 
 }  // namespace blink