e679c39a6e007eb0f0af142780cd7c198b676667
[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 // 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
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
47 SVGResourcesCycleSolver::~SVGResourcesCycleSolver()
48 {
49 }
50
51 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->firstChildSlow(); 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
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
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