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