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