Multi-hop reference cycles not detected.
[WebKit-https.git] / Source / WebCore / rendering / svg / SVGResourcesCycleSolver.cpp
1 /*
2  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public License
15  * along with this library; see the file COPYING.LIB.  If not, write to
16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  * Boston, MA 02110-1301, USA.
18  */
19
20 #include "config.h"
21 #include "SVGResourcesCycleSolver.h"
22
23 #include "Logging.h"
24 #include "RenderAncestorIterator.h"
25 #include "RenderSVGResourceClipper.h"
26 #include "RenderSVGResourceFilter.h"
27 #include "RenderSVGResourceMarker.h"
28 #include "RenderSVGResourceMasker.h"
29 #include "SVGGradientElement.h"
30 #include "SVGPatternElement.h"
31 #include "SVGResources.h"
32 #include "SVGResourcesCache.h"
33
34 // Set to truthy value to debug the resource cache.
35 #define DEBUG_CYCLE_DETECTION 0
36
37 #if DEBUG_CYCLE_DETECTION
38 #define LOG_DEBUG_CYCLE(...) LOG(SVG, __VA_ARGS__)
39 #else
40 #define LOG_DEBUG_CYCLE(...) ((void)0)
41 #endif
42
43 namespace WebCore {
44
45 SVGResourcesCycleSolver::SVGResourcesCycleSolver(RenderElement& renderer, SVGResources& resources)
46     : m_renderer(renderer)
47     , m_resources(resources)
48 {
49 }
50
51 SVGResourcesCycleSolver::~SVGResourcesCycleSolver()
52 {
53 }
54
55 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderElement& renderer) const
56 {
57     LOG_DEBUG_CYCLE("\n(%p) Check for cycles\n", &renderer);
58
59     // First operate on the resources of the given renderer.
60     // <marker id="a"> <path marker-start="url(#b)"/> ...
61     // <marker id="b" marker-start="url(#a)"/>
62     if (auto* resources = SVGResourcesCache::cachedResourcesForRenderer(renderer)) {
63         HashSet<RenderSVGResourceContainer*> resourceSet;
64         resources->buildSetOfResources(resourceSet);
65
66         LOG_DEBUG_CYCLE("(%p) Examine our cached resources\n", &renderer);
67
68         // Walk all resources and check whether they reference any resource contained in the resources set.
69         for (auto* resource : resourceSet) {
70             LOG_DEBUG_CYCLE("(%p) Check %p\n", &renderer, resource);
71             if (m_allResources.contains(resource))
72                 return true;
73
74             // Now check if the resources themselves contain cycles.
75             if (resourceContainsCycles(*resource))
76                 return true;
77         }
78     }
79
80     LOG_DEBUG_CYCLE("(%p) Now the children renderers\n", &renderer);
81
82     // Then operate on the child resources of the given renderer.
83     // <marker id="a"> <path marker-start="url(#b)"/> ...
84     // <marker id="b"> <path marker-start="url(#a)"/> ...
85     for (auto& child : childrenOfType<RenderElement>(renderer)) {
86
87         LOG_DEBUG_CYCLE("(%p) Checking child %p\n", &renderer, &child);
88
89         if (auto* childResources = SVGResourcesCache::cachedResourcesForRenderer(child)) {
90
91             LOG_DEBUG_CYCLE("(%p) Child %p had cached resources. Check them.\n", &renderer, &child);
92
93             // A child of the given 'resource' contains resources.
94             HashSet<RenderSVGResourceContainer*> childResourceSet;
95             childResources->buildSetOfResources(childResourceSet);
96
97             // Walk all child resources and check whether they reference any resource contained in the resources set.
98             for (auto* resource : childResourceSet) {
99                 LOG_DEBUG_CYCLE("(%p) Child %p had resource %p\n", &renderer, &child, resource);
100                 if (m_allResources.contains(resource))
101                     return true;
102             }
103         }
104
105         LOG_DEBUG_CYCLE("(%p) Recurse into child %p\n", &renderer, &child);
106
107         // Walk children recursively, stop immediately if we found a cycle
108         if (resourceContainsCycles(child))
109             return true;
110
111         LOG_DEBUG_CYCLE("\n(%p) Child %p was ok\n", &renderer, &child);
112     }
113
114     LOG_DEBUG_CYCLE("\n(%p) No cycles found\n", &renderer);
115
116     return false;
117 }
118
119 void SVGResourcesCycleSolver::resolveCycles()
120 {
121     ASSERT(m_allResources.isEmpty());
122
123 #if DEBUG_CYCLE_DETECTION
124     LOG_DEBUG_CYCLE("\nBefore cycle detection:\n");
125     m_resources.dump(&m_renderer);
126 #endif
127
128     // Stash all resources into a HashSet for the ease of traversing.
129     HashSet<RenderSVGResourceContainer*> localResources;
130     m_resources.buildSetOfResources(localResources);
131     ASSERT(!localResources.isEmpty());
132
133     // Add all parent resource containers to the HashSet.
134     HashSet<RenderSVGResourceContainer*> ancestorResources;
135     for (auto& resource : ancestorsOfType<RenderSVGResourceContainer>(m_renderer))
136         ancestorResources.add(&resource);
137
138 #if DEBUG_CYCLE_DETECTION
139     LOG_DEBUG_CYCLE("\nDetecting whether any resources references any of following objects:\n");
140     {
141         LOG_DEBUG_CYCLE("Local resources:\n");
142         for (RenderObject* resource : localResources)
143             LOG_DEBUG_CYCLE("|> %s : %p (node %p)\n", resource->renderName(), resource, resource->node());
144
145         fprintf(stderr, "Parent resources:\n");
146         for (RenderObject* resource : ancestorResources)
147             LOG_DEBUG_CYCLE("|> %s : %p (node %p)\n", resource->renderName(), resource, resource->node());
148     }
149 #endif
150
151     // Build combined set of local and parent resources.
152     m_allResources = localResources;
153     for (auto* resource : ancestorResources)
154         m_allResources.add(resource);
155
156     // If we're a resource, add ourselves to the HashSet.
157     if (is<RenderSVGResourceContainer>(m_renderer))
158         m_allResources.add(&downcast<RenderSVGResourceContainer>(m_renderer));
159
160     ASSERT(!m_allResources.isEmpty());
161
162 #if DEBUG_CYCLE_DETECTION
163     LOG_DEBUG_CYCLE("\nAll resources:\n");
164     for (auto* resource : m_allResources)
165         LOG_DEBUG_CYCLE("- %p\n", resource);
166 #endif
167
168     // The job of this function is to determine wheter any of the 'resources' associated with the given 'renderer'
169     // references us (or whether any of its kids references us) -> that's a cycle, we need to find and break it.
170     for (auto* resource : localResources) {
171         if (ancestorResources.contains(resource) || resourceContainsCycles(*resource)) {
172             LOG_DEBUG_CYCLE("\n**** Detected a cycle (see the last test in the output above) ****\n");
173             breakCycle(*resource);
174         }
175     }
176
177 #if DEBUG_CYCLE_DETECTION
178     LOG_DEBUG_CYCLE("\nAfter cycle detection:\n");
179     m_resources.dump(&m_renderer);
180 #endif
181
182     m_allResources.clear();
183 }
184
185 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer& resourceLeadingToCycle)
186 {
187     if (&resourceLeadingToCycle == m_resources.linkedResource()) {
188         m_resources.resetLinkedResource();
189         return;
190     }
191
192     switch (resourceLeadingToCycle.resourceType()) {
193     case MaskerResourceType:
194         ASSERT(&resourceLeadingToCycle == m_resources.masker());
195         m_resources.resetMasker();
196         break;
197     case MarkerResourceType:
198         ASSERT(&resourceLeadingToCycle == m_resources.markerStart() || &resourceLeadingToCycle == m_resources.markerMid() || &resourceLeadingToCycle == m_resources.markerEnd());
199         if (m_resources.markerStart() == &resourceLeadingToCycle)
200             m_resources.resetMarkerStart();
201         if (m_resources.markerMid() == &resourceLeadingToCycle)
202             m_resources.resetMarkerMid();
203         if (m_resources.markerEnd() == &resourceLeadingToCycle)
204             m_resources.resetMarkerEnd();
205         break;
206     case PatternResourceType:
207     case LinearGradientResourceType:
208     case RadialGradientResourceType:
209         ASSERT(&resourceLeadingToCycle == m_resources.fill() || &resourceLeadingToCycle == m_resources.stroke());
210         if (m_resources.fill() == &resourceLeadingToCycle)
211             m_resources.resetFill();
212         if (m_resources.stroke() == &resourceLeadingToCycle)
213             m_resources.resetStroke();
214         break;
215     case FilterResourceType:
216         ASSERT(&resourceLeadingToCycle == m_resources.filter());
217         m_resources.resetFilter();
218         break;
219     case ClipperResourceType:
220         ASSERT(&resourceLeadingToCycle == m_resources.clipper());
221         m_resources.resetClipper();
222         break;
223     case SolidColorResourceType:
224         ASSERT_NOT_REACHED();
225         break;
226     }
227 }
228
229 }