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 36namespace WebCore { 37 38SVGResourcesCycleSolver::SVGResourcesCycleSolver(RenderElement& renderer, SVGResources& resources) 39 : m_renderer(renderer) 40 , m_resources(resources) 41{ 42} 43 44SVGResourcesCycleSolver::~SVGResourcesCycleSolver() 45{ 46} 47 48bool 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 90void 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 148void 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} 195