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