src/third_party/WebKit/Source/core/rendering/RenderMultiColumnFlowThread.cpp

   1 /*
   2  * Copyright (C) 2012 Apple Inc.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS IN..0TERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "core/rendering/RenderMultiColumnFlowThread.h"
  28
  29 #include "core/rendering/RenderMultiColumnSet.h"
  30 #include "core/rendering/RenderMultiColumnSpannerSet.h"
  31
  32 namespace blink {
  33
  34 RenderMultiColumnFlowThread::RenderMultiColumnFlowThread()
  35     : m_columnCount(1)
  36     , m_columnHeightAvailable(0)
  37     , m_inBalancingPass(false)
  38     , m_needsColumnHeightsRecalculation(false)
  39     , m_progressionIsInline(true)
  40 {
  41     setFlowThreadState(InsideInFlowThread);
  42 }
  43
  44 RenderMultiColumnFlowThread::~RenderMultiColumnFlowThread()
  45 {
  46 }
  47
  48 RenderMultiColumnFlowThread* RenderMultiColumnFlowThread::createAnonymous(Document& document, RenderStyle* parentStyle)
  49 {
  50     RenderMultiColumnFlowThread* renderer = new RenderMultiColumnFlowThread();
  51     renderer->setDocumentForAnonymous(&document);
  52     renderer->setStyle(RenderStyle::createAnonymousStyleWithDisplay(parentStyle, BLOCK));
  53     return renderer;
  54 }
  55
  56 RenderMultiColumnSet* RenderMultiColumnFlowThread::firstMultiColumnSet() const
  57 {
  58     for (RenderObject* sibling = nextSibling(); sibling; sibling = sibling->nextSibling()) {
  59         if (sibling->isRenderMultiColumnSet())
  60             return toRenderMultiColumnSet(sibling);
  61     }
  62     return 0;
  63 }
  64
  65 RenderMultiColumnSet* RenderMultiColumnFlowThread::lastMultiColumnSet() const
  66 {
  67     for (RenderObject* sibling = multiColumnBlockFlow()->lastChild(); sibling; sibling = sibling->previousSibling()) {
  68         if (sibling->isRenderMultiColumnSet())
  69             return toRenderMultiColumnSet(sibling);
  70     }
  71     return 0;
  72 }
  73
  74 RenderMultiColumnSpannerSet* RenderMultiColumnFlowThread::containingColumnSpannerSet(const RenderObject* descendant) const
  75 {
  76     ASSERT(descendant->isDescendantOf(this));
  77
  78     // Before we spend time on searching the ancestry, see if there's a quick way to determine
  79     // whether there might be any spanners at all.
  80     RenderMultiColumnSet* firstSet = firstMultiColumnSet();
  81     if (!firstSet || (firstSet == lastMultiColumnSet() && !firstSet->isRenderMultiColumnSpannerSet()))
  82         return 0;
  83
  84     // We have spanners. See if the renderer in question is one or inside of one then.
  85     for (const RenderObject* ancestor = descendant; ancestor && ancestor != this; ancestor = ancestor->parent()) {
  86         if (RenderMultiColumnSpannerSet* spanner = m_spannerMap.get(ancestor))
  87             return spanner;
  88     }
  89     return 0;
  90 }
  91
  92 void RenderMultiColumnFlowThread::populate()
  93 {
  94     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
  95     ASSERT(!nextSibling());
  96     // Reparent children preceding the flow thread into the flow thread. It's multicol content
  97     // now. At this point there's obviously nothing after the flow thread, but renderers (column
  98     // sets and spanners) will be inserted there as we insert elements into the flow thread.
  99     multicolContainer->moveChildrenTo(this, multicolContainer->firstChild(), this, true);
 100 }
 101
 102 void RenderMultiColumnFlowThread::evacuateAndDestroy()
 103 {
 104     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
 105
 106     // Remove all sets.
 107     while (RenderMultiColumnSet* columnSet = firstMultiColumnSet())
 108         columnSet->destroy();
 109
 110     ASSERT(!previousSibling());
 111     ASSERT(!nextSibling());
 112
 113     // Finally we can promote all flow thread's children. Before we move them to the flow thread's
 114     // container, we need to unregister the flow thread, so that they aren't just re-added again to
 115     // the flow thread that we're trying to empty.
 116     multicolContainer->resetMultiColumnFlowThread();
 117     moveAllChildrenTo(multicolContainer, true);
 118
 119     // FIXME: it's scary that neither destroy() nor the move*Children* methods take care of this,
 120     // and instead leave you with dangling root line box pointers. But since this is how it is done
 121     // in other parts of the code that deal with reparenting renderers, let's do the cleanup on our
 122     // own here as well.
 123     deleteLineBoxTree();
 124
 125     destroy();
 126 }
 127
 128 LayoutSize RenderMultiColumnFlowThread::columnOffset(const LayoutPoint& point) const
 129 {
 130     if (!hasValidRegionInfo())
 131         return LayoutSize(0, 0);
 132
 133     LayoutPoint flowThreadPoint = flipForWritingMode(point);
 134     LayoutUnit blockOffset = isHorizontalWritingMode() ? flowThreadPoint.y() : flowThreadPoint.x();
 135     RenderMultiColumnSet* columnSet = columnSetAtBlockOffset(blockOffset);
 136     if (!columnSet)
 137         return LayoutSize(0, 0);
 138     return columnSet->flowThreadTranslationAtOffset(blockOffset);
 139 }
 140
 141 bool RenderMultiColumnFlowThread::needsNewWidth() const
 142 {
 143     LayoutUnit newWidth;
 144     unsigned dummyColumnCount; // We only care if used column-width changes.
 145     calculateColumnCountAndWidth(newWidth, dummyColumnCount);
 146     return newWidth != logicalWidth();
 147 }
 148
 149 void RenderMultiColumnFlowThread::layoutColumns(bool relayoutChildren, SubtreeLayoutScope& layoutScope)
 150 {
 151     if (relayoutChildren)
 152         layoutScope.setChildNeedsLayout(this);
 153
 154     if (!needsLayout()) {
 155         // Just before the multicol container (our parent RenderBlockFlow) finishes laying out, it
 156         // will call recalculateColumnHeights() on us unconditionally, but we only want that method
 157         // to do any work if we actually laid out the flow thread. Otherwise, the balancing
 158         // machinery would kick in needlessly, and trigger additional layout passes. Furthermore, we
 159         // actually depend on a proper flowthread layout pass in order to do balancing, since it's
 160         // flowthread layout that sets up content runs.
 161         m_needsColumnHeightsRecalculation = false;
 162         return;
 163     }
 164
 165     for (RenderMultiColumnSet* columnSet = firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet()) {
 166         if (!m_inBalancingPass) {
 167             // This is the initial layout pass. We need to reset the column height, because contents
 168             // typically have changed.
 169             columnSet->resetColumnHeight();
 170         }
 171     }
 172
 173     invalidateRegions();
 174     m_needsColumnHeightsRecalculation = heightIsAuto();
 175     layout();
 176 }
 177
 178 bool RenderMultiColumnFlowThread::recalculateColumnHeights()
 179 {
 180     // All column sets that needed layout have now been laid out, so we can finally validate them.
 181     validateRegions();
 182
 183     if (!m_needsColumnHeightsRecalculation)
 184         return false;
 185
 186     // Column heights may change here because of balancing. We may have to do multiple layout
 187     // passes, depending on how the contents is fitted to the changed column heights. In most
 188     // cases, laying out again twice or even just once will suffice. Sometimes we need more
 189     // passes than that, though, but the number of retries should not exceed the number of
 190     // columns, unless we have a bug.
 191     bool needsRelayout = false;
 192     for (RenderMultiColumnSet* multicolSet = firstMultiColumnSet(); multicolSet; multicolSet = multicolSet->nextSiblingMultiColumnSet()) {
 193         needsRelayout |= multicolSet->recalculateColumnHeight(m_inBalancingPass ? RenderMultiColumnSet::StretchBySpaceShortage : RenderMultiColumnSet::GuessFromFlowThreadPortion);
 194         if (needsRelayout) {
 195             // Once a column set gets a new column height, that column set and all successive column
 196             // sets need to be laid out over again, since their logical top will be affected by
 197             // this, and therefore their column heights may change as well, at least if the multicol
 198             // height is constrained.
 199             multicolSet->setChildNeedsLayout(MarkOnlyThis);
 200         }
 201     }
 202
 203     if (needsRelayout)
 204         setChildNeedsLayout(MarkOnlyThis);
 205
 206     m_inBalancingPass = needsRelayout;
 207     return needsRelayout;
 208 }
 209
 210 void RenderMultiColumnFlowThread::calculateColumnCountAndWidth(LayoutUnit& width, unsigned& count) const
 211 {
 212     RenderBlock* columnBlock = multiColumnBlockFlow();
 213     const RenderStyle* columnStyle = columnBlock->style();
 214     LayoutUnit availableWidth = columnBlock->contentLogicalWidth();
 215     LayoutUnit columnGap = columnBlock->columnGap();
 216     LayoutUnit computedColumnWidth = max<LayoutUnit>(1, LayoutUnit(columnStyle->columnWidth()));
 217     unsigned computedColumnCount = max<int>(1, columnStyle->columnCount());
 218
 219     ASSERT(!columnStyle->hasAutoColumnCount() || !columnStyle->hasAutoColumnWidth());
 220     if (columnStyle->hasAutoColumnWidth() && !columnStyle->hasAutoColumnCount()) {
 221         count = computedColumnCount;
 222         width = std::max<LayoutUnit>(0, (availableWidth - ((count - 1) * columnGap)) / count);
 223     } else if (!columnStyle->hasAutoColumnWidth() && columnStyle->hasAutoColumnCount()) {
 224         count = std::max<LayoutUnit>(1, (availableWidth + columnGap) / (computedColumnWidth + columnGap));
 225         width = ((availableWidth + columnGap) / count) - columnGap;
 226     } else {
 227         count = std::max<LayoutUnit>(std::min<LayoutUnit>(computedColumnCount, (availableWidth + columnGap) / (computedColumnWidth + columnGap)), 1);
 228         width = ((availableWidth + columnGap) / count) - columnGap;
 229     }
 230 }
 231
 232 void RenderMultiColumnFlowThread::createAndInsertMultiColumnSet()
 233 {
 234     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
 235     RenderMultiColumnSet* newSet = RenderMultiColumnSet::createAnonymous(this, multicolContainer->style());
 236     multicolContainer->RenderBlock::addChild(newSet);
 237     invalidateRegions();
 238
 239     // We cannot handle immediate column set siblings (and there's no need for it, either).
 240     // There has to be at least one spanner separating them.
 241     ASSERT(!newSet->previousSiblingMultiColumnSet() || newSet->previousSiblingMultiColumnSet()->isRenderMultiColumnSpannerSet());
 242     ASSERT(!newSet->nextSiblingMultiColumnSet() || newSet->nextSiblingMultiColumnSet()->isRenderMultiColumnSpannerSet());
 243 }
 244
 245 void RenderMultiColumnFlowThread::createAndInsertSpannerSet(RenderBox* spanner)
 246 {
 247     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
 248     RenderMultiColumnSpannerSet* newSpannerSet = RenderMultiColumnSpannerSet::createAnonymous(this, multicolContainer->style(), spanner);
 249     multicolContainer->RenderBlock::addChild(newSpannerSet);
 250     m_spannerMap.add(spanner, newSpannerSet);
 251     invalidateRegions();
 252 }
 253
 254 bool RenderMultiColumnFlowThread::descendantIsValidColumnSpanner(RenderObject* descendant) const
 255 {
 256     // We assume that we're inside the flow thread. This function is not to be called otherwise.
 257     ASSERT(descendant->isDescendantOf(this));
 258
 259     // The spec says that column-span only applies to in-flow block-level elements.
 260     if (descendant->style()->columnSpan() != ColumnSpanAll || !descendant->isBox() || descendant->isInline() || descendant->isFloatingOrOutOfFlowPositioned())
 261         return false;
 262
 263     if (!descendant->containingBlock()->isRenderBlockFlow()) {
 264         // Needs to be in a block-flow container, and not e.g. a table.
 265         return false;
 266     }
 267
 268     // This looks like a spanner, but if we're inside something unbreakable, it's not to be treated as one.
 269     for (RenderBlock* ancestor = descendant->containingBlock(); ancestor && ancestor->flowThreadContainingBlock() == this; ancestor = ancestor->containingBlock()) {
 270         if (ancestor->isRenderFlowThread()) {
 271             ASSERT(ancestor == this);
 272             return true;
 273         }
 274         if (m_spannerMap.get(ancestor)) {
 275             // FIXME: do we want to support nested spanners in a different way? The outer spanner
 276             // has already broken out from the columns to become sized by the multicol container,
 277             // which may be good enough for the inner spanner. But margins, borders, padding and
 278             // explicit widths on the outer spanner, or on any children between the outer and inner
 279             // spanner, will affect the width of the inner spanner this way, which might be
 280             // undesirable. The spec has nothing to say on the matter.
 281             return false; // Ignore nested spanners.
 282         }
 283         if (ancestor->isUnsplittableForPagination())
 284             return false;
 285     }
 286     ASSERT_NOT_REACHED();
 287     return false;
 288 }
 289
 290 const char* RenderMultiColumnFlowThread::renderName() const
 291 {
 292     return "RenderMultiColumnFlowThread";
 293 }
 294
 295 void RenderMultiColumnFlowThread::addRegionToThread(RenderMultiColumnSet* columnSet)
 296 {
 297     if (RenderMultiColumnSet* nextSet = columnSet->nextSiblingMultiColumnSet()) {
 298         RenderMultiColumnSetList::iterator it = m_multiColumnSetList.find(nextSet);
 299         ASSERT(it != m_multiColumnSetList.end());
 300         m_multiColumnSetList.insertBefore(it, columnSet);
 301     } else {
 302         m_multiColumnSetList.add(columnSet);
 303     }
 304     columnSet->setIsValid(true);
 305 }
 306
 307 void RenderMultiColumnFlowThread::willBeRemovedFromTree()
 308 {
 309     m_spannerMap.clear();
 310     // Detach all column sets from the flow thread. Cannot destroy them at this point, since they
 311     // are siblings of this object, and there may be pointers to this object's sibling somewhere
 312     // further up on the call stack.
 313     for (RenderMultiColumnSet* columnSet = firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet())
 314         columnSet->detachRegion();
 315     multiColumnBlockFlow()->resetMultiColumnFlowThread();
 316     RenderFlowThread::willBeRemovedFromTree();
 317 }
 318
 319 void RenderMultiColumnFlowThread::flowThreadDescendantWasInserted(RenderObject* descendant)
 320 {
 321     // Go through the subtree that was just inserted and create column sets (needed by regular
 322     // column content) and spanner sets (one needed by each spanner).
 323     for (RenderObject* renderer = descendant; renderer; renderer = renderer->nextInPreOrder(descendant)) {
 324         if (containingColumnSpannerSet(renderer))
 325             continue; // Inside a column spanner set. Nothing to do, then.
 326         if (descendantIsValidColumnSpanner(renderer)) {
 327             // This renderer is a spanner, so it needs to establish a spanner set.
 328             createAndInsertSpannerSet(toRenderBox(renderer));
 329             continue;
 330         }
 331         // This renderer is regular column content (i.e. not a spanner). Create a set if necessary.
 332         RenderMultiColumnSet* lastSet = lastMultiColumnSet();
 333         if (!lastSet || lastSet->isRenderMultiColumnSpannerSet())
 334             createAndInsertMultiColumnSet();
 335     }
 336 }
 337
 338 void RenderMultiColumnFlowThread::computeLogicalHeight(LayoutUnit logicalHeight, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
 339 {
 340     // We simply remain at our intrinsic height.
 341     computedValues.m_extent = logicalHeight;
 342     computedValues.m_position = logicalTop;
 343 }
 344
 345 void RenderMultiColumnFlowThread::updateLogicalWidth()
 346 {
 347     LayoutUnit columnWidth;
 348     calculateColumnCountAndWidth(columnWidth, m_columnCount);
 349     setLogicalWidth(columnWidth);
 350 }
 351
 352 void RenderMultiColumnFlowThread::layout()
 353 {
 354     RenderFlowThread::layout();
 355     if (RenderMultiColumnSet* lastSet = lastMultiColumnSet())
 356         lastSet->expandToEncompassFlowThreadContentsIfNeeded();
 357 }
 358
 359 void RenderMultiColumnFlowThread::setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage)
 360 {
 361     // Only positive values are interesting (and allowed) here. Zero space shortage may be reported
 362     // when we're at the top of a column and the element has zero height. Ignore this, and also
 363     // ignore any negative values, which may occur when we set an early break in order to honor
 364     // widows in the next column.
 365     if (spaceShortage <= 0)
 366         return;
 367
 368     if (RenderMultiColumnSet* multicolSet = columnSetAtBlockOffset(offset))
 369         multicolSet->recordSpaceShortage(spaceShortage);
 370 }
 371
 372 void RenderMultiColumnFlowThread::updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight)
 373 {
 374     if (RenderMultiColumnSet* multicolSet = columnSetAtBlockOffset(offset))
 375         multicolSet->updateMinimumColumnHeight(minHeight);
 376 }
 377
 378 RenderMultiColumnSet* RenderMultiColumnFlowThread::columnSetAtBlockOffset(LayoutUnit /*offset*/) const
 379 {
 380     // For now there's only one column set, so this is easy:
 381     return firstMultiColumnSet();
 382 }
 383
 384 bool RenderMultiColumnFlowThread::addForcedRegionBreak(LayoutUnit offset, RenderObject* /*breakChild*/, bool /*isBefore*/, LayoutUnit* offsetBreakAdjustment)
 385 {
 386     if (RenderMultiColumnSet* multicolSet = columnSetAtBlockOffset(offset)) {
 387         multicolSet->addContentRun(offset);
 388         if (offsetBreakAdjustment)
 389             *offsetBreakAdjustment = pageLogicalHeightForOffset(offset) ? pageRemainingLogicalHeightForOffset(offset, IncludePageBoundary) : LayoutUnit();
 390         return true;
 391     }
 392     return false;
 393 }
 394
 395 bool RenderMultiColumnFlowThread::isPageLogicalHeightKnown() const
 396 {
 397     if (RenderMultiColumnSet* columnSet = lastMultiColumnSet())
 398         return columnSet->pageLogicalHeight();
 399     return false;
 400 }
 401
 402 }