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