| /* |
| * Copyright (C) 1999 Lars Knoll (knoll@kde.org) |
| * (C) 1999 Antti Koivisto (koivisto@kde.org) |
| * (C) 2007 David Smith (catfish.man@gmail.com) |
| * Copyright (C) 2003-2015, 2017 Apple Inc. All rights reserved. |
| * Copyright (C) Research In Motion Limited 2010. 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. |
| */ |
| |
| #include "config.h" |
| #include "RenderTreeBuilderMultiColumn.h" |
| |
| #include "RenderBlockFlow.h" |
| #include "RenderChildIterator.h" |
| #include "RenderMultiColumnFlow.h" |
| #include "RenderMultiColumnSet.h" |
| #include "RenderMultiColumnSpannerPlaceholder.h" |
| #include "RenderTextControl.h" |
| #include "RenderTreeBuilder.h" |
| #include "RenderTreeBuilderBlock.h" |
| #include "RenderView.h" |
| |
| namespace WebCore { |
| |
| static RenderMultiColumnSet* findSetRendering(const RenderMultiColumnFlow& fragmentedFlow, const RenderObject& renderer) |
| { |
| // Find the set inside which the specified renderer would be rendered. |
| for (auto* multicolSet = fragmentedFlow.firstMultiColumnSet(); multicolSet; multicolSet = multicolSet->nextSiblingMultiColumnSet()) { |
| if (multicolSet->containsRendererInFragmentedFlow(renderer)) |
| return multicolSet; |
| } |
| return nullptr; |
| } |
| |
| static RenderObject* spannerPlacehoderCandidate(const RenderObject& renderer, const RenderMultiColumnFlow& stayWithin) |
| { |
| // Spanner candidate is a next sibling/ancestor's next child within the flow thread and |
| // it is in the same inflow/out-of-flow layout context. |
| if (renderer.isOutOfFlowPositioned()) |
| return nullptr; |
| |
| ASSERT(renderer.isDescendantOf(&stayWithin)); |
| auto* current = &renderer; |
| while (true) { |
| // Skip to the first in-flow sibling. |
| auto* nextSibling = current->nextSibling(); |
| while (nextSibling && nextSibling->isOutOfFlowPositioned()) |
| nextSibling = nextSibling->nextSibling(); |
| if (nextSibling) |
| return nextSibling; |
| // No sibling candidate, jump to the parent and check its siblings. |
| current = current->parent(); |
| if (!current || current == &stayWithin || current->isOutOfFlowPositioned()) |
| return nullptr; |
| } |
| return nullptr; |
| } |
| |
| static bool isValidColumnSpanner(const RenderMultiColumnFlow& fragmentedFlow, const RenderObject& descendant) |
| { |
| // We assume that we're inside the flow thread. This function is not to be called otherwise. |
| ASSERT(descendant.isDescendantOf(&fragmentedFlow)); |
| // First make sure that the renderer itself has the right properties for becoming a spanner. |
| if (!is<RenderBox>(descendant)) |
| return false; |
| |
| auto& descendantBox = downcast<RenderBox>(descendant); |
| if (descendantBox.isFloatingOrOutOfFlowPositioned()) |
| return false; |
| |
| if (descendantBox.style().columnSpan() != ColumnSpan::All) |
| return false; |
| |
| auto* parent = descendantBox.parent(); |
| if (!is<RenderBlockFlow>(*parent) || parent->childrenInline()) { |
| // Needs to be block-level. |
| return false; |
| } |
| |
| // We need to have the flow thread as the containing block. A spanner cannot break out of the flow thread. |
| auto* enclosingFragmentedFlow = descendantBox.enclosingFragmentedFlow(); |
| if (enclosingFragmentedFlow != &fragmentedFlow) |
| return false; |
| |
| // This looks like a spanner, but if we're inside something unbreakable, it's not to be treated as one. |
| for (auto* ancestor = descendantBox.containingBlock(); ancestor; ancestor = ancestor->containingBlock()) { |
| if (is<RenderView>(*ancestor)) |
| return false; |
| if (ancestor->isLegend()) |
| return false; |
| if (is<RenderTextControl>(*ancestor)) |
| return false; |
| if (is<RenderFragmentedFlow>(*ancestor)) { |
| // Don't allow any intervening non-multicol fragmentation contexts. The spec doesn't say |
| // anything about disallowing this, but it's just going to be too complicated to |
| // implement (not to mention specify behavior). |
| return ancestor == &fragmentedFlow; |
| } |
| if (is<RenderBlockFlow>(*ancestor)) { |
| auto& blockFlowAncestor = downcast<RenderBlockFlow>(*ancestor); |
| if (blockFlowAncestor.willCreateColumns()) { |
| // This ancestor (descendent of the fragmentedFlow) will create columns later. The spanner belongs to it. |
| return false; |
| } |
| if (blockFlowAncestor.multiColumnFlow()) { |
| // While this ancestor (descendent of the fragmentedFlow) has a fragmented flow context, this context is being destroyed. |
| // However the spanner still belongs to it (will most likely be moved to the parent fragmented context as the next step). |
| return false; |
| } |
| } |
| ASSERT(ancestor->style().columnSpan() != ColumnSpan::All || !isValidColumnSpanner(fragmentedFlow, *ancestor)); |
| if (ancestor->isUnsplittableForPagination()) |
| return false; |
| } |
| ASSERT_NOT_REACHED(); |
| return false; |
| } |
| |
| RenderTreeBuilder::MultiColumn::MultiColumn(RenderTreeBuilder& builder) |
| : m_builder(builder) |
| { |
| } |
| |
| void RenderTreeBuilder::MultiColumn::updateAfterDescendants(RenderBlockFlow& flow) |
| { |
| bool needsFragmentedFlow = flow.requiresColumns(flow.style().columnCount()); |
| bool hasFragmentedFlow = flow.multiColumnFlow(); |
| |
| if (!hasFragmentedFlow && needsFragmentedFlow) { |
| createFragmentedFlow(flow); |
| return; |
| } |
| if (hasFragmentedFlow && !needsFragmentedFlow) { |
| destroyFragmentedFlow(flow); |
| return; |
| } |
| } |
| |
| void RenderTreeBuilder::MultiColumn::createFragmentedFlow(RenderBlockFlow& flow) |
| { |
| flow.setChildrenInline(false); // Do this to avoid wrapping inline children that are just going to move into the flow thread. |
| flow.deleteLines(); |
| // If this soon-to-be multicolumn flow is already part of a multicolumn context, we need to move back the descendant spanners |
| // to their original position before moving subtrees around. |
| if (auto* enclosingflow = flow.enclosingFragmentedFlow(); is<RenderMultiColumnFlow>(enclosingflow)) |
| restoreColumnSpannersForContainer(flow, downcast<RenderMultiColumnFlow>(*enclosingflow)); |
| |
| auto newFragmentedFlow = WebCore::createRenderer<RenderMultiColumnFlow>(flow.document(), RenderStyle::createAnonymousStyleWithDisplay(flow.style(), DisplayType::Block)); |
| newFragmentedFlow->initializeStyle(); |
| auto& fragmentedFlow = *newFragmentedFlow; |
| m_builder.blockBuilder().attach(flow, WTFMove(newFragmentedFlow), nullptr); |
| |
| // Reparent children preceding the fragmented flow into the fragmented flow. |
| m_builder.moveChildren(flow, fragmentedFlow, flow.firstChild(), &fragmentedFlow, RenderTreeBuilder::NormalizeAfterInsertion::Yes); |
| if (flow.isFieldset()) { |
| // Keep legends out of the flow thread. |
| for (auto& box : childrenOfType<RenderBox>(fragmentedFlow)) { |
| if (box.isLegend()) |
| m_builder.move(fragmentedFlow, flow, box, RenderTreeBuilder::NormalizeAfterInsertion::Yes); |
| } |
| } |
| |
| flow.setMultiColumnFlow(fragmentedFlow); |
| } |
| |
| void RenderTreeBuilder::MultiColumn::restoreColumnSpannersForContainer(const RenderElement& container, RenderMultiColumnFlow& multiColumnFlow) |
| { |
| auto& spanners = multiColumnFlow.spannerMap(); |
| Vector<RenderMultiColumnSpannerPlaceholder*> placeholdersToRestore; |
| for (auto& spannerAndPlaceholder : spanners) { |
| auto& placeholder = *spannerAndPlaceholder.value; |
| if (!placeholder.isDescendantOf(&container)) |
| continue; |
| placeholdersToRestore.append(&placeholder); |
| } |
| for (auto* placeholder : placeholdersToRestore) { |
| auto* spanner = placeholder->spanner(); |
| if (!spanner) { |
| ASSERT_NOT_REACHED(); |
| continue; |
| } |
| // Move the spanner back to its original position. |
| auto& spannerOriginalParent = *placeholder->parent(); |
| // Detaching the spanner takes care of removing the placeholder (and merges the RenderMultiColumnSets). |
| auto spannerToReInsert = m_builder.detach(*spanner->parent(), *spanner); |
| m_builder.attach(spannerOriginalParent, WTFMove(spannerToReInsert)); |
| } |
| } |
| |
| void RenderTreeBuilder::MultiColumn::destroyFragmentedFlow(RenderBlockFlow& flow) |
| { |
| auto& multiColumnFlow = *flow.multiColumnFlow(); |
| multiColumnFlow.deleteLines(); |
| |
| // Move spanners back to their original DOM position in the tree, and destroy the placeholders. |
| auto& spanners = multiColumnFlow.spannerMap(); |
| Vector<RenderMultiColumnSpannerPlaceholder*> placeholdersToDelete; |
| for (auto& spannerAndPlaceholder : spanners) |
| placeholdersToDelete.append(spannerAndPlaceholder.value.get()); |
| Vector<std::pair<RenderElement*, RenderPtr<RenderObject>>> parentAndSpannerList; |
| for (auto* placeholder : placeholdersToDelete) { |
| auto* spannerOriginalParent = placeholder->parent(); |
| if (spannerOriginalParent == &multiColumnFlow) |
| spannerOriginalParent = &flow; |
| // Detaching the spanner takes care of removing the placeholder (and merges the RenderMultiColumnSets). |
| auto* spanner = placeholder->spanner(); |
| parentAndSpannerList.append(std::make_pair(spannerOriginalParent, m_builder.detach(*spanner->parent(), *spanner, CanCollapseAnonymousBlock::No))); |
| } |
| while (auto* columnSet = multiColumnFlow.firstMultiColumnSet()) |
| m_builder.destroy(*columnSet); |
| |
| flow.clearMultiColumnFlow(); |
| auto hasInitialBlockChild = [&] { |
| if (!flow.isFieldset()) |
| return false; |
| // We don't move the legend under the multicolumn flow (see MultiColumn::createFragmentedFlow), so when the multicolumn context is destroyed |
| // the fieldset already has a legend block level box. |
| for (auto& box : childrenOfType<RenderBox>(flow)) { |
| if (box.isLegend()) |
| return true; |
| } |
| return false; |
| }(); |
| flow.setChildrenInline(!hasInitialBlockChild); |
| m_builder.moveAllChildren(multiColumnFlow, flow, RenderTreeBuilder::NormalizeAfterInsertion::Yes); |
| m_builder.destroy(multiColumnFlow); |
| for (auto& parentAndSpanner : parentAndSpannerList) |
| m_builder.attach(*parentAndSpanner.first, WTFMove(parentAndSpanner.second)); |
| } |
| |
| |
| RenderObject* RenderTreeBuilder::MultiColumn::resolveMovedChild(RenderFragmentedFlow& enclosingFragmentedFlow, RenderObject* beforeChild) |
| { |
| if (!beforeChild) |
| return nullptr; |
| |
| if (!is<RenderBox>(*beforeChild)) |
| return beforeChild; |
| |
| if (!is<RenderMultiColumnFlow>(enclosingFragmentedFlow)) |
| return beforeChild; |
| |
| // We only need to resolve for column spanners. |
| if (beforeChild->style().columnSpan() != ColumnSpan::All) |
| return beforeChild; |
| |
| // The renderer for the actual DOM node that establishes a spanner is moved from its original |
| // location in the render tree to becoming a sibling of the column sets. In other words, it's |
| // moved out from the flow thread (and becomes a sibling of it). When we for instance want to |
| // create and insert a renderer for the sibling node immediately preceding the spanner, we need |
| // to map that spanner renderer to the spanner's placeholder, which is where the new inserted |
| // renderer belongs. |
| if (auto* placeholder = downcast<RenderMultiColumnFlow>(enclosingFragmentedFlow).findColumnSpannerPlaceholder(downcast<RenderBox>(beforeChild))) |
| return placeholder; |
| |
| // This is an invalid spanner, or its placeholder hasn't been created yet. This happens when |
| // moving an entire subtree into the flow thread, when we are processing the insertion of this |
| // spanner's preceding sibling, and we obviously haven't got as far as processing this spanner |
| // yet. |
| return beforeChild; |
| } |
| |
| static bool gShiftingSpanner = false; |
| |
| void RenderTreeBuilder::MultiColumn::multiColumnDescendantInserted(RenderMultiColumnFlow& flow, RenderObject& newDescendant) |
| { |
| if (gShiftingSpanner || newDescendant.isRenderFragmentedFlow()) |
| return; |
| |
| auto* subtreeRoot = &newDescendant; |
| auto* descendant = subtreeRoot; |
| while (descendant) { |
| // Skip nested multicolumn flows. |
| if (is<RenderMultiColumnFlow>(*descendant)) { |
| descendant = descendant->nextSibling(); |
| continue; |
| } |
| if (is<RenderMultiColumnSpannerPlaceholder>(*descendant)) { |
| // A spanner's placeholder has been inserted. The actual spanner renderer is moved from |
| // where it would otherwise occur (if it weren't a spanner) to becoming a sibling of the |
| // column sets. |
| RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*descendant); |
| ASSERT(!flow.spannerMap().get(placeholder.spanner())); |
| flow.spannerMap().add(placeholder.spanner(), downcast<RenderMultiColumnSpannerPlaceholder>(descendant)); |
| ASSERT(!placeholder.firstChild()); // There should be no children here, but if there are, we ought to skip them. |
| } else |
| descendant = processPossibleSpannerDescendant(flow, subtreeRoot, *descendant); |
| if (descendant) |
| descendant = descendant->nextInPreOrder(subtreeRoot); |
| } |
| } |
| |
| RenderObject* RenderTreeBuilder::MultiColumn::processPossibleSpannerDescendant(RenderMultiColumnFlow& flow, RenderObject*& subtreeRoot, RenderObject& descendant) |
| { |
| RenderBlockFlow* multicolContainer = flow.multiColumnBlockFlow(); |
| RenderObject* nextRendererInFragmentedFlow = spannerPlacehoderCandidate(descendant, flow); |
| RenderObject* insertBeforeMulticolChild = nullptr; |
| RenderObject* nextDescendant = &descendant; |
| |
| if (!multicolContainer) |
| return nullptr; |
| |
| if (isValidColumnSpanner(flow, descendant)) { |
| // This is a spanner (column-span:all). Such renderers are moved from where they would |
| // otherwise occur in the render tree to becoming a direct child of the multicol container, |
| // so that they live among the column sets. This simplifies the layout implementation, and |
| // basically just relies on regular block layout done by the RenderBlockFlow that |
| // establishes the multicol container. |
| RenderBlockFlow* container = downcast<RenderBlockFlow>(descendant.parent()); |
| RenderMultiColumnSet* setToSplit = nullptr; |
| if (nextRendererInFragmentedFlow) { |
| setToSplit = findSetRendering(flow, descendant); |
| if (setToSplit) { |
| setToSplit->setNeedsLayout(); |
| insertBeforeMulticolChild = setToSplit->nextSibling(); |
| } |
| } |
| // Moving a spanner's renderer so that it becomes a sibling of the column sets requires us |
| // to insert an anonymous placeholder in the tree where the spanner's renderer otherwise |
| // would have been. This is needed for a two reasons: We need a way of separating inline |
| // content before and after the spanner, so that it becomes separate line boxes. Secondly, |
| // this placeholder serves as a break point for column sets, so that, when encountered, we |
| // end flowing one column set and move to the next one. |
| auto newPlaceholder = RenderMultiColumnSpannerPlaceholder::createAnonymous(flow, downcast<RenderBox>(descendant), container->style()); |
| auto& placeholder = *newPlaceholder; |
| m_builder.attach(*container, WTFMove(newPlaceholder), descendant.nextSibling()); |
| auto takenDescendant = m_builder.detach(*container, descendant); |
| |
| // This is a guard to stop an ancestor flow thread from processing the spanner. |
| gShiftingSpanner = true; |
| m_builder.blockBuilder().attach(*multicolContainer, WTFMove(takenDescendant), insertBeforeMulticolChild); |
| gShiftingSpanner = false; |
| |
| // The spanner has now been moved out from the flow thread, but we don't want to |
| // examine its children anyway. They are all part of the spanner and shouldn't trigger |
| // creation of column sets or anything like that. Continue at its original position in |
| // the tree, i.e. where the placeholder was just put. |
| if (subtreeRoot == &descendant) |
| subtreeRoot = &placeholder; |
| nextDescendant = &placeholder; |
| } else { |
| // This is regular multicol content, i.e. not part of a spanner. |
| if (is<RenderMultiColumnSpannerPlaceholder>(nextRendererInFragmentedFlow)) { |
| // Inserted right before a spanner. Is there a set for us there? |
| RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*nextRendererInFragmentedFlow); |
| if (RenderObject* previous = placeholder.spanner()->previousSibling()) { |
| if (is<RenderMultiColumnSet>(*previous)) |
| return nextDescendant; // There's already a set there. Nothing to do. |
| } |
| insertBeforeMulticolChild = placeholder.spanner(); |
| } else if (RenderMultiColumnSet* lastSet = flow.lastMultiColumnSet()) { |
| // This child is not an immediate predecessor of a spanner, which means that if this |
| // child precedes a spanner at all, there has to be a column set created for us there |
| // already. If it doesn't precede any spanner at all, on the other hand, we need a |
| // column set at the end of the multicol container. We don't really check here if the |
| // child inserted precedes any spanner or not (as that's an expensive operation). Just |
| // make sure we have a column set at the end. It's no big deal if it remains unused. |
| if (!lastSet->nextSibling()) |
| return nextDescendant; |
| } |
| } |
| // Need to create a new column set when there's no set already created. We also always insert |
| // another column set after a spanner. Even if it turns out that there are no renderers |
| // following the spanner, there may be bottom margins there, which take up space. |
| auto newSet = createRenderer<RenderMultiColumnSet>(flow, RenderStyle::createAnonymousStyleWithDisplay(multicolContainer->style(), DisplayType::Block)); |
| newSet->initializeStyle(); |
| auto& set = *newSet; |
| m_builder.blockBuilder().attach(*multicolContainer, WTFMove(newSet), insertBeforeMulticolChild); |
| flow.invalidateFragments(); |
| |
| // We cannot handle immediate column set siblings at the moment (and there's no need for |
| // it, either). There has to be at least one spanner separating them. |
| ASSERT_UNUSED(set, !RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(&set) |
| || !RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet()); |
| ASSERT(!RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(&set) |
| || !RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet()); |
| |
| return nextDescendant; |
| } |
| |
| void RenderTreeBuilder::MultiColumn::handleSpannerRemoval(RenderMultiColumnFlow& flow, RenderObject& spanner, RenderTreeBuilder::CanCollapseAnonymousBlock canCollapseAnonymousBlock) |
| { |
| // The placeholder may already have been removed, but if it hasn't, do so now. |
| if (auto placeholder = flow.spannerMap().take(&downcast<RenderBox>(spanner))) |
| m_builder.destroy(*placeholder, canCollapseAnonymousBlock); |
| |
| if (auto* next = spanner.nextSibling()) { |
| if (auto* previous = spanner.previousSibling()) { |
| if (previous->isRenderMultiColumnSet() && next->isRenderMultiColumnSet()) { |
| // Merge two sets that no longer will be separated by a spanner. |
| m_builder.destroy(*next); |
| previous->setNeedsLayout(); |
| } |
| } |
| } |
| } |
| |
| void RenderTreeBuilder::MultiColumn::multiColumnRelativeWillBeRemoved(RenderMultiColumnFlow& flow, RenderObject& relative, RenderTreeBuilder::CanCollapseAnonymousBlock canCollapseAnonymousBlock) |
| { |
| flow.invalidateFragments(); |
| if (is<RenderMultiColumnSpannerPlaceholder>(relative)) { |
| // Remove the map entry for this spanner, but leave the actual spanner renderer alone. Also |
| // keep the reference to the spanner, since the placeholder may be about to be re-inserted |
| // in the tree. |
| ASSERT(relative.isDescendantOf(&flow)); |
| flow.spannerMap().remove(downcast<RenderMultiColumnSpannerPlaceholder>(relative).spanner()); |
| return; |
| } |
| if (relative.style().columnSpan() == ColumnSpan::All) { |
| if (relative.parent() != flow.parent()) |
| return; // not a valid spanner. |
| |
| handleSpannerRemoval(flow, relative, canCollapseAnonymousBlock); |
| } |
| // Note that we might end up with empty column sets if all column content is removed. That's no |
| // big deal though (and locating them would be expensive), and they will be found and re-used if |
| // content is added again later. |
| } |
| |
| RenderObject* RenderTreeBuilder::MultiColumn::adjustBeforeChildForMultiColumnSpannerIfNeeded(RenderObject& beforeChild) |
| { |
| if (!is<RenderBox>(beforeChild)) |
| return &beforeChild; |
| |
| auto* nextSibling = beforeChild.nextSibling(); |
| if (!nextSibling) |
| return &beforeChild; |
| |
| if (!is<RenderMultiColumnSet>(*nextSibling)) |
| return &beforeChild; |
| |
| auto* multiColumnFlow = downcast<RenderMultiColumnSet>(*nextSibling).multiColumnFlow(); |
| if (!multiColumnFlow) |
| return &beforeChild; |
| |
| return multiColumnFlow->findColumnSpannerPlaceholder(downcast<RenderBox>(&beforeChild)); |
| } |
| |
| } |
