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