path: root/chromium/third_party/blink/renderer/core/layout/ng/inline/ng_inline_fragment_traversal.cc

// 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 "third_party/blink/renderer/core/layout/ng/inline/ng_inline_fragment_traversal.h"

#include "third_party/blink/renderer/core/layout/layout_inline.h"
#include "third_party/blink/renderer/core/layout/layout_object.h"
#include "third_party/blink/renderer/core/layout/ng/ng_physical_box_fragment.h"

namespace blink {

namespace {

using Result = NGPhysicalFragmentWithOffset;

class NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  virtual Vector<Result> CollectFrom(const NGPhysicalFragment&) = 0;

 protected:
  explicit NGPhysicalFragmentCollectorBase() = default;

  virtual void Visit() = 0;

  const NGPhysicalFragment& GetFragment() const { return *current_fragment_; }
  void SetShouldStopTraversing() { should_stop_traversing_ = true; }
  bool HasStoppedTraversing() const { return should_stop_traversing_; }

  void Emit() {
    results_.push_back(Result{current_fragment_, current_offset_to_root_});
  }

  // Visits and collets fragments in the subtree rooted at |fragment|.
  // |fragment| itself is not visited.
  Vector<Result> CollectExclusivelyFrom(const NGPhysicalFragment& fragment) {
    current_fragment_ = &fragment;
    root_fragment_ = &fragment;
    VisitChildren();
    return std::move(results_);
  }

  // Visits and collets fragments in the subtree rooted at |fragment|.
  // |fragment| itself is visited.
  Vector<Result> CollectInclusivelyFrom(const NGPhysicalFragment& fragment) {
    current_fragment_ = &fragment;
    root_fragment_ = &fragment;
    Visit();
    return std::move(results_);
  }

  void VisitChildren() {
    if (should_stop_traversing_)
      return;

    const NGPhysicalFragment& fragment = *current_fragment_;
    if (!fragment.IsContainer())
      return;

    // Traverse descendants unless the fragment is laid out separately from the
    // inline layout algorithm.
    if (&fragment != root_fragment_ && fragment.IsBlockLayoutRoot())
      return;

    DCHECK(fragment.IsContainer());
    DCHECK(fragment.IsInline() || fragment.IsLineBox() ||
           (fragment.IsBlockFlow() &&
            ToNGPhysicalBoxFragment(fragment).ChildrenInline()));

    for (const auto& child :
         ToNGPhysicalContainerFragment(fragment).Children()) {
      base::AutoReset<NGPhysicalOffset> offset_resetter(
          &current_offset_to_root_, current_offset_to_root_ + child->Offset());
      base::AutoReset<const NGPhysicalFragment*> fragment_resetter(
          &current_fragment_, child.get());
      Visit();

      if (should_stop_traversing_)
        return;
    }
  }

 private:
  const NGPhysicalFragment* root_fragment_ = nullptr;
  const NGPhysicalFragment* current_fragment_ = nullptr;
  NGPhysicalOffset current_offset_to_root_;
  Vector<Result> results_;
  bool should_stop_traversing_ = false;

  DISALLOW_COPY_AND_ASSIGN(NGPhysicalFragmentCollectorBase);
};

// The visitor emitting all visited fragments.
class DescendantCollector final : public NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  DescendantCollector() = default;

  Vector<Result> CollectFrom(const NGPhysicalFragment& fragment) final {
    return CollectExclusivelyFrom(fragment);
  }

 private:
  void Visit() final {
    Emit();
    VisitChildren();
  }

  DISALLOW_COPY_AND_ASSIGN(DescendantCollector);
};

// The visitor emitting all visited fragments.
class InclusiveDescendantCollector final
    : public NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  InclusiveDescendantCollector() = default;

  Vector<Result> CollectFrom(const NGPhysicalFragment& fragment) final {
    return CollectInclusivelyFrom(fragment);
  }

 private:
  void Visit() final {
    Emit();
    VisitChildren();
  }

  DISALLOW_COPY_AND_ASSIGN(InclusiveDescendantCollector);
};

