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