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