2 * Copyright (C) Research In Motion Limited 2010. All rights reserved.
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.
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.
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.
21 #include "SVGResourcesCycleSolver.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"
34 // Set to truthy value to debug the resource cache.
35 #define DEBUG_CYCLE_DETECTION 0
37 #if DEBUG_CYCLE_DETECTION
38 #define LOG_DEBUG_CYCLE(...) LOG(SVG, __VA_ARGS__)
40 #define LOG_DEBUG_CYCLE(...) ((void)0)
45 SVGResourcesCycleSolver::SVGResourcesCycleSolver(RenderElement& renderer, SVGResources& resources)
46 : m_renderer(renderer)
47 , m_resources(resources)
51 SVGResourcesCycleSolver::~SVGResourcesCycleSolver()
55 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderElement& renderer) const
57 LOG_DEBUG_CYCLE("\n(%p) Check for cycles\n", &renderer);
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);
66 LOG_DEBUG_CYCLE("(%p) Examine our cached resources\n", &renderer);
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))
74 // Now check if the resources themselves contain cycles.
75 if (resourceContainsCycles(*resource))
80 LOG_DEBUG_CYCLE("(%p) Now the children renderers\n", &renderer);
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)) {
87 LOG_DEBUG_CYCLE("(%p) Checking child %p\n", &renderer, &child);
89 if (auto* childResources = SVGResourcesCache::cachedResourcesForRenderer(child)) {
91 LOG_DEBUG_CYCLE("(%p) Child %p had cached resources. Check them.\n", &renderer, &child);
93 // A child of the given 'resource' contains resources.
94 HashSet<RenderSVGResourceContainer*> childResourceSet;
95 childResources->buildSetOfResources(childResourceSet);
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))
105 LOG_DEBUG_CYCLE("(%p) Recurse into child %p\n", &renderer, &child);
107 // Walk children recursively, stop immediately if we found a cycle
108 if (resourceContainsCycles(child))
111 LOG_DEBUG_CYCLE("\n(%p) Child %p was ok\n", &renderer, &child);
114 LOG_DEBUG_CYCLE("\n(%p) No cycles found\n", &renderer);
119 void SVGResourcesCycleSolver::resolveCycles()
121 ASSERT(m_allResources.isEmpty());
123 #if DEBUG_CYCLE_DETECTION
124 LOG_DEBUG_CYCLE("\nBefore cycle detection:\n");
125 m_resources.dump(&m_renderer);
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());
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);
138 #if DEBUG_CYCLE_DETECTION
139 LOG_DEBUG_CYCLE("\nDetecting whether any resources references any of following objects:\n");
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());
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());
151 // Build combined set of local and parent resources.
152 m_allResources = localResources;
153 for (auto* resource : ancestorResources)
154 m_allResources.add(resource);
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));
160 ASSERT(!m_allResources.isEmpty());
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);
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);
177 #if DEBUG_CYCLE_DETECTION
178 LOG_DEBUG_CYCLE("\nAfter cycle detection:\n");
179 m_resources.dump(&m_renderer);
182 m_allResources.clear();
185 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer& resourceLeadingToCycle)
187 if (&resourceLeadingToCycle == m_resources.linkedResource()) {
188 m_resources.resetLinkedResource();
192 switch (resourceLeadingToCycle.resourceType()) {
193 case MaskerResourceType:
194 ASSERT(&resourceLeadingToCycle == m_resources.masker());
195 m_resources.resetMasker();
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();
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();
215 case FilterResourceType:
216 ASSERT(&resourceLeadingToCycle == m_resources.filter());
217 m_resources.resetFilter();
219 case ClipperResourceType:
220 ASSERT(&resourceLeadingToCycle == m_resources.clipper());
221 m_resources.resetClipper();
223 case SolidColorResourceType:
224 ASSERT_NOT_REACHED();