LayoutTreeBuilder.cpp [plain text]
#include "config.h"
#include "LayoutTreeBuilder.h"
#if ENABLE(LAYOUT_FORMATTING_CONTEXT)
#include "CachedImage.h"
#include "HTMLNames.h"
#include "HTMLTableCellElement.h"
#include "HTMLTableColElement.h"
#include "HTMLTableElement.h"
#include "InlineFormattingState.h"
#include "InvalidationContext.h"
#include "InvalidationState.h"
#include "LayoutBox.h"
#include "LayoutBoxGeometry.h"
#include "LayoutChildIterator.h"
#include "LayoutContainerBox.h"
#include "LayoutContext.h"
#include "LayoutInitialContainingBlock.h"
#include "LayoutInlineTextBox.h"
#include "LayoutLineBreakBox.h"
#include "LayoutPhase.h"
#include "LayoutReplacedBox.h"
#include "LayoutSize.h"
#include "LayoutState.h"
#include "RenderBlock.h"
#include "RenderBox.h"
#include "RenderChildIterator.h"
#include "RenderElement.h"
#include "RenderImage.h"
#include "RenderInline.h"
#include "RenderLineBreak.h"
#include "RenderStyle.h"
#include "RenderTable.h"
#include "RenderTableCaption.h"
#include "RenderTableCell.h"
#include "RenderView.h"
#include <wtf/IsoMallocInlines.h>
#include <wtf/text/TextStream.h>
namespace WebCore {
namespace Layout {
WTF_MAKE_ISO_ALLOCATED_IMPL(LayoutTree);
LayoutTree::LayoutTree()
{
}
static void appendChild(ContainerBox& parent, Box& newChild)
{
if (!parent.hasChild()) {
parent.setFirstChild(newChild);
parent.setLastChild(newChild);
newChild.setParent(parent);
return;
}
auto& lastChild = const_cast<Box&>(*parent.lastChild());
lastChild.setNextSibling(newChild);
newChild.setPreviousSibling(lastChild);
newChild.setParent(parent);
parent.setLastChild(newChild);
}
static Optional<LayoutSize> accumulatedOffsetForInFlowPositionedContinuation(const RenderBox& block)
{
if (!block.isAnonymous() || !block.isInFlowPositioned() || !block.isContinuation())
return { };
return block.relativePositionOffset();
}
static bool canUseSimplifiedTextMeasuring(const StringView& content, const FontCascade& font, bool whitespaceIsCollapsed)
{
if (font.codePath(TextRun(content)) == FontCascade::CodePath::Complex)
return false;
if (font.wordSpacing() || font.letterSpacing())
return false;
for (unsigned i = 0; i < content.length(); ++i) {
if ((!whitespaceIsCollapsed && content[i] == '\t') || content[i] == noBreakSpace || content[i] == softHyphen || content[i] >= HiraganaLetterSmallA)
return false;
}
return true;
}
std::unique_ptr<Layout::LayoutTree> TreeBuilder::buildLayoutTree(const RenderView& renderView)
{
PhaseScope scope(Phase::Type::TreeBuilding);
auto rootStyle = RenderStyle::clone(renderView.style());
rootStyle.setLogicalWidth(Length(renderView.width(), Fixed));
rootStyle.setLogicalHeight(Length(renderView.height(), Fixed));
auto rootLayoutBox = makeUnique<InitialContainingBlock>(WTFMove(rootStyle));
auto& rootContainer = *rootLayoutBox;
auto layoutTree = makeUnique<LayoutTree>();
layoutTree->append(WTFMove(rootLayoutBox));
TreeBuilder(*layoutTree).buildSubTree(renderView, rootContainer);
return layoutTree;
}
TreeBuilder::TreeBuilder(LayoutTree& layoutTree)
: m_layoutTree(layoutTree)
{
}
Box& TreeBuilder::createReplacedBox(Optional<Box::ElementAttributes> elementAttributes, RenderStyle&& style)
{
auto newBox = makeUnique<ReplacedBox>(elementAttributes, WTFMove(style));
auto& box = *newBox;
m_layoutTree.append(WTFMove(newBox));
return box;
}
Box& TreeBuilder::createTextBox(String text, bool canUseSimplifiedTextMeasuring, RenderStyle&& style)
{
auto newBox = makeUnique<InlineTextBox>(text, canUseSimplifiedTextMeasuring, WTFMove(style));
auto& box = *newBox;
m_layoutTree.append(WTFMove(newBox));
return box;
}
Box& TreeBuilder::createLineBreakBox(bool isOptional, RenderStyle&& style)
{
auto newBox = makeUnique<Layout::LineBreakBox>(isOptional, WTFMove(style));
auto& box = *newBox;
m_layoutTree.append(WTFMove(newBox));
return box;
}
ContainerBox& TreeBuilder::createContainer(Optional<Box::ElementAttributes> elementAttributes, RenderStyle&& style)
{
auto newContainer = makeUnique<ContainerBox>(elementAttributes, WTFMove(style));
auto& container = *newContainer;
m_layoutTree.append(WTFMove(newContainer));
return container;
}
Box* TreeBuilder::createLayoutBox(const ContainerBox& parentContainer, const RenderObject& childRenderer)
{
auto elementAttributes = [] (const RenderElement& renderer) -> Optional<Box::ElementAttributes> {
if (renderer.isDocumentElementRenderer())
return Box::ElementAttributes { Box::ElementType::Document };
if (auto* element = renderer.element()) {
if (element->hasTagName(HTMLNames::bodyTag))
return Box::ElementAttributes { Box::ElementType::Body };
if (element->hasTagName(HTMLNames::imgTag))
return Box::ElementAttributes { Box::ElementType::Image };
if (element->hasTagName(HTMLNames::iframeTag))
return Box::ElementAttributes { Box::ElementType::IFrame };
return Box::ElementAttributes { Box::ElementType::GenericElement };
}
return WTF::nullopt;
};
Box* childLayoutBox = nullptr;
if (is<RenderText>(childRenderer)) {
auto& textRenderer = downcast<RenderText>(childRenderer);
String text = textRenderer.text();
auto useSimplifiedTextMeasuring = canUseSimplifiedTextMeasuring(text, parentContainer.style().fontCascade(), parentContainer.style().collapseWhiteSpace());
if (parentContainer.style().display() == DisplayType::Inline)
childLayoutBox = &createTextBox(text, useSimplifiedTextMeasuring, RenderStyle::clone(parentContainer.style()));
else
childLayoutBox = &createTextBox(text, useSimplifiedTextMeasuring, RenderStyle::createAnonymousStyleWithDisplay(parentContainer.style(), DisplayType::Inline));
} else {
auto& renderer = downcast<RenderElement>(childRenderer);
auto displayType = renderer.style().display();
auto clonedStyle = RenderStyle::clone(renderer.style());
if (is<RenderLineBreak>(renderer)) {
clonedStyle.setDisplay(DisplayType::Inline);
clonedStyle.setFloating(Float::No);
clonedStyle.setPosition(PositionType::Static);
childLayoutBox = &createLineBreakBox(downcast<RenderLineBreak>(childRenderer).isWBR(), WTFMove(clonedStyle));
} else if (is<RenderTable>(renderer)) {
auto tableWrapperBoxStyle = RenderStyle::createAnonymousStyleWithDisplay(parentContainer.style(), renderer.style().display() == DisplayType::Table ? DisplayType::Block : DisplayType::Inline);
tableWrapperBoxStyle.setPosition(renderer.style().position());
tableWrapperBoxStyle.setFloating(renderer.style().floating());
tableWrapperBoxStyle.setTop(Length { renderer.style().top() });
tableWrapperBoxStyle.setLeft(Length { renderer.style().left() });
tableWrapperBoxStyle.setBottom(Length { renderer.style().bottom() });
tableWrapperBoxStyle.setRight(Length { renderer.style().right() });
tableWrapperBoxStyle.setMarginTop(Length { renderer.style().marginTop() });
tableWrapperBoxStyle.setMarginLeft(Length { renderer.style().marginLeft() });
tableWrapperBoxStyle.setMarginBottom(Length { renderer.style().marginBottom() });
tableWrapperBoxStyle.setMarginRight(Length { renderer.style().marginRight() });
childLayoutBox = &createContainer(Box::ElementAttributes { Box::ElementType::TableWrapperBox }, WTFMove(tableWrapperBoxStyle));
childLayoutBox->setIsAnonymous();
} else if (is<RenderReplaced>(renderer)) {
childLayoutBox = &createReplacedBox(elementAttributes(renderer), WTFMove(clonedStyle));
downcast<ReplacedBox>(*childLayoutBox).setIntrinsicSize(downcast<RenderReplaced>(renderer).intrinsicSize());
if (is<RenderImage>(renderer)) {
auto& imageRenderer = downcast<RenderImage>(renderer);
if (imageRenderer.shouldDisplayBrokenImageIcon())
downcast<ReplacedBox>(*childLayoutBox).setIntrinsicRatio(1);
if (imageRenderer.cachedImage())
downcast<ReplacedBox>(*childLayoutBox).setCachedImage(*imageRenderer.cachedImage());
}
} else {
if (displayType == DisplayType::Block) {
if (auto offset = accumulatedOffsetForInFlowPositionedContinuation(downcast<RenderBox>(renderer))) {
clonedStyle.setTop({ offset->height(), Fixed });
clonedStyle.setLeft({ offset->width(), Fixed });
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
} else
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
} else if (displayType == DisplayType::Flex)
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
else if (displayType == DisplayType::Inline)
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
else if (displayType == DisplayType::InlineBlock)
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
else if (displayType == DisplayType::TableCaption || displayType == DisplayType::TableCell) {
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
} else if (displayType == DisplayType::TableRowGroup || displayType == DisplayType::TableHeaderGroup || displayType == DisplayType::TableFooterGroup
|| displayType == DisplayType::TableRow || displayType == DisplayType::TableColumnGroup) {
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
} else if (displayType == DisplayType::TableColumn) {
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
auto& tableColElement = static_cast<HTMLTableColElement&>(*renderer.element());
auto columnWidth = tableColElement.width();
if (!columnWidth.isEmpty())
childLayoutBox->setColumnWidth(columnWidth.toInt());
if (tableColElement.span() > 1)
childLayoutBox->setColumnSpan(tableColElement.span());
} else {
ASSERT_NOT_IMPLEMENTED_YET();
clonedStyle.setDisplay(DisplayType::Block);
childLayoutBox = &createContainer(elementAttributes(renderer), WTFMove(clonedStyle));
}
}
if (is<RenderTableCell>(renderer)) {
auto* tableCellElement = renderer.element();
if (is<HTMLTableCellElement>(tableCellElement)) {
auto& cellElement = downcast<HTMLTableCellElement>(*tableCellElement);
auto rowSpan = cellElement.rowSpan();
if (rowSpan > 1)
childLayoutBox->setRowSpan(rowSpan);
auto columnSpan = cellElement.colSpan();
if (columnSpan > 1)
childLayoutBox->setColumnSpan(columnSpan);
}
}
if (childRenderer.isAnonymous())
childLayoutBox->setIsAnonymous();
}
return childLayoutBox;
}
void TreeBuilder::buildTableStructure(const RenderTable& tableRenderer, ContainerBox& tableWrapperBox)
{
auto* tableChild = tableRenderer.firstChild();
while (is<RenderTableCaption>(tableChild)) {
auto& captionRenderer = *tableChild;
auto* captionBox = createLayoutBox(tableWrapperBox, captionRenderer);
appendChild(tableWrapperBox, *captionBox);
auto& captionContainer = downcast<ContainerBox>(*captionBox);
buildSubTree(downcast<RenderElement>(captionRenderer), captionContainer);
tableChild = tableChild->nextSibling();
}
auto tableBoxStyle = RenderStyle::clone(tableRenderer.style());
tableBoxStyle.setPosition(PositionType::Static);
tableBoxStyle.setFloating(Float::No);
tableBoxStyle.resetMargin();
if (is<HTMLTableElement>(tableRenderer.element()))
tableBoxStyle.setBoxSizing(BoxSizing::BorderBox);
auto& tableBox = createContainer(Box::ElementAttributes { Box::ElementType::TableBox }, WTFMove(tableBoxStyle));
appendChild(tableWrapperBox, tableBox);
auto* sectionRenderer = tableChild;
while (sectionRenderer) {
auto* sectionBox = createLayoutBox(tableBox, *sectionRenderer);
appendChild(tableBox, *sectionBox);
auto& sectionContainer = downcast<ContainerBox>(*sectionBox);
buildSubTree(downcast<RenderElement>(*sectionRenderer), sectionContainer);
sectionRenderer = sectionRenderer->nextSibling();
}
auto addMissingTableCells = [&] (auto& tableBody) {
size_t maximumColumns = 0;
size_t currentRow = 0;
Vector<size_t> numberOfCellsPerRow;
for (auto& rowBox : childrenOfType<ContainerBox>(tableBody)) {
if (numberOfCellsPerRow.size() <= currentRow) {
numberOfCellsPerRow.append({ });
}
for (auto& cellBox : childrenOfType<ContainerBox>(rowBox)) {
auto numberOfSpannedColumns = cellBox.columnSpan();
for (size_t rowSpan = 0; rowSpan < cellBox.rowSpan(); ++rowSpan) {
auto rowIndexWithSpan = currentRow + rowSpan;
if (numberOfCellsPerRow.size() <= rowIndexWithSpan) {
numberOfCellsPerRow.append(numberOfSpannedColumns);
continue;
}
numberOfCellsPerRow[rowIndexWithSpan] += numberOfSpannedColumns;
}
}
maximumColumns = std::max(maximumColumns, numberOfCellsPerRow[currentRow]);
++currentRow;
}
size_t rowIndex = 0;
for (auto& rowBox : childrenOfType<ContainerBox>(tableBody)) {
ASSERT(maximumColumns >= numberOfCellsPerRow[rowIndex]);
auto numberOfMissingCells = maximumColumns - numberOfCellsPerRow[rowIndex++];
for (size_t i = 0; i < numberOfMissingCells; ++i)
appendChild(const_cast<ContainerBox&>(rowBox), createContainer({ }, RenderStyle::createAnonymousStyleWithDisplay(rowBox.style(), DisplayType::TableCell)));
}
};
for (auto& section : childrenOfType<ContainerBox>(tableBox)) {
if (!section.isTableBody())
continue;
addMissingTableCells(section);
}
}
void TreeBuilder::buildSubTree(const RenderElement& parentRenderer, ContainerBox& parentContainer)
{
for (auto& childRenderer : childrenOfType<RenderObject>(parentRenderer)) {
auto* childLayoutBox = createLayoutBox(parentContainer, childRenderer);
appendChild(parentContainer, *childLayoutBox);
if (childLayoutBox->isTableWrapperBox())
buildTableStructure(downcast<RenderTable>(childRenderer), downcast<ContainerBox>(*childLayoutBox));
else if (is<ContainerBox>(*childLayoutBox))
buildSubTree(downcast<RenderElement>(childRenderer), downcast<ContainerBox>(*childLayoutBox));
}
}
#if ENABLE(TREE_DEBUGGING)
void showInlineTreeAndRuns(TextStream& stream, const LayoutState& layoutState, const ContainerBox& inlineFormattingRoot, size_t depth)
{
auto& inlineFormattingState = layoutState.establishedInlineFormattingState(inlineFormattingRoot);
auto& lines = inlineFormattingState.lines();
auto& lineBoxes = inlineFormattingState.lineBoxes();
for (size_t lineIndex = 0; lineIndex < lines.size(); ++lineIndex) {
auto addSpacing = [&] {
size_t printedCharacters = 0;
stream << "-------- --";
while (++printedCharacters <= depth * 2)
stream << " ";
};
addSpacing();
auto& line = lines[lineIndex];
auto& lineBoxLogicalRect = line.lineBoxLogicalRect();
stream << "line at (" << lineBoxLogicalRect.left() << "," << lineBoxLogicalRect.top() << ") size (" << lineBoxLogicalRect.width() << "x" << lineBoxLogicalRect.height() << ") baseline (" << line.baseline() << ")";
stream.nextLine();
addSpacing();
stream << " Inline level boxes:";
stream.nextLine();
auto& lineBox = lineBoxes[lineIndex];
auto outputInlineLevelBox = [&](const auto& inlineLevelBox) {
addSpacing();
stream << " ";
if (inlineLevelBox.isRootInlineBox())
stream << "Root inline box";
else if (inlineLevelBox.isAtomicInlineLevelBox())
stream << "Atomic inline level box";
else if (inlineLevelBox.isLineBreakBox())
stream << "Line break box";
else if (inlineLevelBox.isInlineBox())
stream << "Generic inline box";
else
stream << "Generic inline level box";
auto& layoutBox = inlineLevelBox.layoutBox();
auto logicalRect = lineBox.logicalMarginRectForInlineLevelBox(layoutBox, layoutState.geometryForBox(layoutBox));
stream
<< " at (" << logicalRect.left() << "," << logicalRect.top() << ")"
<< " size (" << logicalRect.width() << "x" << logicalRect.height() << ")"
<< " baseline (" << logicalRect.top() + inlineLevelBox.baseline() << ")"
<< " ascent (" << inlineLevelBox.baseline() << "/" << inlineLevelBox.layoutBounds().ascent << ")"
<< " descent (" << inlineLevelBox.descent().valueOr(0.0f) << "/" << inlineLevelBox.layoutBounds().descent << ")";
stream.nextLine();
};
outputInlineLevelBox(lineBox.rootInlineBox());
for (auto& inlineLevelBox : lineBox.nonRootInlineLevelBoxes())
outputInlineLevelBox(*inlineLevelBox);
addSpacing();
stream << " Runs:";
stream.nextLine();
for (auto& run : inlineFormattingState.lineRuns()) {
if (run.lineIndex() != lineIndex)
continue;
addSpacing();
stream << " ";
if (run.text())
stream << "text run";
else
stream << "box run";
stream << " at (" << run.logicalLeft() << "," << run.logicalTop() << ") size " << run.logicalWidth() << "x" << run.logicalHeight();
if (run.text())
stream << " run(" << run.text()->start() << ", " << run.text()->end() << ")";
stream.nextLine();
}
}
}
static void outputLayoutBox(TextStream& stream, const Box& layoutBox, const BoxGeometry* boxGeometry, unsigned depth)
{
unsigned printedCharacters = 0;
while (++printedCharacters <= depth * 2)
stream << " ";
if (layoutBox.isFloatingPositioned())
stream << "[float] ";
if (is<InitialContainingBlock>(layoutBox))
stream << "Initial containing block";
else if (layoutBox.isDocumentBox())
stream << "HTML";
else if (layoutBox.isBodyBox())
stream << "BODY";
else if (layoutBox.isTableWrapperBox())
stream << "TABLE wrapper box";
else if (layoutBox.isTableBox())
stream << "TABLE";
else if (layoutBox.isTableCaption())
stream << "CAPTION";
else if (layoutBox.isTableHeader())
stream << "THEAD";
else if (layoutBox.isTableBody())
stream << "TBODY";
else if (layoutBox.isTableFooter())
stream << "TFOOT";
else if (layoutBox.isTableColumnGroup())
stream << "COL GROUP";
else if (layoutBox.isTableColumn())
stream << "COL";
else if (layoutBox.isTableCell())
stream << "TD";
else if (layoutBox.isTableRow())
stream << "TR";
else if (layoutBox.isFlexBox())
stream << "Flex box";
else if (layoutBox.isFlexItem())
stream << "Flex item";
else if (layoutBox.isInlineLevelBox()) {
if (layoutBox.isAnonymous())
stream << "anonymous inline box";
else if (layoutBox.isInlineBlockBox())
stream << "inline-block box";
else if (layoutBox.isLineBreakBox())
stream << (downcast<LineBreakBox>(layoutBox).isOptional() ? "word break opportunity" : "line break");
else if (layoutBox.isAtomicInlineLevelBox())
stream << "atomic inline level box";
else if (layoutBox.isReplacedBox())
stream << "replaced inline box";
else if (layoutBox.isInlineBox())
stream << "inline box";
else
stream << "other inline level box";
} else if (layoutBox.isBlockLevelBox())
stream << "block box";
else
stream << "unknown box";
if (boxGeometry) {
auto borderBox = BoxGeometry::borderBoxRect(*boxGeometry);
stream << " at (" << borderBox.left() << "," << borderBox.top() << ") size " << borderBox.width() << "x" << borderBox.height();
}
stream << " (" << &layoutBox << ")";
if (is<InlineTextBox>(layoutBox)) {
auto textContent = downcast<InlineTextBox>(layoutBox).content();
stream << " length->(" << textContent.length() << ")";
textContent.replaceWithLiteral('\\', "\\\\");
textContent.replaceWithLiteral('\n', "\\n");
const size_t maxPrintedLength = 80;
if (textContent.length() > maxPrintedLength) {
auto substring = textContent.substring(0, maxPrintedLength);
stream << " \"" << substring.utf8().data() << "\"...";
} else
stream << " \"" << textContent.utf8().data() << "\"";
}
stream.nextLine();
}
static void outputLayoutTree(const LayoutState* layoutState, TextStream& stream, const ContainerBox& rootContainer, unsigned depth)
{
for (auto& child : childrenOfType<Box>(rootContainer)) {
if (layoutState) {
if (layoutState->hasBoxGeometry(child))
outputLayoutBox(stream, child, &layoutState->geometryForBox(child), depth);
else
outputLayoutBox(stream, child, nullptr, depth);
if (child.establishesInlineFormattingContext())
showInlineTreeAndRuns(stream, *layoutState, downcast<ContainerBox>(child), depth + 1);
} else
outputLayoutBox(stream, child, nullptr, depth);
if (is<ContainerBox>(child))
outputLayoutTree(layoutState, stream, downcast<ContainerBox>(child), depth + 1);
}
}
String layoutTreeAsText(const Box& layoutBox, const LayoutState* layoutState)
{
TextStream stream(TextStream::LineMode::MultipleLine, TextStream::Formatting::SVGStyleRect);
auto& initialContainingBlock = layoutBox.initialContainingBlock();
outputLayoutBox(stream, initialContainingBlock, layoutState ? &layoutState->geometryForBox(initialContainingBlock) : nullptr, 0);
outputLayoutTree(layoutState, stream, initialContainingBlock, 1);
return stream.release();
}
void showLayoutTree(const Box& layoutBox, const LayoutState* layoutState)
{
auto treeAsText = layoutTreeAsText(layoutBox, layoutState);
WTFLogAlways("%s", treeAsText.utf8().data());
}
void showLayoutTree(const Box& layoutBox)
{
showLayoutTree(layoutBox, nullptr);
}
void printLayoutTreeForLiveDocuments()
{
for (const auto* document : Document::allDocuments()) {
if (!document->renderView())
continue;
if (document->frame() && document->frame()->isMainFrame())
fprintf(stderr, "----------------------main frame--------------------------\n");
fprintf(stderr, "%s\n", document->url().string().utf8().data());
auto& renderView = *document->renderView();
auto layoutTree = TreeBuilder::buildLayoutTree(renderView);
auto layoutState = LayoutState { *document, layoutTree->root() };
auto& layoutRoot = layoutState.root();
auto invalidationState = InvalidationState { };
LayoutContext(layoutState).layout(renderView.size(), invalidationState);
showLayoutTree(layoutRoot, &layoutState);
}
}
#endif
}
}
#endif