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 }