Use "= default" to denote default constructor or destructor
[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() = default;
52
53 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderElement& renderer) const
54 {
55     LOG_DEBUG_CYCLE("\n(%p) Check for cycles\n", &renderer);
56
57     // First operate on the resources of the given renderer.
58     // <marker id="a"> <path marker-start="url(#b)"/> ...
59     // <marker id="b" marker-start="url(#a)"/>
60     if (auto* resources = SVGResourcesCache::cachedResourcesForRenderer(renderer)) {
61         HashSet<RenderSVGResourceContainer*> resourceSet;
62         resources->buildSetOfResources(resourceSet);
63
64         LOG_DEBUG_CYCLE("(%p) Examine our cached resources\n", &renderer);
65
66         // Walk all resources and check whether they reference any resource contained in the resources set.
67         for (auto* resource : resourceSet) {
68             LOG_DEBUG_CYCLE("(%p) Check %p\n", &renderer, resource);
69             if (m_allResources.contains(resource))
70                 return true;
71
72             // Now check if the resources themselves contain cycles.
73             if (resourceContainsCycles(*resource))
74                 return true;
75         }
76     }
77
78     LOG_DEBUG_CYCLE("(%p) Now the children renderers\n", &renderer);
79
80     // Then operate on the child resources of the given renderer.
81     // <marker id="a"> <path marker-start="url(#b)"/> ...
82     // <marker id="b"> <path marker-start="url(#a)"/> ...
83     for (auto& child : childrenOfType<RenderElement>(renderer)) {
84
85         LOG_DEBUG_CYCLE("(%p) Checking child %p\n", &renderer, &child);
86
87         if (auto* childResources = SVGResourcesCache::cachedResourcesForRenderer(child)) {
88
89             LOG_DEBUG_CYCLE("(%p) Child %p had cached resources. Check them.\n", &renderer, &child);
90
91             // A child of the given 'resource' contains resources.
92             HashSet<RenderSVGResourceContainer*> childResourceSet;
93             childResources->buildSetOfResources(childResourceSet);
94
95             // Walk all child resources and check whether they reference any resource contained in the resources set.
96             for (auto* resource : childResourceSet) {
97                 LOG_DEBUG_CYCLE("(%p) Child %p had resource %p\n", &renderer, &child, resource);
98                 if (m_allResources.contains(resource))
99                     return true;
100             }
101         }
102
103         LOG_DEBUG_CYCLE("(%p) Recurse into child %p\n", &renderer, &child);
104
105         // Walk children recursively, stop immediately if we found a cycle
106         if (resourceContainsCycles(child))
107             return true;
108
109         LOG_DEBUG_CYCLE("\n(%p) Child %p was ok\n", &renderer, &child);
110     }
111
112     LOG_DEBUG_CYCLE("\n(%p) No cycles found\n", &renderer);
113
114     return false;
115 }
116
117 void SVGResourcesCycleSolver::resolveCycles()
118 {
119     ASSERT(m_allResources.isEmpty());
120
121 #if DEBUG_CYCLE_DETECTION
122     LOG_DEBUG_CYCLE("\nBefore cycle detection:\n");
123     m_resources.dump(&m_renderer);
124 #endif
125
126     // Stash all resources into a HashSet for the ease of traversing.
127     HashSet<RenderSVGResourceContainer*> localResources;
128     m_resources.buildSetOfResources(localResources);
129     ASSERT(!localResources.isEmpty());
130
131     // Add all parent resource containers to the HashSet.
132     HashSet<RenderSVGResourceContainer*> ancestorResources;
133     for (auto& resource : ancestorsOfType<RenderSVGResourceContainer>(m_renderer))
134         ancestorResources.add(&resource);
135
136 #if DEBUG_CYCLE_DETECTION
137     LOG_DEBUG_CYCLE("\nDetecting whether any resources references any of following objects:\n");
138     {
139         LOG_DEBUG_CYCLE("Local resources:\n");
140         for (RenderObject* resource : localResources)
141             LOG_DEBUG_CYCLE("|> %s : %p (node %p)\n", resource->renderName(), resource, resource->node());
142
143         fprintf(stderr, "Parent resources:\n");
144         for (RenderObject* resource : ancestorResources)
145             LOG_DEBUG_CYCLE("|> %s : %p (node %p)\n", resource->renderName(), resource, resource->node());
146     }
147 #endif
148
149     // Build combined set of local and parent resources.
150     m_allResources = localResources;
151     for (auto* resource : ancestorResources)
152         m_allResources.add(resource);
153
154     // If we're a resource, add ourselves to the HashSet.
155     if (is<RenderSVGResourceContainer>(m_renderer))
156         m_allResources.add(&downcast<RenderSVGResourceContainer>(m_renderer));
157
158     ASSERT(!m_allResources.isEmpty());
159
160 #if DEBUG_CYCLE_DETECTION
161     LOG_DEBUG_CYCLE("\nAll resources:\n");
162     for (auto* resource : m_allResources)
163         LOG_DEBUG_CYCLE("- %p\n", resource);
164 #endif
165
166     // The job of this function is to determine wheter any of the 'resources' associated with the given 'renderer'
167     // references us (or whether any of its kids references us) -> that's a cycle, we need to find and break it.
168     for (auto* resource : localResources) {
169         if (ancestorResources.contains(resource) || resourceContainsCycles(*resource)) {
170             LOG_DEBUG_CYCLE("\n**** Detected a cycle (see the last test in the output above) ****\n");
171             breakCycle(*resource);
172         }
173     }
174
175 #if DEBUG_CYCLE_DETECTION
176     LOG_DEBUG_CYCLE("\nAfter cycle detection:\n");
177     m_resources.dump(&m_renderer);
178 #endif
179
180     m_allResources.clear();
181 }
182
183 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer& resourceLeadingToCycle)
184 {
185     if (&resourceLeadingToCycle == m_resources.linkedResource()) {
186         m_resources.resetLinkedResource();
187         return;
188     }
189
190     switch (resourceLeadingToCycle.resourceType()) {
191     case MaskerResourceType:
192         ASSERT(&resourceLeadingToCycle == m_resources.masker());
193         m_resources.resetMasker();
194         break;
195     case MarkerResourceType:
196         ASSERT(&resourceLeadingToCycle == m_resources.markerStart() || &resourceLeadingToCycle == m_resources.markerMid() || &resourceLeadingToCycle == m_resources.markerEnd());
197         if (m_resources.markerStart() == &resourceLeadingToCycle)
198             m_resources.resetMarkerStart();
199         if (m_resources.markerMid() == &resourceLeadingToCycle)
200             m_resources.resetMarkerMid();
201         if (m_resources.markerEnd() == &resourceLeadingToCycle)
202             m_resources.resetMarkerEnd();
203         break;
204     case PatternResourceType:
205     case LinearGradientResourceType:
206     case RadialGradientResourceType:
207         ASSERT(&resourceLeadingToCycle == m_resources.fill() || &resourceLeadingToCycle == m_resources.stroke());
208         if (m_resources.fill() == &resourceLeadingToCycle)
209             m_resources.resetFill();
210         if (m_resources.stroke() == &resourceLeadingToCycle)
211             m_resources.resetStroke();
212         break;
213     case FilterResourceType:
214         ASSERT(&resourceLeadingToCycle == m_resources.filter());
215         m_resources.resetFilter();
216         break;
217     case ClipperResourceType:
218         ASSERT(&resourceLeadingToCycle == m_resources.clipper());
219         m_resources.resetClipper();
220         break;
221     case SolidColorResourceType:
222         ASSERT_NOT_REACHED();
223         break;
224     }
225 }
226
227 }