Layer flashing and poor perf during scrolling of message list on gmail.com and hotmai...
[WebKit-https.git] / Source / WebCore / rendering / LayerOverlapMap.cpp
1 /*
2  * Copyright (C) 2019 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. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "LayerOverlapMap.h"
28 #include "RenderLayer.h"
29 #include <wtf/text/TextStream.h>
30
31 namespace WebCore {
32
33 struct RectList {
34     Vector<LayoutRect> rects;
35     LayoutRect boundingRect;
36     
37     void append(const LayoutRect& rect)
38     {
39         rects.append(rect);
40         boundingRect.unite(rect);
41     }
42
43     void append(const RectList& rectList)
44     {
45         rects.appendVector(rectList.rects);
46         boundingRect.unite(rectList.boundingRect);
47     }
48     
49     bool intersects(const LayoutRect& rect) const
50     {
51         if (!rects.size() || !rect.intersects(boundingRect))
52             return false;
53
54         for (const auto& currentRect : rects) {
55             if (currentRect.intersects(rect))
56                 return true;
57         }
58         return false;
59     }
60 };
61
62 static TextStream& operator<<(TextStream& ts, const RectList& rectList)
63 {
64     ts << "bounds " << rectList.boundingRect << " (" << rectList.rects << " rects)";
65     return ts;
66 }
67
68 // Used to store overlap rects in a way that takes overflow into account.
69 // It stores a tree whose nodes are layers with composited scrolling. The tree is built lazily as layers are added whose containing block
70 // chains contain composited scrollers. The tree always starts at the root layer.
71 // Checking for overlap involves finding the node for the clipping layer enclosing the given layer (or the root),
72 // and comparing against the bounds of earlier siblings.
73 class OverlapMapContainer {
74 public:
75     OverlapMapContainer(const RenderLayer& rootLayer)
76         : m_rootScope(rootLayer)
77     {
78     }
79
80     // Layers are added in z-order, lazily creating clipping scopes as necessary.
81     void add(const RenderLayer&, const LayoutRect& bounds, const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers);
82     bool overlapsLayers(const RenderLayer&, const LayoutRect& bounds, const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers) const;
83     void append(std::unique_ptr<OverlapMapContainer>&&);
84     
85     String dump(unsigned) const;
86
87 private:
88     struct ClippingScope {
89         ClippingScope(const RenderLayer& inLayer)
90             : layer(inLayer)
91         {
92         }
93
94         ClippingScope(const LayerOverlapMap::LayerAndBounds& layerAndBounds)
95             : layer(layerAndBounds.layer)
96             , bounds(layerAndBounds.bounds)
97         {
98         }
99
100         ClippingScope* childWithLayer(const RenderLayer& layer) const
101         {
102             for (auto& child : children) {
103                 if (&child.layer == &layer)
104                     return const_cast<ClippingScope*>(&child);
105             }
106             return nullptr;
107         }
108
109         ClippingScope* addChildWithLayerAndBounds(const LayerOverlapMap::LayerAndBounds& layerAndBounds)
110         {
111             children.append({ layerAndBounds });
112             return &children.last();
113         }
114
115         ClippingScope* addChild(const ClippingScope& child)
116         {
117             children.append(child);
118             return &children.last();
119         }
120
121         void appendRect(const LayoutRect& bounds)
122         {
123             rectList.append(bounds);
124         }
125
126         const RenderLayer& layer;
127         LayoutRect bounds; // Bounds of the composited clip.
128         Vector<ClippingScope> children;
129         RectList rectList;
130     };
131
132     static ClippingScope* clippingScopeContainingLayerChildRecursive(const ClippingScope& currNode, const RenderLayer& layer)
133     {
134         for (auto& child : currNode.children) {
135             if (&layer == &child.layer)
136                 return const_cast<ClippingScope*>(&currNode);
137
138             if (auto* foundNode = clippingScopeContainingLayerChildRecursive(child, layer))
139                 return foundNode;
140         }
141
142         return nullptr;
143     }
144
145     ClippingScope* scopeContainingLayer(const RenderLayer& layer) const
146     {
147         return clippingScopeContainingLayerChildRecursive(m_rootScope, layer);
148     }
149     
150     static void mergeClippingScopesRecursive(const ClippingScope& sourceScope, ClippingScope& destScope);
151
152     ClippingScope* ensureClippingScopeForLayers(const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers);
153     ClippingScope* findClippingScopeForLayers(const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers) const;
154
155     void recursiveOutputToStream(TextStream&, const ClippingScope&, unsigned depth) const;
156
157     const ClippingScope& rootScope() const { return m_rootScope; }
158     ClippingScope& rootScope() { return m_rootScope; }
159
160     ClippingScope m_rootScope;
161 };
162
163 void OverlapMapContainer::add(const RenderLayer&, const LayoutRect& bounds, const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers)
164 {
165     auto* layerScope = ensureClippingScopeForLayers(enclosingClippingLayers);
166     layerScope->appendRect(bounds);
167 }
168
169 bool OverlapMapContainer::overlapsLayers(const RenderLayer&, const LayoutRect& bounds, const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers) const
170 {
171     if (m_rootScope.rectList.intersects(bounds))
172         return true;
173
174     if (m_rootScope.children.isEmpty())
175         return false;
176
177     // Find the ClippingScope for which this layer is a child.
178     auto* clippingScope = findClippingScopeForLayers(enclosingClippingLayers);
179     if (!clippingScope)
180         return false;
181
182     if (clippingScope->rectList.intersects(bounds))
183         return true;
184
185     // FIXME: In some cases do we have to walk up the ancestor clipping scope chain?
186     return false;
187 }
188
189 void OverlapMapContainer::mergeClippingScopesRecursive(const ClippingScope& sourceScope, ClippingScope& destScope)
190 {
191     ASSERT(&sourceScope.layer == &destScope.layer);
192     destScope.rectList.append(sourceScope.rectList);
193
194     for (auto& sourceChildScope : sourceScope.children) {
195         ClippingScope* destChild = destScope.childWithLayer(sourceChildScope.layer);
196         if (destChild) {
197             destChild->rectList.append(sourceChildScope.rectList);
198             mergeClippingScopesRecursive(sourceChildScope, *destChild);
199         } else {
200             // New child, just copy the whole subtree.
201             destScope.addChild(sourceScope);
202         }
203     }
204 }
205
206 void OverlapMapContainer::append(std::unique_ptr<OverlapMapContainer>&& otherContainer)
207 {
208     mergeClippingScopesRecursive(otherContainer->rootScope(), m_rootScope);
209 }
210
211 OverlapMapContainer::ClippingScope* OverlapMapContainer::ensureClippingScopeForLayers(const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers)
212 {
213     ASSERT(enclosingClippingLayers.size());
214     ASSERT(enclosingClippingLayers[0].layer.isRenderViewLayer());
215
216     auto* currScope = &m_rootScope;
217     for (unsigned i = 1; i < enclosingClippingLayers.size(); ++i) {
218         auto& scopeLayerAndBounds = enclosingClippingLayers[i];
219         auto* childScope = currScope->childWithLayer(scopeLayerAndBounds.layer);
220         if (!childScope) {
221             currScope = currScope->addChildWithLayerAndBounds(scopeLayerAndBounds);
222             break;
223         }
224
225         currScope = childScope;
226     }
227
228     return const_cast<ClippingScope*>(currScope);
229 }
230
231 OverlapMapContainer::ClippingScope* OverlapMapContainer::findClippingScopeForLayers(const Vector<LayerOverlapMap::LayerAndBounds>& enclosingClippingLayers) const
232 {
233     ASSERT(enclosingClippingLayers.size());
234     ASSERT(enclosingClippingLayers[0].layer.isRenderViewLayer());
235
236     const auto* currScope = &m_rootScope;
237     for (unsigned i = 1; i < enclosingClippingLayers.size(); ++i) {
238         auto& scopeLayerAndBounds = enclosingClippingLayers[i];
239         auto* childScope = currScope->childWithLayer(scopeLayerAndBounds.layer);
240         if (!childScope)
241             return nullptr;
242
243         currScope = childScope;
244     }
245
246     return const_cast<ClippingScope*>(currScope);
247 }
248
249 void OverlapMapContainer::recursiveOutputToStream(TextStream& ts, const ClippingScope& scope, unsigned depth) const
250 {
251     ts << "\n" << indent << TextStream::Repeat { 2 * depth, ' ' } << " scope for layer " << &scope.layer << " rects " << scope.rectList;
252     for (auto& childScope : scope.children)
253         recursiveOutputToStream(ts, childScope, depth + 1);
254 }
255
256 String OverlapMapContainer::dump(unsigned indent) const
257 {
258     TextStream multilineStream;
259     multilineStream.increaseIndent(indent);
260     multilineStream << "overlap container - root scope layer " <<  &m_rootScope.layer << " rects " << m_rootScope.rectList;
261
262     for (auto& childScope : m_rootScope.children)
263         recursiveOutputToStream(multilineStream, childScope, 1);
264
265     return multilineStream.release();
266 }
267
268 LayerOverlapMap::LayerOverlapMap(const RenderLayer& rootLayer)
269     : m_geometryMap(UseTransforms)
270     , m_rootLayer(rootLayer)
271 {
272     // Begin assuming the root layer will be composited so that there is
273     // something on the stack. The root layer should also never get an
274     // popCompositingContainer call.
275     pushCompositingContainer();
276 }
277
278 LayerOverlapMap::~LayerOverlapMap() = default;
279
280 void LayerOverlapMap::add(const RenderLayer& layer, const LayoutRect& bounds, const Vector<LayerAndBounds>& enclosingClippingLayers)
281 {
282     // Layers do not contribute to overlap immediately--instead, they will
283     // contribute to overlap as soon as their composited ancestor has been
284     // recursively processed and popped off the stack.
285     ASSERT(m_overlapStack.size() >= 2);
286     m_overlapStack[m_overlapStack.size() - 2]->add(layer, bounds, enclosingClippingLayers);
287     
288     m_isEmpty = false;
289 }
290
291 bool LayerOverlapMap::overlapsLayers(const RenderLayer& layer, const LayoutRect& bounds, const Vector<LayerAndBounds>& enclosingClippingLayers) const
292 {
293     return m_overlapStack.last()->overlapsLayers(layer, bounds, enclosingClippingLayers);
294 }
295
296 void LayerOverlapMap::pushCompositingContainer()
297 {
298     m_overlapStack.append(std::make_unique<OverlapMapContainer>(m_rootLayer));
299 }
300
301 void LayerOverlapMap::popCompositingContainer()
302 {
303     m_overlapStack[m_overlapStack.size() - 2]->append(WTFMove(m_overlapStack.last()));
304     m_overlapStack.removeLast();
305 }
306
307 static TextStream& operator<<(TextStream& ts, const OverlapMapContainer& container)
308 {
309     ts << container.dump(ts.indent());
310     return ts;
311 }
312
313 TextStream& operator<<(TextStream& ts, const LayerOverlapMap& overlapMap)
314 {
315     TextStream multilineStream;
316
317     TextStream::GroupScope scope(ts);
318     multilineStream << "LayerOverlapMap\n";
319     multilineStream.increaseIndent(2);
320
321     bool needNewline = false;
322     for (auto& container : overlapMap.overlapStack()) {
323         if (needNewline)
324             multilineStream << "\n";
325         else
326             needNewline = true;
327         multilineStream << indent << *container;
328     }
329
330     ts << multilineStream.release();
331     return ts;
332 }
333
334 } // namespace WebCore
335