[CSSRegions] Use auto keyword to clean-up for loops
[WebKit-https.git] / Source / WebCore / rendering / RenderNamedFlowThread.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 "RenderNamedFlowThread.h"
28
29 #include "ExceptionCodePlaceholder.h"
30 #include "FlowThreadController.h"
31 #include "InlineTextBox.h"
32 #include "InspectorInstrumentation.h"
33 #include "NodeRenderingTraversal.h"
34 #include "NodeTraversal.h"
35 #include "Position.h"
36 #include "Range.h"
37 #include "RenderInline.h"
38 #include "RenderRegion.h"
39 #include "RenderText.h"
40 #include "RenderView.h"
41 #include "ShadowRoot.h"
42 #include "Text.h"
43 #include "WebKitNamedFlow.h"
44
45 namespace WebCore {
46
47 RenderNamedFlowThread::RenderNamedFlowThread(Document& document, PassRef<RenderStyle> style, PassRefPtr<WebKitNamedFlow> namedFlow)
48     : RenderFlowThread(document, std::move(style))
49     , m_flowThreadChildList(adoptPtr(new FlowThreadChildList()))
50     , m_overset(true)
51     , m_namedFlow(namedFlow)
52     , m_regionLayoutUpdateEventTimer(this, &RenderNamedFlowThread::regionLayoutUpdateEventTimerFired)
53     , m_regionOversetChangeEventTimer(this, &RenderNamedFlowThread::regionOversetChangeEventTimerFired)
54 {
55 }
56
57 RenderNamedFlowThread::~RenderNamedFlowThread()
58 {
59     // The flow thread can be destroyed without unregistering the content nodes if the document is destroyed.
60     // This can lead to problems because the nodes are still marked as belonging to a flow thread.
61     clearContentElements();
62
63     // Also leave the NamedFlow object in a consistent state by calling mark for destruction.
64     setMarkForDestruction();
65 }
66
67 const char* RenderNamedFlowThread::renderName() const
68 {    
69     return "RenderNamedFlowThread";
70 }
71     
72 void RenderNamedFlowThread::clearContentElements()
73 {
74     for (auto it = m_contentElements.begin(), end = m_contentElements.end(); it != end; ++it) {
75         Element* contentElement = *it;
76         
77         ASSERT(contentElement);
78         ASSERT(contentElement->inNamedFlow());
79         ASSERT(&contentElement->document() == &document());
80         
81         contentElement->clearInNamedFlow();
82     }
83     
84     m_contentElements.clear();
85 }
86
87 void RenderNamedFlowThread::updateWritingMode()
88 {
89     RenderRegion* firstRegion = m_regionList.first();
90     if (!firstRegion)
91         return;
92     if (style().writingMode() == firstRegion->style().writingMode())
93         return;
94
95     // The first region defines the principal writing mode for the entire flow.
96     auto newStyle = RenderStyle::clone(&style());
97     newStyle.get().setWritingMode(firstRegion->style().writingMode());
98     setStyle(std::move(newStyle));
99 }
100
101 RenderObject* RenderNamedFlowThread::nextRendererForNode(Node* node) const
102 {
103     for (auto it = m_flowThreadChildList->begin(), end = m_flowThreadChildList->end(); it != end; ++it) {
104         RenderObject* child = *it;
105         ASSERT(child->node());
106         unsigned short position = node->compareDocumentPosition(child->node());
107         if (position & Node::DOCUMENT_POSITION_FOLLOWING)
108             return child;
109     }
110
111     return 0;
112 }
113
114 RenderObject* RenderNamedFlowThread::previousRendererForNode(Node* node) const
115 {
116     if (m_flowThreadChildList->isEmpty())
117         return 0;
118
119     auto begin = m_flowThreadChildList->begin();
120     auto end = m_flowThreadChildList->end();
121     auto it = end;
122
123     do {
124         --it;
125         RenderObject* child = *it;
126         ASSERT(child->node());
127         unsigned short position = node->compareDocumentPosition(child->node());
128         if (position & Node::DOCUMENT_POSITION_PRECEDING)
129             return child;
130     } while (it != begin);
131
132     return 0;
133 }
134
135 void RenderNamedFlowThread::addFlowChild(RenderObject* newChild)
136 {
137     // The child list is used to sort the flow thread's children render objects 
138     // based on their corresponding nodes DOM order. The list is needed to avoid searching the whole DOM.
139
140     Node* childNode = newChild->node();
141
142     // Do not add anonymous objects.
143     if (!childNode)
144         return;
145
146     ASSERT(childNode->isElementNode());
147
148     RenderObject* beforeChild = nextRendererForNode(childNode);
149     if (beforeChild)
150         m_flowThreadChildList->insertBefore(beforeChild, newChild);
151     else
152         m_flowThreadChildList->add(newChild);
153 }
154
155 void RenderNamedFlowThread::removeFlowChild(RenderObject* child)
156 {
157     m_flowThreadChildList->remove(child);
158 }
159
160 bool RenderNamedFlowThread::dependsOn(RenderNamedFlowThread* otherRenderFlowThread) const
161 {
162     if (m_layoutBeforeThreadsSet.contains(otherRenderFlowThread))
163         return true;
164
165     // Recursively traverse the m_layoutBeforeThreadsSet.
166     for (auto iterator = m_layoutBeforeThreadsSet.begin(), end = m_layoutBeforeThreadsSet.end(); iterator != end; ++iterator) {
167         const RenderNamedFlowThread* beforeFlowThread = (*iterator).key;
168         if (beforeFlowThread->dependsOn(otherRenderFlowThread))
169             return true;
170     }
171
172     return false;
173 }
174
175 // Compare two regions to determine in which one the content should flow first.
176 // The function returns true if the first passed region is "less" than the second passed region.
177 // If the first region appears before second region in DOM,
178 // the first region is "less" than the second region.
179 // If the first region is "less" than the second region, the first region receives content before second region.
180 static bool compareRenderRegions(const RenderRegion* firstRegion, const RenderRegion* secondRegion)
181 {
182     ASSERT(firstRegion);
183     ASSERT(secondRegion);
184
185     ASSERT(firstRegion->generatingElement());
186     ASSERT(secondRegion->generatingElement());
187
188     // If the regions belong to different nodes, compare their position in the DOM.
189     if (firstRegion->generatingElement() != secondRegion->generatingElement()) {
190         unsigned short position = firstRegion->generatingElement()->compareDocumentPosition(secondRegion->generatingElement());
191
192         // If the second region is contained in the first one, the first region is "less" if it's :before.
193         if (position & Node::DOCUMENT_POSITION_CONTAINED_BY) {
194             ASSERT(secondRegion->style().styleType() == NOPSEUDO);
195             return firstRegion->style().styleType() == BEFORE;
196         }
197
198         // If the second region contains the first region, the first region is "less" if the second is :after.
199         if (position & Node::DOCUMENT_POSITION_CONTAINS) {
200             ASSERT(firstRegion->style().styleType() == NOPSEUDO);
201             return secondRegion->style().styleType() == AFTER;
202         }
203
204         return (position & Node::DOCUMENT_POSITION_FOLLOWING);
205     }
206
207     // FIXME: Currently it's not possible for an element to be both a region and have pseudo-children. The case is covered anyway.
208     switch (firstRegion->style().styleType()) {
209     case BEFORE:
210         // The second region can be the node or the after pseudo-element (before is smaller than any of those).
211         return true;
212     case AFTER:
213         // The second region can be the node or the before pseudo-element (after is greater than any of those).
214         return false;
215     case NOPSEUDO:
216         // The second region can either be the before or the after pseudo-element (the node is only smaller than the after pseudo-element).
217         return firstRegion->style().styleType() == AFTER;
218     default:
219         break;
220     }
221
222     ASSERT_NOT_REACHED();
223     return true;
224 }
225
226 // This helper function adds a region to a list preserving the order property of the list.
227 static void addRegionToList(RenderRegionList& regionList, RenderRegion* renderRegion)
228 {
229     if (regionList.isEmpty())
230         regionList.add(renderRegion);
231     else {
232         // Find the first region "greater" than renderRegion.
233         auto it = regionList.begin();
234         while (it != regionList.end() && !compareRenderRegions(renderRegion, *it))
235             ++it;
236         regionList.insertBefore(it, renderRegion);
237     }
238 }
239
240 void RenderNamedFlowThread::addRegionToNamedFlowThread(RenderRegion* renderRegion)
241 {
242     ASSERT(renderRegion);
243     ASSERT(!renderRegion->isValid());
244
245     if (renderRegion->parentNamedFlowThread())
246         addDependencyOnFlowThread(renderRegion->parentNamedFlowThread());
247
248     renderRegion->setIsValid(true);
249     addRegionToList(m_regionList, renderRegion);
250
251     if (m_regionList.first() == renderRegion)
252         updateWritingMode();
253 }
254
255 void RenderNamedFlowThread::addRegionToThread(RenderRegion* renderRegion)
256 {
257     ASSERT(renderRegion);
258     ASSERT(!renderRegion->isValid());
259
260     resetMarkForDestruction();
261
262     if (renderRegion->parentNamedFlowThread() && renderRegion->parentNamedFlowThread()->dependsOn(this)) {
263         // The order of invalid regions is irrelevant.
264         m_invalidRegionList.add(renderRegion);
265         // Register ourself to get a notification when the state changes.
266         renderRegion->parentNamedFlowThread()->m_observerThreadsSet.add(this);
267         return;
268     }
269
270     addRegionToNamedFlowThread(renderRegion);
271
272     invalidateRegions();
273 }
274
275 void RenderNamedFlowThread::removeRegionFromThread(RenderRegion* renderRegion)
276 {
277     ASSERT(renderRegion);
278
279     if (renderRegion->parentNamedFlowThread()) {
280         if (!renderRegion->isValid()) {
281             ASSERT(m_invalidRegionList.contains(renderRegion));
282             m_invalidRegionList.remove(renderRegion);
283             renderRegion->parentNamedFlowThread()->m_observerThreadsSet.remove(this);
284             // No need to invalidate the regions rectangles. The removed region
285             // was not taken into account. Just return here.
286             return;
287         }
288         removeDependencyOnFlowThread(renderRegion->parentNamedFlowThread());
289     }
290
291     ASSERT(m_regionList.contains(renderRegion));
292     bool wasFirst = m_regionList.first() == renderRegion;
293     m_regionList.remove(renderRegion);
294
295     if (canBeDestroyed())
296         setMarkForDestruction();
297
298     // After removing all the regions in the flow the following layout needs to dispatch the regionLayoutUpdate event
299     if (m_regionList.isEmpty())
300         setDispatchRegionLayoutUpdateEvent(true);
301     else if (wasFirst)
302         updateWritingMode();
303
304     invalidateRegions();
305 }
306
307 void RenderNamedFlowThread::regionChangedWritingMode(RenderRegion* region)
308 {
309     if (m_regionList.first() == region)
310         updateWritingMode();
311 }
312
313 void RenderNamedFlowThread::computeOversetStateForRegions(LayoutUnit oldClientAfterEdge)
314 {
315     LayoutUnit height = oldClientAfterEdge;
316
317     // FIXME: the visual overflow of middle region (if it is the last one to contain any content in a render flow thread)
318     // might not be taken into account because the render flow thread height is greater that that regions height + its visual overflow
319     // because of how computeLogicalHeight is implemented for RenderNamedFlowThread (as a sum of all regions height).
320     // This means that the middle region will be marked as fit (even if it has visual overflow flowing into the next region)
321     if (hasRenderOverflow()
322         && ( (isHorizontalWritingMode() && visualOverflowRect().maxY() > clientBoxRect().maxY())
323             || (!isHorizontalWritingMode() && visualOverflowRect().maxX() > clientBoxRect().maxX())))
324         height = isHorizontalWritingMode() ? visualOverflowRect().maxY() : visualOverflowRect().maxX();
325
326     RenderRegion* lastReg = lastRegion();
327     for (auto iter = m_regionList.begin(), end = m_regionList.end(); iter != end; ++iter) {
328         RenderRegion* region = *iter;
329         LayoutUnit flowMin = height - (isHorizontalWritingMode() ? region->flowThreadPortionRect().y() : region->flowThreadPortionRect().x());
330         LayoutUnit flowMax = height - (isHorizontalWritingMode() ? region->flowThreadPortionRect().maxY() : region->flowThreadPortionRect().maxX());
331         RegionOversetState previousState = region->regionOversetState();
332         RegionOversetState state = RegionFit;
333         if (flowMin <= 0)
334             state = RegionEmpty;
335         if (flowMax > 0 && region == lastReg)
336             state = RegionOverset;
337         region->setRegionOversetState(state);
338         // determine whether the NamedFlow object should dispatch a regionLayoutUpdate event
339         // FIXME: currently it cannot determine whether a region whose regionOverset state remained either "fit" or "overset" has actually
340         // changed, so it just assumes that the NamedFlow should dispatch the event
341         if (previousState != state
342             || state == RegionFit
343             || state == RegionOverset)
344             setDispatchRegionLayoutUpdateEvent(true);
345         
346         if (previousState != state)
347             setDispatchRegionOversetChangeEvent(true);
348     }
349     
350     // If the number of regions has changed since we last computed the overset property, schedule the regionOversetChange event.
351     if (previousRegionCountChanged()) {
352         setDispatchRegionOversetChangeEvent(true);
353         updatePreviousRegionCount();
354     }
355
356     // With the regions overflow state computed we can also set the overset flag for the named flow.
357     // If there are no valid regions in the chain, overset is true.
358     m_overset = lastReg ? lastReg->regionOversetState() == RegionOverset : true;
359 }
360
361 void RenderNamedFlowThread::checkInvalidRegions()
362 {
363     Vector<RenderRegion*> newValidRegions;
364     for (auto iter = m_invalidRegionList.begin(), end = m_invalidRegionList.end(); iter != end; ++iter) {
365         RenderRegion* region = *iter;
366         // The only reason a region would be invalid is because it has a parent flow thread.
367         ASSERT(!region->isValid() && region->parentNamedFlowThread());
368         if (region->parentNamedFlowThread()->dependsOn(this))
369             continue;
370
371         newValidRegions.append(region);
372     }
373
374     for (auto iter = newValidRegions.begin(), end = newValidRegions.end(); iter != end; ++iter) {
375         RenderRegion* region = *iter;
376         m_invalidRegionList.remove(region);
377         region->parentNamedFlowThread()->m_observerThreadsSet.remove(this);
378         addRegionToNamedFlowThread(region);
379     }
380
381     if (!newValidRegions.isEmpty())
382         invalidateRegions();
383
384     if (m_observerThreadsSet.isEmpty())
385         return;
386
387     // Notify all the flow threads that were dependent on this flow.
388
389     // Create a copy of the list first. That's because observers might change the list when calling checkInvalidRegions.
390     Vector<RenderNamedFlowThread*> observers;
391     copyToVector(m_observerThreadsSet, observers);
392
393     for (size_t i = 0; i < observers.size(); ++i) {
394         RenderNamedFlowThread* flowThread = observers.at(i);
395         flowThread->checkInvalidRegions();
396     }
397 }
398
399 void RenderNamedFlowThread::addDependencyOnFlowThread(RenderNamedFlowThread* otherFlowThread)
400 {
401     RenderNamedFlowThreadCountedSet::AddResult result = m_layoutBeforeThreadsSet.add(otherFlowThread);
402     if (result.isNewEntry) {
403         // This is the first time we see this dependency. Make sure we recalculate all the dependencies.
404         view().flowThreadController().setIsRenderNamedFlowThreadOrderDirty(true);
405     }
406 }
407
408 void RenderNamedFlowThread::removeDependencyOnFlowThread(RenderNamedFlowThread* otherFlowThread)
409 {
410     bool removed = m_layoutBeforeThreadsSet.remove(otherFlowThread);
411     if (removed) {
412         checkInvalidRegions();
413         view().flowThreadController().setIsRenderNamedFlowThreadOrderDirty(true);
414     }
415 }
416
417 void RenderNamedFlowThread::pushDependencies(RenderNamedFlowThreadList& list)
418 {
419     for (auto iter = m_layoutBeforeThreadsSet.begin(), end = m_layoutBeforeThreadsSet.end(); iter != end; ++iter) {
420         RenderNamedFlowThread* flowThread = (*iter).key;
421         if (list.contains(flowThread))
422             continue;
423         flowThread->pushDependencies(list);
424         list.add(flowThread);
425     }
426 }
427
428 // The content nodes list contains those nodes with -webkit-flow-into: flow.
429 // An element with display:none should also be listed among those nodes.
430 // The list of nodes is ordered.
431 void RenderNamedFlowThread::registerNamedFlowContentElement(Element& contentElement)
432 {
433     ASSERT(&contentElement.document() == &document());
434
435     contentElement.setInNamedFlow();
436
437     resetMarkForDestruction();
438
439     // Find the first content node following the new content node.
440     for (auto it = m_contentElements.begin(), end = m_contentElements.end(); it != end; ++it) {
441         Element* element = *it;
442         unsigned short position = contentElement.compareDocumentPosition(element);
443         if (position & Node::DOCUMENT_POSITION_FOLLOWING) {
444             m_contentElements.insertBefore(element, &contentElement);
445             InspectorInstrumentation::didRegisterNamedFlowContentElement(&document(), m_namedFlow.get(), &contentElement, element);
446             return;
447         }
448     }
449
450     m_contentElements.add(&contentElement);
451     InspectorInstrumentation::didRegisterNamedFlowContentElement(&document(), m_namedFlow.get(), &contentElement);
452 }
453
454 void RenderNamedFlowThread::unregisterNamedFlowContentElement(Element& contentElement)
455 {
456     ASSERT(m_contentElements.contains(&contentElement));
457     ASSERT(contentElement.inNamedFlow());
458     ASSERT(&contentElement.document() == &document());
459
460     contentElement.clearInNamedFlow();
461     m_contentElements.remove(&contentElement);
462
463     if (canBeDestroyed())
464         setMarkForDestruction();
465
466     InspectorInstrumentation::didUnregisterNamedFlowContentElement(&document(), m_namedFlow.get(), &contentElement);
467 }
468
469 bool RenderNamedFlowThread::hasContentElement(Element& contentElement) const
470 {
471     return m_contentElements.contains(&contentElement);
472 }
473     
474 const AtomicString& RenderNamedFlowThread::flowThreadName() const
475 {
476     return m_namedFlow->name();
477 }
478
479 bool RenderNamedFlowThread::isChildAllowed(const RenderObject& child, const RenderStyle& style) const
480 {
481     if (!child.node())
482         return true;
483
484     ASSERT(child.node()->isElementNode());
485
486     Node* originalParent = NodeRenderingTraversal::parent(child.node());
487     if (!originalParent || !originalParent->isElementNode() || !originalParent->renderer())
488         return true;
489
490     return toElement(originalParent)->renderer()->isChildAllowed(child, style);
491 }
492
493 void RenderNamedFlowThread::dispatchRegionLayoutUpdateEvent()
494 {
495     RenderFlowThread::dispatchRegionLayoutUpdateEvent();
496     InspectorInstrumentation::didUpdateRegionLayout(&document(), m_namedFlow.get());
497
498     if (!m_regionLayoutUpdateEventTimer.isActive() && m_namedFlow->hasEventListeners())
499         m_regionLayoutUpdateEventTimer.startOneShot(0);
500 }
501
502 void RenderNamedFlowThread::dispatchRegionOversetChangeEvent()
503 {
504     RenderFlowThread::dispatchRegionOversetChangeEvent();
505     InspectorInstrumentation::didChangeRegionOverset(&document(), m_namedFlow.get());
506     
507     if (!m_regionOversetChangeEventTimer.isActive() && m_namedFlow->hasEventListeners())
508         m_regionOversetChangeEventTimer.startOneShot(0);
509 }
510
511 void RenderNamedFlowThread::regionLayoutUpdateEventTimerFired(Timer<RenderNamedFlowThread>*)
512 {
513     ASSERT(m_namedFlow);
514
515     m_namedFlow->dispatchRegionLayoutUpdateEvent();
516 }
517
518 void RenderNamedFlowThread::regionOversetChangeEventTimerFired(Timer<RenderNamedFlowThread>*)
519 {
520     ASSERT(m_namedFlow);
521     
522     m_namedFlow->dispatchRegionOversetChangeEvent();
523 }
524
525 void RenderNamedFlowThread::setMarkForDestruction()
526 {
527     if (m_namedFlow->flowState() == WebKitNamedFlow::FlowStateNull)
528         return;
529
530     m_namedFlow->setRenderer(0);
531     // After this call ends, the renderer can be safely destroyed.
532     // The NamedFlow object may outlive its renderer if it's referenced from a script and may be reatached to one if the named flow is recreated in the stylesheet.
533 }
534
535 void RenderNamedFlowThread::resetMarkForDestruction()
536 {
537     if (m_namedFlow->flowState() == WebKitNamedFlow::FlowStateCreated)
538         return;
539
540     m_namedFlow->setRenderer(this);
541 }
542
543 bool RenderNamedFlowThread::isMarkedForDestruction() const
544 {
545     // Flow threads in the "NULL" state can be destroyed.
546     return m_namedFlow->flowState() == WebKitNamedFlow::FlowStateNull;
547 }
548
549 static bool isContainedInElements(const Vector<Element*>& others, Element* element)
550 {
551     for (size_t i = 0; i < others.size(); i++) {
552         Element* other = others.at(i);
553         if (other->contains(element))
554             return true;
555     }
556     return false;
557 }
558
559 static bool boxIntersectsRegion(LayoutUnit logicalTopForBox, LayoutUnit logicalBottomForBox, LayoutUnit logicalTopForRegion, LayoutUnit logicalBottomForRegion)
560 {
561     bool regionIsEmpty = logicalBottomForRegion != LayoutUnit::max() && logicalTopForRegion != LayoutUnit::min()
562         && (logicalBottomForRegion - logicalTopForRegion) <= 0;
563     return  (logicalBottomForBox - logicalTopForBox) > 0
564         && !regionIsEmpty
565         && logicalTopForBox < logicalBottomForRegion && logicalTopForRegion < logicalBottomForBox;
566 }
567
568 // Retrieve the next node to be visited while computing the ranges inside a region.
569 static Node* nextNodeInsideContentElement(const Node* currNode, const Element* contentElement)
570 {
571     ASSERT(currNode);
572     ASSERT(contentElement && contentElement->inNamedFlow());
573
574 #if ENABLE(SVG)
575     if (currNode->renderer() && currNode->renderer()->isSVGRoot())
576         return NodeTraversal::nextSkippingChildren(currNode, contentElement);
577 #endif
578     return NodeTraversal::next(currNode, contentElement);
579 }
580
581 void RenderNamedFlowThread::getRanges(Vector<RefPtr<Range>>& rangeObjects, const RenderRegion* region) const
582 {
583     LayoutUnit logicalTopForRegion;
584     LayoutUnit logicalBottomForRegion;
585
586     // extend the first region top to contain everything up to its logical height
587     if (region->isFirstRegion())
588         logicalTopForRegion = LayoutUnit::min();
589     else
590         logicalTopForRegion =  region->logicalTopForFlowThreadContent();
591
592     // extend the last region to contain everything above its y()
593     if (region->isLastRegion())
594         logicalBottomForRegion = LayoutUnit::max();
595     else
596         logicalBottomForRegion = region->logicalBottomForFlowThreadContent();
597
598     Vector<Element*> elements;
599     // eliminate the contentElements that are descendants of other contentElements
600     for (auto it = contentElements().begin(), end = contentElements().end(); it != end; ++it) {
601         Element* element = *it;
602         if (!isContainedInElements(elements, element))
603             elements.append(element);
604     }
605
606     for (size_t i = 0; i < elements.size(); i++) {
607         Element* contentElement = elements.at(i);
608         if (!contentElement->renderer())
609             continue;
610
611         RefPtr<Range> range = Range::create(contentElement->document());
612         bool foundStartPosition = false;
613         bool startsAboveRegion = true;
614         bool endsBelowRegion = true;
615         bool skipOverOutsideNodes = false;
616         Node* lastEndNode = 0;
617
618         for (Node* node = contentElement; node; node = nextNodeInsideContentElement(node, contentElement)) {
619             RenderObject* renderer = node->renderer();
620             if (!renderer)
621                 continue;
622
623             LayoutRect boundingBox;
624             if (renderer->isRenderInline())
625                 boundingBox = toRenderInline(renderer)->linesBoundingBox();
626             else if (renderer->isText())
627                 boundingBox = toRenderText(renderer)->linesBoundingBox();
628             else {
629                 boundingBox =  toRenderBox(renderer)->frameRect();
630                 if (toRenderBox(renderer)->isRelPositioned())
631                     boundingBox.move(toRenderBox(renderer)->relativePositionLogicalOffset());
632             }
633
634             LayoutUnit offsetTop = renderer->containingBlock()->offsetFromLogicalTopOfFirstPage();
635             const LayoutPoint logicalOffsetFromTop(isHorizontalWritingMode() ? LayoutUnit() :  offsetTop,
636                 isHorizontalWritingMode() ? offsetTop : LayoutUnit());
637
638             boundingBox.moveBy(logicalOffsetFromTop);
639
640             LayoutUnit logicalTopForRenderer = region->logicalTopOfFlowThreadContentRect(boundingBox);
641             LayoutUnit logicalBottomForRenderer = region->logicalBottomOfFlowThreadContentRect(boundingBox);
642
643             // if the bounding box of the current element doesn't intersect the region box
644             // close the current range only if the start element began inside the region,
645             // otherwise just move the start position after this node and keep skipping them until we found a proper start position.
646             if (!boxIntersectsRegion(logicalTopForRenderer, logicalBottomForRenderer, logicalTopForRegion, logicalBottomForRegion)) {
647                 if (foundStartPosition) {
648                     if (!startsAboveRegion) {
649                         if (range->intersectsNode(node, IGNORE_EXCEPTION))
650                             range->setEndBefore(node, IGNORE_EXCEPTION);
651                         rangeObjects.append(range->cloneRange(IGNORE_EXCEPTION));
652                         range = Range::create(contentElement->document());
653                         startsAboveRegion = true;
654                     } else
655                         skipOverOutsideNodes = true;
656                 }
657                 if (skipOverOutsideNodes)
658                     range->setStartAfter(node, IGNORE_EXCEPTION);
659                 foundStartPosition = false;
660                 continue;
661             }
662
663             // start position
664             if (logicalTopForRenderer < logicalTopForRegion && startsAboveRegion) {
665                 if (renderer->isText()) { // Text crosses region top
666                     // for Text elements, just find the last textbox that is contained inside the region and use its start() offset as start position
667                     RenderText* textRenderer = toRenderText(renderer);
668                     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
669                         if (offsetTop + box->logicalBottom() < logicalTopForRegion)
670                             continue;
671                         range->setStart(Position(toText(node), box->start()));
672                         startsAboveRegion = false;
673                         break;
674                     }
675                 } else { // node crosses region top
676                     // for all elements, except Text, just set the start position to be before their children
677                     startsAboveRegion = true;
678                     range->setStart(Position(node, Position::PositionIsBeforeChildren));
679                 }
680             } else { // node starts inside region
681                 // for elements that start inside the region, set the start position to be before them. If we found one, we will just skip the others until
682                 // the range is closed.
683                 if (startsAboveRegion) {
684                     startsAboveRegion = false;
685                     range->setStartBefore(node, IGNORE_EXCEPTION);
686                 }
687             }
688             skipOverOutsideNodes  = false;
689             foundStartPosition = true;
690
691             // end position
692             if (logicalBottomForRegion < logicalBottomForRenderer && (endsBelowRegion || (!endsBelowRegion && !node->isDescendantOf(lastEndNode)))) {
693                 // for Text elements, just find just find the last textbox that is contained inside the region and use its start()+len() offset as end position
694                 if (renderer->isText()) { // Text crosses region bottom
695                     RenderText* textRenderer = toRenderText(renderer);
696                     InlineTextBox* lastBox = 0;
697                     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
698                         if ((offsetTop + box->logicalTop()) < logicalBottomForRegion) {
699                             lastBox = box;
700                             continue;
701                         }
702                         ASSERT(lastBox);
703                         if (lastBox)
704                             range->setEnd(Position(toText(node), lastBox->start() + lastBox->len()));
705                         break;
706                     }
707                     endsBelowRegion = false;
708                     lastEndNode = node;
709                 } else { // node crosses region bottom
710                     // for all elements, except Text, just set the start position to be after their children
711                     range->setEnd(Position(node, Position::PositionIsAfterChildren));
712                     endsBelowRegion = true;
713                     lastEndNode = node;
714                 }
715             } else { // node ends inside region
716                 // for elements that ends inside the region, set the end position to be after them
717                 // allow this end position to be changed only by other elements that are not descendants of the current end node
718                 if (endsBelowRegion || (!endsBelowRegion && !node->isDescendantOf(lastEndNode))) {
719                     range->setEndAfter(node, IGNORE_EXCEPTION);
720                     endsBelowRegion = false;
721                     lastEndNode = node;
722                 }
723             }
724         }
725         if (foundStartPosition || skipOverOutsideNodes)
726             rangeObjects.append(range);
727     }
728 }
729
730 #if USE(ACCELERATED_COMPOSITING)
731 bool RenderNamedFlowThread::collectsGraphicsLayersUnderRegions() const
732 {
733     // We only need to map layers to regions for named flow threads.
734     // Multi-column threads are displayed on top of the regions and do not require
735     // distributing the layers.
736
737     return true;
738 }
739 #endif
740
741 }