Unreviewed build fix after 156082. Guard SVG code with defines.
[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     clearContentNodes();
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::clearContentNodes()
79 {
80     for (NamedFlowContentNodes::iterator it = m_contentNodes.begin(); it != m_contentNodes.end(); ++it) {
81         Node* contentNode = *it;
82         
83         ASSERT(contentNode && contentNode->isElementNode());
84         ASSERT(contentNode->inNamedFlow());
85         ASSERT(&contentNode->document() == &document());
86         
87         contentNode->clearInNamedFlow();
88     }
89     
90     m_contentNodes.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::registerNamedFlowContentNode(Node* contentNode)
443 {
444     ASSERT(contentNode && contentNode->isElementNode());
445     ASSERT(&contentNode->document() == &document());
446
447     contentNode->setInNamedFlow();
448
449     resetMarkForDestruction();
450
451     // Find the first content node following the new content node.
452     for (NamedFlowContentNodes::iterator it = m_contentNodes.begin(); it != m_contentNodes.end(); ++it) {
453         Node* node = *it;
454         unsigned short position = contentNode->compareDocumentPosition(node);
455         if (position & Node::DOCUMENT_POSITION_FOLLOWING) {
456             m_contentNodes.insertBefore(node, contentNode);
457             return;
458         }
459     }
460     m_contentNodes.add(contentNode);
461 }
462
463 void RenderNamedFlowThread::unregisterNamedFlowContentNode(Node* contentNode)
464 {
465     ASSERT(contentNode && contentNode->isElementNode());
466     ASSERT(m_contentNodes.contains(contentNode));
467     ASSERT(contentNode->inNamedFlow());
468     ASSERT(&contentNode->document() == &document());
469
470     contentNode->clearInNamedFlow();
471     m_contentNodes.remove(contentNode);
472
473     if (canBeDestroyed())
474         setMarkForDestruction();
475 }
476
477 const AtomicString& RenderNamedFlowThread::flowThreadName() const
478 {
479     return m_namedFlow->name();
480 }
481
482 bool RenderNamedFlowThread::isChildAllowed(RenderObject* child, RenderStyle* style) const
483 {
484     if (!child->node())
485         return true;
486
487     ASSERT(child->node()->isElementNode());
488     Node* originalParent = NodeRenderingTraversal::parent(child->node());
489
490     if (!originalParent || !originalParent->renderer())
491         return true;
492
493     return originalParent->renderer()->isChildAllowed(child, style);
494 }
495
496 void RenderNamedFlowThread::dispatchRegionLayoutUpdateEvent()
497 {
498     RenderFlowThread::dispatchRegionLayoutUpdateEvent();
499     InspectorInstrumentation::didUpdateRegionLayout(&document(), m_namedFlow.get());
500
501     if (!m_regionLayoutUpdateEventTimer.isActive() && m_namedFlow->hasEventListeners())
502         m_regionLayoutUpdateEventTimer.startOneShot(0);
503 }
504
505 void RenderNamedFlowThread::dispatchRegionOversetChangeEvent()
506 {
507     RenderFlowThread::dispatchRegionOversetChangeEvent();
508     InspectorInstrumentation::didChangeRegionOverset(&document(), m_namedFlow.get());
509     
510     if (!m_regionOversetChangeEventTimer.isActive() && m_namedFlow->hasEventListeners())
511         m_regionOversetChangeEventTimer.startOneShot(0);
512 }
513
514 void RenderNamedFlowThread::regionLayoutUpdateEventTimerFired(Timer<RenderNamedFlowThread>*)
515 {
516     ASSERT(m_namedFlow);
517
518     m_namedFlow->dispatchRegionLayoutUpdateEvent();
519 }
520
521 void RenderNamedFlowThread::regionOversetChangeEventTimerFired(Timer<RenderNamedFlowThread>*)
522 {
523     ASSERT(m_namedFlow);
524     
525     m_namedFlow->dispatchRegionOversetChangeEvent();
526 }
527
528 void RenderNamedFlowThread::setMarkForDestruction()
529 {
530     if (m_namedFlow->flowState() == WebKitNamedFlow::FlowStateNull)
531         return;
532
533     m_namedFlow->setRenderer(0);
534     // After this call ends, the renderer can be safely destroyed.
535     // 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.
536 }
537
538 void RenderNamedFlowThread::resetMarkForDestruction()
539 {
540     if (m_namedFlow->flowState() == WebKitNamedFlow::FlowStateCreated)
541         return;
542
543     m_namedFlow->setRenderer(this);
544 }
545
546 bool RenderNamedFlowThread::isMarkedForDestruction() const
547 {
548     // Flow threads in the "NULL" state can be destroyed.
549     return m_namedFlow->flowState() == WebKitNamedFlow::FlowStateNull;
550 }
551
552 static bool isContainedInNodes(Vector<Node*> others, Node* node)
553 {
554     for (size_t i = 0; i < others.size(); i++) {
555         Node* other = others.at(i);
556         if (other->contains(node))
557             return true;
558     }
559     return false;
560 }
561
562 static bool boxIntersectsRegion(LayoutUnit logicalTopForBox, LayoutUnit logicalBottomForBox, LayoutUnit logicalTopForRegion, LayoutUnit logicalBottomForRegion)
563 {
564     bool regionIsEmpty = logicalBottomForRegion != LayoutUnit::max() && logicalTopForRegion != LayoutUnit::min()
565         && (logicalBottomForRegion - logicalTopForRegion) <= 0;
566     return  (logicalBottomForBox - logicalTopForBox) > 0
567         && !regionIsEmpty
568         && logicalTopForBox < logicalBottomForRegion && logicalTopForRegion < logicalBottomForBox;
569 }
570
571 // Retrieve the next node to be visited while computing the ranges inside a region.
572 static Node* nextNodeInsideContentNode(const Node* currNode, const Node* contentNode)
573 {
574     ASSERT(currNode);
575     ASSERT(contentNode && contentNode->inNamedFlow());
576
577 #if ENABLE(SVG)
578     if (currNode->renderer() && currNode->renderer()->isSVGRoot())
579         return NodeTraversal::nextSkippingChildren(currNode, contentNode);
580 #endif
581     return NodeTraversal::next(currNode, contentNode);
582 }
583
584 void RenderNamedFlowThread::getRanges(Vector<RefPtr<Range> >& rangeObjects, const RenderRegion* region) const
585 {
586     LayoutUnit logicalTopForRegion;
587     LayoutUnit logicalBottomForRegion;
588
589     // extend the first region top to contain everything up to its logical height
590     if (region->isFirstRegion())
591         logicalTopForRegion = LayoutUnit::min();
592     else
593         logicalTopForRegion =  region->logicalTopForFlowThreadContent();
594
595     // extend the last region to contain everything above its y()
596     if (region->isLastRegion())
597         logicalBottomForRegion = LayoutUnit::max();
598     else
599         logicalBottomForRegion = region->logicalBottomForFlowThreadContent();
600
601     Vector<Node*> nodes;
602     // eliminate the contentNodes that are descendants of other contentNodes
603     for (NamedFlowContentNodes::const_iterator it = contentNodes().begin(); it != contentNodes().end(); ++it) {
604         Node* node = *it;
605         if (!isContainedInNodes(nodes, node))
606             nodes.append(node);
607     }
608
609     for (size_t i = 0; i < nodes.size(); i++) {
610         Node* contentNode = nodes.at(i);
611         if (!contentNode->renderer())
612             continue;
613
614         RefPtr<Range> range = Range::create(&contentNode->document());
615         bool foundStartPosition = false;
616         bool startsAboveRegion = true;
617         bool endsBelowRegion = true;
618         bool skipOverOutsideNodes = false;
619         Node* lastEndNode = 0;
620
621         for (Node* node = contentNode; node; node = nextNodeInsideContentNode(node, contentNode)) {
622             RenderObject* renderer = node->renderer();
623             if (!renderer)
624                 continue;
625
626             LayoutRect boundingBox;
627             if (renderer->isRenderInline())
628                 boundingBox = toRenderInline(renderer)->linesBoundingBox();
629             else if (renderer->isText())
630                 boundingBox = toRenderText(renderer)->linesBoundingBox();
631             else {
632                 boundingBox =  toRenderBox(renderer)->frameRect();
633                 if (toRenderBox(renderer)->isRelPositioned())
634                     boundingBox.move(toRenderBox(renderer)->relativePositionLogicalOffset());
635             }
636
637             LayoutUnit offsetTop = renderer->containingBlock()->offsetFromLogicalTopOfFirstPage();
638             const LayoutPoint logicalOffsetFromTop(isHorizontalWritingMode() ? LayoutUnit() :  offsetTop,
639                 isHorizontalWritingMode() ? offsetTop : LayoutUnit());
640
641             boundingBox.moveBy(logicalOffsetFromTop);
642
643             LayoutUnit logicalTopForRenderer = region->logicalTopOfFlowThreadContentRect(boundingBox);
644             LayoutUnit logicalBottomForRenderer = region->logicalBottomOfFlowThreadContentRect(boundingBox);
645
646             // if the bounding box of the current element doesn't intersect the region box
647             // close the current range only if the start element began inside the region,
648             // otherwise just move the start position after this node and keep skipping them until we found a proper start position.
649             if (!boxIntersectsRegion(logicalTopForRenderer, logicalBottomForRenderer, logicalTopForRegion, logicalBottomForRegion)) {
650                 if (foundStartPosition) {
651                     if (!startsAboveRegion) {
652                         if (range->intersectsNode(node, IGNORE_EXCEPTION))
653                             range->setEndBefore(node, IGNORE_EXCEPTION);
654                         rangeObjects.append(range->cloneRange(IGNORE_EXCEPTION));
655                         range = Range::create(&contentNode->document());
656                         startsAboveRegion = true;
657                     } else
658                         skipOverOutsideNodes = true;
659                 }
660                 if (skipOverOutsideNodes)
661                     range->setStartAfter(node, IGNORE_EXCEPTION);
662                 foundStartPosition = false;
663                 continue;
664             }
665
666             // start position
667             if (logicalTopForRenderer < logicalTopForRegion && startsAboveRegion) {
668                 if (renderer->isText()) { // Text crosses region top
669                     // for Text elements, just find the last textbox that is contained inside the region and use its start() offset as start position
670                     RenderText* textRenderer = toRenderText(renderer);
671                     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
672                         if (offsetTop + box->logicalBottom() < logicalTopForRegion)
673                             continue;
674                         range->setStart(Position(toText(node), box->start()));
675                         startsAboveRegion = false;
676                         break;
677                     }
678                 } else { // node crosses region top
679                     // for all elements, except Text, just set the start position to be before their children
680                     startsAboveRegion = true;
681                     range->setStart(Position(node, Position::PositionIsBeforeChildren));
682                 }
683             } else { // node starts inside region
684                 // 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
685                 // the range is closed.
686                 if (startsAboveRegion) {
687                     startsAboveRegion = false;
688                     range->setStartBefore(node, IGNORE_EXCEPTION);
689                 }
690             }
691             skipOverOutsideNodes  = false;
692             foundStartPosition = true;
693
694             // end position
695             if (logicalBottomForRegion < logicalBottomForRenderer && (endsBelowRegion || (!endsBelowRegion && !node->isDescendantOf(lastEndNode)))) {
696                 // 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
697                 if (renderer->isText()) { // Text crosses region bottom
698                     RenderText* textRenderer = toRenderText(renderer);
699                     InlineTextBox* lastBox = 0;
700                     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
701                         if ((offsetTop + box->logicalTop()) < logicalBottomForRegion) {
702                             lastBox = box;
703                             continue;
704                         }
705                         ASSERT(lastBox);
706                         if (lastBox)
707                             range->setEnd(Position(toText(node), lastBox->start() + lastBox->len()));
708                         break;
709                     }
710                     endsBelowRegion = false;
711                     lastEndNode = node;
712                 } else { // node crosses region bottom
713                     // for all elements, except Text, just set the start position to be after their children
714                     range->setEnd(Position(node, Position::PositionIsAfterChildren));
715                     endsBelowRegion = true;
716                     lastEndNode = node;
717                 }
718             } else { // node ends inside region
719                 // for elements that ends inside the region, set the end position to be after them
720                 // allow this end position to be changed only by other elements that are not descendants of the current end node
721                 if (endsBelowRegion || (!endsBelowRegion && !node->isDescendantOf(lastEndNode))) {
722                     range->setEndAfter(node, IGNORE_EXCEPTION);
723                     endsBelowRegion = false;
724                     lastEndNode = node;
725                 }
726             }
727         }
728         if (foundStartPosition || skipOverOutsideNodes)
729             rangeObjects.append(range);
730     }
731 }
732
733 }