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