blob: f5ee6c8d00d4c1fc9ef756191b0628e78c8236fe [file] [log] [blame]
/*
* Copyright (C) 1999 Lars Knoll (knoll@kde.org)
* (C) 1999 Antti Koivisto (koivisto@kde.org)
* Copyright (C) 2003, 2004, 2005, 2006, 2007, 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.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
*/
// 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/html/list_item_ordinal.h"
#include "third_party/blink/renderer/core/dom/layout_tree_builder_traversal.h"
#include "third_party/blink/renderer/core/html/html_olist_element.h"
#include "third_party/blink/renderer/core/layout/layout_list_item.h"
#include "third_party/blink/renderer/core/layout/ng/list/layout_ng_list_item.h"
namespace blink {
ListItemOrdinal::ListItemOrdinal()
: type_(kNeedsUpdate), not_in_list_(false), not_in_list_changed_(false) {}
bool ListItemOrdinal::IsList(const Node& node) {
return IsHTMLUListElement(node) || IsHTMLOListElement(node);
}
bool ListItemOrdinal::IsListItem(const LayoutObject* layout_object) {
return layout_object &&
(layout_object->IsListItem() || layout_object->IsLayoutNGListItem());
}
bool ListItemOrdinal::IsListItem(const Node& node) {
return IsListItem(node.GetLayoutObject());
}
ListItemOrdinal* ListItemOrdinal::Get(const Node& item_node) {
LayoutObject* layout_object = item_node.GetLayoutObject();
if (layout_object) {
if (layout_object->IsListItem())
return &ToLayoutListItem(layout_object)->Ordinal();
if (layout_object->IsLayoutNGListItem())
return &ToLayoutNGListItem(layout_object)->Ordinal();
}
return nullptr;
}
// Returns the enclosing list with respect to the DOM order.
Node* ListItemOrdinal::EnclosingList(const Node* list_item_node) {
if (!list_item_node)
return nullptr;
Node* first_node = nullptr;
// We use parentNode because the enclosing list could be a ShadowRoot that's
// not Element.
for (Node* parent = FlatTreeTraversal::Parent(*list_item_node); parent;
parent = FlatTreeTraversal::Parent(*parent)) {
if (IsList(*parent))
return parent;
if (!first_node)
first_node = parent;
}
// If there's no actual <ul> or <ol> list element, then the first found
// node acts as our list for purposes of determining what other list items
// should be numbered as part of the same list.
return first_node;
}
// Returns the next list item with respect to the DOM order.
ListItemOrdinal::NodeAndOrdinal ListItemOrdinal::NextListItem(
const Node* list_node,
const Node* item) {
if (!list_node)
return {};
const Node* current = item ? item : list_node;
DCHECK(current);
DCHECK(!current->GetDocument().ChildNeedsDistributionRecalc());
current = LayoutTreeBuilderTraversal::Next(*current, list_node);
while (current) {
if (IsList(*current)) {
// We've found a nested, independent list: nothing to do here.
current =
LayoutTreeBuilderTraversal::NextSkippingChildren(*current, list_node);
continue;
}
if (ListItemOrdinal* ordinal = Get(*current))
return {current, ordinal};
// FIXME: Can this be optimized to skip the children of the elements without
// a layoutObject?
current = LayoutTreeBuilderTraversal::Next(*current, list_node);
}
return {};
}
// Returns the previous list item with respect to the DOM order.
ListItemOrdinal::NodeAndOrdinal ListItemOrdinal::PreviousListItem(
const Node* list_node,
const Node* item) {
const Node* current = item;
DCHECK(current);
DCHECK(!current->GetDocument().ChildNeedsDistributionRecalc());
for (current = LayoutTreeBuilderTraversal::Previous(*current, list_node);
current && current != list_node;
current = LayoutTreeBuilderTraversal::Previous(*current, list_node)) {
ListItemOrdinal* ordinal = Get(*current);
if (!ordinal)
continue;
const Node* other_list = EnclosingList(current);
// This item is part of our current list, so it's what we're looking for.
if (list_node == other_list)
return {current, ordinal};
// We found ourself inside another list; lets skip the rest of it.
// Use nextIncludingPseudo() here because the other list itself may actually
// be a list item itself. We need to examine it, so we do this to counteract
// the previousIncludingPseudo() that will be done by the loop.
if (other_list)
current = LayoutTreeBuilderTraversal::Next(*other_list, list_node);
}
return {};
}
// Returns the item for the next ordinal value. It is usually the next list
// item, except when the <ol> element has the 'reversed' attribute.
ListItemOrdinal::NodeAndOrdinal ListItemOrdinal::NextOrdinalItem(
bool is_list_reversed,
const Node* list,
const Node* item) {
return is_list_reversed ? PreviousListItem(list, item)
: NextListItem(list, item);
}
base::Optional<int> ListItemOrdinal::ExplicitValue() const {
if (!HasExplicitValue())
return {};
return value_;
}
int ListItemOrdinal::CalcValue(const Node& item_node) const {
if (HasExplicitValue())
return value_;
Node* list = EnclosingList(&item_node);
HTMLOListElement* o_list_element = ToHTMLOListElementOrNull(list);
int value_step = 1;
if (o_list_element && o_list_element->IsReversed())
value_step = -1;
// FIXME: This recurses to a possible depth of the length of the list.
// That's not good -- we need to change this to an iterative algorithm.
if (NodeAndOrdinal previous = PreviousListItem(list, &item_node))
return ClampAdd(previous.ordinal->Value(*previous.node), value_step);
if (o_list_element)
return o_list_element->StartConsideringItemCount();
return 1;
}
int ListItemOrdinal::Value(const Node& item_node) const {
if (Type() != kNeedsUpdate)
return value_;
value_ = CalcValue(item_node);
SetType(kUpdated);
return value_;
}
// Invalidate one instance of |ListItemOrdinal|.
void ListItemOrdinal::InvalidateSelf(const Node& item_node, ValueType type) {
DCHECK_NE(type, kUpdated);
SetType(type);
LayoutObject* layout_object = item_node.GetLayoutObject();
if (layout_object->IsListItem())
ToLayoutListItem(layout_object)->OrdinalValueChanged();
else if (layout_object->IsLayoutNGListItem())
ToLayoutNGListItem(layout_object)->OrdinalValueChanged();
}
// Invalidate items after |item_node| in the DOM order.
void ListItemOrdinal::InvalidateAfter(const Node* list_node,
const Node* item_node) {
for (NodeAndOrdinal item = NextListItem(list_node, item_node); item;
item = NextListItem(list_node, item.node)) {
DCHECK(item.ordinal);
if (item.ordinal->Type() == kUpdated)
item.ordinal->InvalidateSelf(*item.node);
}
}
// Invalidate items after |item_node| in the ordinal order.
void ListItemOrdinal::InvalidateOrdinalsAfter(bool is_reversed,
const Node* list_node,
const Node* item_node) {
for (NodeAndOrdinal item = NextOrdinalItem(is_reversed, list_node, item_node);
item; item = NextOrdinalItem(is_reversed, list_node, item.node)) {
DCHECK(item.ordinal);
if (item.ordinal->Type() != kUpdated) {
// If an item has been marked for update before, we can safely
// assume that all the following ones have too.
// This gives us the opportunity to stop here and avoid
// marking the same nodes again.
return;
}
item.ordinal->InvalidateSelf(*item.node);
}
}
void ListItemOrdinal::SetExplicitValue(int value, const Node& item_node) {
if (HasExplicitValue() && value_ == value)
return;
value_ = value;
InvalidateSelf(item_node, kExplicit);
InvalidateAfter(EnclosingList(&item_node), &item_node);
}
void ListItemOrdinal::ClearExplicitValue(const Node& item_node) {
if (!HasExplicitValue())
return;
InvalidateSelf(item_node);
InvalidateAfter(EnclosingList(&item_node), &item_node);
}
void ListItemOrdinal::SetNotInList(bool not_in_list, const Node& item_node) {
if (not_in_list_ == not_in_list)
return;
not_in_list_ = not_in_list;
SetNotInListChanged(true);
LayoutObject* layout_object = item_node.GetLayoutObject();
if (layout_object->IsLayoutNGListItem())
layout_object->NotifyOfSubtreeChange();
}
void ListItemOrdinal::SetNotInListChanged(bool changed) {
not_in_list_changed_ = changed;
}
unsigned ListItemOrdinal::ItemCountForOrderedList(
const HTMLOListElement* list_node) {
DCHECK(list_node);
unsigned item_count = 0;
for (NodeAndOrdinal list_item = NextListItem(list_node); list_item;
list_item = NextListItem(list_node, list_item.node))
item_count++;
return item_count;
}
void ListItemOrdinal::InvalidateAllItemsForOrderedList(
const HTMLOListElement* list_node) {
DCHECK(list_node);
if (NodeAndOrdinal list_item = NextListItem(list_node)) {
list_item.ordinal->InvalidateSelf(*list_item.node);
InvalidateAfter(list_node, list_item.node);
}
}
// TODO(layout-dev): We should use layout tree traversal instead of flat tree
// traversal to invalidate ordinal number cache since lite items in unassigned
// slots don't have cached value. See http://crbug.com/844277 for details.
void ListItemOrdinal::ItemInsertedOrRemoved(
const LayoutObject* layout_list_item) {
// If distribution recalc is needed, updateListMarkerNumber will be re-invoked
// after distribution is calculated.
const Node* item_node = layout_list_item->GetNode();
if (item_node->GetDocument().IsSlotAssignmentOrLegacyDistributionDirty())
return;
if (item_node->GetDocument().IsFlatTreeTraversalForbidden())
return;
Node* list_node = EnclosingList(item_node);
CHECK(list_node);
bool is_list_reversed = false;
if (auto* o_list_element = ToHTMLOListElementOrNull(list_node)) {
o_list_element->ItemCountChanged();
is_list_reversed = o_list_element->IsReversed();
}
// FIXME: The n^2 protection below doesn't help if the elements were inserted
// after the the list had already been displayed.
// Avoid an O(n^2) walk over the children below when they're all known to be
// attaching.
if (list_node->NeedsAttach())
return;
InvalidateOrdinalsAfter(is_list_reversed, list_node, item_node);
}
} // namespace blink