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