Home | History | Annotate | Download | only in svg 
      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
    214