dab5d7b21e7ae9f0dd9c00a587402ada1ac7fc04
[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 "RenderRegion.h"
30 #include "RenderView.h"
31 #include "WebKitNamedFlow.h"
32
33 namespace WebCore {
34
35 RenderNamedFlowThread::RenderNamedFlowThread(Node* node, const AtomicString& name)
36     : RenderFlowThread(node)
37     , m_flowThreadName(name)
38 {
39 }
40
41 const char* RenderNamedFlowThread::renderName() const
42 {    
43     return "RenderNamedFlowThread";
44 }
45
46
47 RenderObject* RenderNamedFlowThread::nextRendererForNode(Node* node) const
48 {
49     FlowThreadChildList::const_iterator it = m_flowThreadChildList.begin();
50     FlowThreadChildList::const_iterator end = m_flowThreadChildList.end();
51     
52     for (; it != end; ++it) {
53         RenderObject* child = *it;
54         ASSERT(child->node());
55         unsigned short position = node->compareDocumentPosition(child->node());
56         if (position & Node::DOCUMENT_POSITION_FOLLOWING)
57             return child;
58     }
59     
60     return 0;
61 }
62
63 RenderObject* RenderNamedFlowThread::previousRendererForNode(Node* node) const
64 {
65     if (m_flowThreadChildList.isEmpty())
66         return 0;
67     
68     FlowThreadChildList::const_iterator begin = m_flowThreadChildList.begin();
69     FlowThreadChildList::const_iterator end = m_flowThreadChildList.end();
70     FlowThreadChildList::const_iterator it = end;
71     
72     do {
73         --it;
74         RenderObject* child = *it;
75         ASSERT(child->node());
76         unsigned short position = node->compareDocumentPosition(child->node());
77         if (position & Node::DOCUMENT_POSITION_PRECEDING)
78             return child;
79     } while (it != begin);
80     
81     return 0;
82 }
83
84 void RenderNamedFlowThread::addFlowChild(RenderObject* newChild, RenderObject* beforeChild)
85 {
86     // The child list is used to sort the flow thread's children render objects 
87     // based on their corresponding nodes DOM order. The list is needed to avoid searching the whole DOM.
88
89     // Do not add anonymous objects.
90     if (!newChild->node())
91         return;
92
93     if (beforeChild)
94         m_flowThreadChildList.insertBefore(beforeChild, newChild);
95     else
96         m_flowThreadChildList.add(newChild);
97 }
98
99 void RenderNamedFlowThread::removeFlowChild(RenderObject* child)
100 {
101     m_flowThreadChildList.remove(child);
102 }
103
104 bool RenderNamedFlowThread::dependsOn(RenderNamedFlowThread* otherRenderFlowThread) const
105 {
106     if (m_layoutBeforeThreadsSet.contains(otherRenderFlowThread))
107         return true;
108
109     // Recursively traverse the m_layoutBeforeThreadsSet.
110     RenderNamedFlowThreadCountedSet::const_iterator iterator = m_layoutBeforeThreadsSet.begin();
111     RenderNamedFlowThreadCountedSet::const_iterator end = m_layoutBeforeThreadsSet.end();
112     for (; iterator != end; ++iterator) {
113         const RenderNamedFlowThread* beforeFlowThread = (*iterator).first;
114         if (beforeFlowThread->dependsOn(otherRenderFlowThread))
115             return true;
116     }
117
118     return false;
119 }
120
121 // Compare two regions to determine in which one the content should flow first.
122 // The function returns true if the first passed region is "less" than the second passed region.
123 // If the first region appears before second region in DOM,
124 // the first region is "less" than the second region.
125 // If the first region is "less" than the second region, the first region receives content before second region.
126 static bool compareRenderRegions(const RenderRegion* firstRegion, const RenderRegion* secondRegion)
127 {
128     ASSERT(firstRegion);
129     ASSERT(secondRegion);
130
131     // If the regions have the same region-index, compare their position in dom.
132     ASSERT(firstRegion->node());
133     ASSERT(secondRegion->node());
134
135     unsigned short position = firstRegion->node()->compareDocumentPosition(secondRegion->node());
136     return (position & Node::DOCUMENT_POSITION_FOLLOWING);
137 }
138
139 void RenderNamedFlowThread::addRegionToThread(RenderRegion* renderRegion)
140 {
141     ASSERT(renderRegion);
142     if (m_regionList.isEmpty())
143         m_regionList.add(renderRegion);
144     else {
145         // Find the first region "greater" than renderRegion.
146         RenderRegionList::iterator it = m_regionList.begin();
147         while (it != m_regionList.end() && !compareRenderRegions(renderRegion, *it))
148             ++it;
149         m_regionList.insertBefore(it, renderRegion);
150     }
151
152     ASSERT(!renderRegion->isValid());
153     if (renderRegion->parentNamedFlowThread()) {
154         if (renderRegion->parentNamedFlowThread()->dependsOn(this)) {
155             // Register ourself to get a notification when the state changes.
156             renderRegion->parentNamedFlowThread()->m_observerThreadsSet.add(this);
157             return;
158         }
159
160         addDependencyOnFlowThread(renderRegion->parentNamedFlowThread());
161     }
162
163     renderRegion->setIsValid(true);
164
165     invalidateRegions();
166 }
167
168 void RenderNamedFlowThread::removeRegionFromThread(RenderRegion* renderRegion)
169 {
170     ASSERT(renderRegion);
171     m_regionRangeMap.clear();
172     m_regionList.remove(renderRegion);
173
174     if (renderRegion->parentNamedFlowThread()) {
175         if (!renderRegion->isValid()) {
176             renderRegion->parentNamedFlowThread()->m_observerThreadsSet.remove(this);
177             // No need to invalidate the regions rectangles. The removed region
178             // was not taken into account. Just return here.
179             return;
180         }
181         removeDependencyOnFlowThread(renderRegion->parentNamedFlowThread());
182     }
183     
184     invalidateRegions();
185 }
186
187
188 void RenderNamedFlowThread::checkInvalidRegions()
189 {
190     for (RenderRegionList::iterator iter = m_regionList.begin(); iter != m_regionList.end(); ++iter) {
191         RenderRegion* region = *iter;
192         // The only reason a region would be invalid is because it has a parent flow thread.
193         ASSERT(region->isValid() || region->parentNamedFlowThread());
194         if (region->isValid() || region->parentNamedFlowThread()->dependsOn(this))
195             continue;
196
197         region->parentNamedFlowThread()->m_observerThreadsSet.remove(this);
198         addDependencyOnFlowThread(region->parentNamedFlowThread());
199         region->setIsValid(true);
200         invalidateRegions();
201     }
202
203     if (m_observerThreadsSet.isEmpty())
204         return;
205
206     // Notify all the flow threads that were dependent on this flow.
207
208     // Create a copy of the list first. That's because observers might change the list when calling checkInvalidRegions.
209     Vector<RenderNamedFlowThread*> observers;
210     copyToVector(m_observerThreadsSet, observers);
211
212     for (size_t i = 0; i < observers.size(); ++i) {
213         RenderNamedFlowThread* flowThread = observers.at(i);
214         flowThread->checkInvalidRegions();
215     }
216 }
217
218 void RenderNamedFlowThread::addDependencyOnFlowThread(RenderNamedFlowThread* otherFlowThread)
219 {
220     RenderNamedFlowThreadCountedSet::AddResult result = m_layoutBeforeThreadsSet.add(otherFlowThread);
221     if (result.isNewEntry) {
222         // This is the first time we see this dependency. Make sure we recalculate all the dependencies.
223         view()->setIsRenderNamedFlowThreadOrderDirty(true);
224     }
225 }
226
227 void RenderNamedFlowThread::removeDependencyOnFlowThread(RenderNamedFlowThread* otherFlowThread)
228 {
229     bool removed = m_layoutBeforeThreadsSet.remove(otherFlowThread);
230     if (removed) {
231         checkInvalidRegions();
232         view()->setIsRenderNamedFlowThreadOrderDirty(true);
233     }
234 }
235
236 void RenderNamedFlowThread::pushDependencies(RenderNamedFlowThreadList& list)
237 {
238     for (RenderNamedFlowThreadCountedSet::iterator iter = m_layoutBeforeThreadsSet.begin(); iter != m_layoutBeforeThreadsSet.end(); ++iter) {
239         RenderNamedFlowThread* flowThread = (*iter).first;
240         if (list.contains(flowThread))
241             continue;
242         flowThread->pushDependencies(list);
243         list.add(flowThread);
244     }
245 }
246
247 WebKitNamedFlow* RenderNamedFlowThread::ensureNamedFlow()
248 {
249     if (!m_namedFlow)
250         m_namedFlow = WebKitNamedFlow::create(this);
251
252     return m_namedFlow.get();
253 }
254
255 }