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 "core/rendering/svg/SVGResourcesCycleSolver.h"
22
23 // Set to a value > 0, to debug the resource cache.
24 #define DEBUG_CYCLE_DETECTION 0
25
26 #include "core/rendering/svg/RenderSVGResourceClipper.h"
27 #include "core/rendering/svg/RenderSVGResourceFilter.h"
28 #include "core/rendering/svg/RenderSVGResourceMarker.h"
29 #include "core/rendering/svg/RenderSVGResourceMasker.h"
30 #include "core/rendering/svg/SVGResources.h"
31 #include "core/rendering/svg/SVGResourcesCache.h"
32 #include "core/svg/SVGFilterElement.h"
33 #include "core/svg/SVGGradientElement.h"
34 #include "core/svg/SVGPatternElement.h"
35
36 namespace WebCore {
37
SVGResourcesCycleSolver(RenderObject * renderer,SVGResources * resources)38 SVGResourcesCycleSolver::SVGResourcesCycleSolver(RenderObject* renderer, SVGResources* resources)
39 : m_renderer(renderer)
40 , m_resources(resources)
41 {
42 ASSERT(m_renderer);
43 ASSERT(m_resources);
44 }
45
~SVGResourcesCycleSolver()46 SVGResourcesCycleSolver::~SVGResourcesCycleSolver()
47 {
48 }
49
resourceContainsCycles(RenderObject * renderer) const50 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderObject* renderer) const
51 {
52 ASSERT(renderer);
53
54 // First operate on the resources of the given renderer.
55 // <marker id="a"> <path marker-start="url(#b)"/> ...
56 // <marker id="b" marker-start="url(#a)"/>
57 if (SVGResources* resources = SVGResourcesCache::cachedResourcesForRenderObject(renderer)) {
58 HashSet<RenderSVGResourceContainer*> resourceSet;
59 resources->buildSetOfResources(resourceSet);
60
61 // Walk all resources and check wheter they reference any resource contained in the resources set.
62 HashSet<RenderSVGResourceContainer*>::iterator end = resourceSet.end();
63 for (HashSet<RenderSVGResourceContainer*>::iterator it = resourceSet.begin(); it != end; ++it) {
64 if (m_allResources.contains(*it))
65 return true;
66 }
67 }
68
69 // Then operate on the child resources of the given renderer.
70 // <marker id="a"> <path marker-start="url(#b)"/> ...
71 // <marker id="b"> <path marker-start="url(#a)"/> ...
72 for (RenderObject* child = renderer->firstChild(); child; child = child->nextSibling()) {
73 SVGResources* childResources = SVGResourcesCache::cachedResourcesForRenderObject(child);
74 if (!childResources)
75 continue;
76
77 // A child of the given 'resource' contains resources.
78 HashSet<RenderSVGResourceContainer*> childSet;
79 childResources->buildSetOfResources(childSet);
80
81 // Walk all child resources and check wheter they reference any resource contained in the resources set.
82 HashSet<RenderSVGResourceContainer*>::iterator end = childSet.end();
83 for (HashSet<RenderSVGResourceContainer*>::iterator it = childSet.begin(); it != end; ++it) {
84 if (m_allResources.contains(*it))
85 return true;
86 }
87
88 // Walk children recursively, stop immediately if we found a cycle
89 if (resourceContainsCycles(child))
90 return true;
91 }
92
93 return false;
94 }
95
resolveCycles()96 void SVGResourcesCycleSolver::resolveCycles()
97 {
98 ASSERT(m_allResources.isEmpty());
99
100 #if DEBUG_CYCLE_DETECTION > 0
101 fprintf(stderr, "\nBefore cycle detection:\n");
102 m_resources->dump(m_renderer);
103 #endif
104
105 // Stash all resources into a HashSet for the ease of traversing.
106 HashSet<RenderSVGResourceContainer*> localResources;
107 m_resources->buildSetOfResources(localResources);
108 ASSERT(!localResources.isEmpty());
109
110 // Add all parent resource containers to the HashSet.
111 HashSet<RenderSVGResourceContainer*> parentResources;
112 RenderObject* parent = m_renderer->parent();
113 while (parent) {
114 if (parent->isSVGResourceContainer())
115 parentResources.add(toRenderSVGResourceContainer(parent));
116 parent = parent->parent();
117 }
118
119 #if DEBUG_CYCLE_DETECTION > 0
120 fprintf(stderr, "\nDetecting wheter any resources references any of following objects:\n");
121 {
122 fprintf(stderr, "Local resources:\n");
123 HashSet<RenderSVGResourceContainer*>::iterator end = localResources.end();
124 for (HashSet<RenderSVGResourceContainer*>::iterator it = localResources.begin(); it != end; ++it)
125 fprintf(stderr, "|> %s: object=%p (node=%p)\n", (*it)->renderName(), *it, (*it)->node());
126
127 fprintf(stderr, "Parent resources:\n");
128 end = parentResources.end();
129 for (HashSet<RenderSVGResourceContainer*>::iterator it = parentResources.begin(); it != end; ++it)
130 fprintf(stderr, "|> %s: object=%p (node=%p)\n", (*it)->renderName(), *it, (*it)->node());
131 }
132 #endif
133
134 // Build combined set of local and parent resources.
135 m_allResources = localResources;
136 HashSet<RenderSVGResourceContainer*>::iterator end = parentResources.end();
137 for (HashSet<RenderSVGResourceContainer*>::iterator it = parentResources.begin(); it != end; ++it)
138 m_allResources.add(*it);
139
140 // If we're a resource, add ourselves to the HashSet.
141 if (m_renderer->isSVGResourceContainer())
142 m_allResources.add(toRenderSVGResourceContainer(m_renderer));
143
144 ASSERT(!m_allResources.isEmpty());
145
146 // The job of this function is to determine wheter any of the 'resources' associated with the given 'renderer'
147 // references us (or wheter any of its kids references us) -> that's a cycle, we need to find and break it.
148 end = localResources.end();
149 for (HashSet<RenderSVGResourceContainer*>::iterator it = localResources.begin(); it != end; ++it) {
150 RenderSVGResourceContainer* resource = *it;
151 if (parentResources.contains(resource) || resourceContainsCycles(resource))
152 breakCycle(resource);
153 }
154
155 #if DEBUG_CYCLE_DETECTION > 0
156 fprintf(stderr, "\nAfter cycle detection:\n");
157 m_resources->dump(m_renderer);
158 #endif
159
160 m_allResources.clear();
161 }
162
breakCycle(RenderSVGResourceContainer * resourceLeadingToCycle)163 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer* resourceLeadingToCycle)
164 {
165 ASSERT(resourceLeadingToCycle);
166 if (resourceLeadingToCycle == m_resources->linkedResource()) {
167 m_resources->resetLinkedResource();
168 return;
169 }
170
171 switch (resourceLeadingToCycle->resourceType()) {
172 case MaskerResourceType:
173 ASSERT(resourceLeadingToCycle == m_resources->masker());
174 m_resources->resetMasker();
175 break;
176 case MarkerResourceType:
177 ASSERT(resourceLeadingToCycle == m_resources->markerStart() || resourceLeadingToCycle == m_resources->markerMid() || resourceLeadingToCycle == m_resources->markerEnd());
178 if (m_resources->markerStart() == resourceLeadingToCycle)
179 m_resources->resetMarkerStart();
180 if (m_resources->markerMid() == resourceLeadingToCycle)
181 m_resources->resetMarkerMid();
182 if (m_resources->markerEnd() == resourceLeadingToCycle)
183 m_resources->resetMarkerEnd();
184 break;
185 case PatternResourceType:
186 case LinearGradientResourceType:
187 case RadialGradientResourceType:
188 ASSERT(resourceLeadingToCycle == m_resources->fill() || resourceLeadingToCycle == m_resources->stroke());
189 if (m_resources->fill() == resourceLeadingToCycle)
190 m_resources->resetFill();
191 if (m_resources->stroke() == resourceLeadingToCycle)
192 m_resources->resetStroke();
193 break;
194 case FilterResourceType:
195 ASSERT(resourceLeadingToCycle == m_resources->filter());
196 m_resources->resetFilter();
197 break;
198 case ClipperResourceType:
199 ASSERT(resourceLeadingToCycle == m_resources->clipper());
200 m_resources->resetClipper();
201 break;
202 case SolidColorResourceType:
203 ASSERT_NOT_REACHED();
204 break;
205 }
206 }
207
208 }
209