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
43namespace WebCore {
44
45SVGResourcesCycleSolver::SVGResourcesCycleSolver(RenderElement& renderer, SVGResources& resources)
46 : m_renderer(renderer)
47 , m_resources(resources)
48{
49}
50
51SVGResourcesCycleSolver::~SVGResourcesCycleSolver() = default;
52
53bool 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
117void 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
183void 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}
228