// The visitor emitting fragments generated from the given LayoutInline,
// supporting culled inline.
// Note: Since we apply culled inline per line, we have a fragment for
// LayoutInline in second line but not in first line in
// "t0803-c5502-imrgn-r-01-b-ag.html".
class LayoutInlineCollector final : public NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  explicit LayoutInlineCollector(const LayoutInline& container) {
    CollectInclusiveDescendants(container);
  }

  Vector<Result> CollectFrom(const NGPhysicalFragment& fragment) final {
    return CollectExclusivelyFrom(fragment);
  }

 private:
  void Visit() final {
    if (!GetFragment().IsLineBox() &&
        inclusive_descendants_.Contains(GetFragment().GetLayoutObject())) {
      Emit();
      return;
    }
    VisitChildren();
  }

  void CollectInclusiveDescendants(const LayoutInline& container) {
    inclusive_descendants_.insert(&container);
    for (const LayoutObject* node = container.FirstChild(); node;
         node = node->NextSibling()) {
      if (node->IsFloatingOrOutOfFlowPositioned())
        continue;
      if (node->IsBox() || node->IsText()) {
        inclusive_descendants_.insert(node);
        continue;
      }
      if (!node->IsLayoutInline())
        continue;
      CollectInclusiveDescendants(ToLayoutInline(*node));
    }
  }

  HashSet<const LayoutObject*> inclusive_descendants_;

  DISALLOW_COPY_AND_ASSIGN(LayoutInlineCollector);
};

// The visitor emitting all fragments generated from the given LayoutObject.
class LayoutObjectCollector final : public NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  explicit LayoutObjectCollector(const LayoutObject* layout_object)
      : target_(layout_object) {}

  Vector<Result> CollectFrom(const NGPhysicalFragment& fragment) final {
    return CollectExclusivelyFrom(fragment);
  }

 private:
  void Visit() final {
    if (GetFragment().GetLayoutObject() == target_)
      Emit();
    VisitChildren();
  }

  const LayoutObject* target_;

  DISALLOW_COPY_AND_ASSIGN(LayoutObjectCollector);
};

// The visitor emitting ancestors of the given fragment in bottom-up order.
class AncestorCollector : public NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  explicit AncestorCollector(const NGPhysicalFragment& target)
      : target_(target) {}

  Vector<Result> CollectFrom(const NGPhysicalFragment& fragment) final {
    // TODO(xiaochengh): Change this into CollectInclusivlyFrom() to include
    // subtree root to align with NodeTraversal::AncestorsOf().
    return CollectExclusivelyFrom(fragment);
  }

 private:
  void Visit() final {
    if (&GetFragment() == &target_) {
      SetShouldStopTraversing();
      return;
    }

    VisitChildren();
    if (HasStoppedTraversing())
      Emit();
  }

  const NGPhysicalFragment& target_;
};

// The visitor emitting inclusive ancestors of the given fragment in bottom-up
// order.
class InclusiveAncestorCollector : public NGPhysicalFragmentCollectorBase {
  STACK_ALLOCATED();

 public:
  explicit InclusiveAncestorCollector(const NGPhysicalFragment& target)
      : target_(target) {}

  Vector<Result> CollectFrom(const NGPhysicalFragment& fragment) final {
    // TODO(xiaochengh): Change this into CollectInclusivlyFrom() to include
    // subtree root to align with NodeTraversal::InclusiveAncestorsOf().
    return CollectExclusivelyFrom(fragment);
  }

 private:
  void Visit() final {
    if (&GetFragment() == &target_) {
      SetShouldStopTraversing();
      Emit();
      return;
    }

    VisitChildren();
    if (HasStoppedTraversing())
      Emit();
  }

  const NGPhysicalFragment& target_;
};

}  // namespace

// static
Vector<Result> NGInlineFragmentTraversal::SelfFragmentsOf(
    const NGPhysicalContainerFragment& container,
    const LayoutObject* layout_object) {
  if (layout_object->IsLayoutInline()) {
    return LayoutInlineCollector(ToLayoutInline(*layout_object))
        .CollectFrom(container);
  }
  return LayoutObjectCollector(layout_object).CollectFrom(container);
}

// static
Vector<Result> NGInlineFragmentTraversal::DescendantsOf(
    const NGPhysicalContainerFragment& container) {
  return DescendantCollector().CollectFrom(container);
}

// static
Vector<Result> NGInlineFragmentTraversal::InclusiveDescendantsOf(
    const NGPhysicalFragment& root) {
  return InclusiveDescendantCollector().CollectFrom(root);
}

// static
Vector<Result> NGInlineFragmentTraversal::InclusiveAncestorsOf(
    const NGPhysicalContainerFragment& container,
    const NGPhysicalFragment& target) {
  return InclusiveAncestorCollector(target).CollectFrom(container);
}

// static
Vector<Result> NGInlineFragmentTraversal::AncestorsOf(
    const NGPhysicalContainerFragment& container,
    const NGPhysicalFragment& target) {
  return AncestorCollector(target).CollectFrom(container);
}

}  // namespace blink