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 blink {
     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 struct ActiveFrame {
     51     typedef SVGResourcesCycleSolver::ResourceSet ResourceSet;
     52 
     53     ActiveFrame(ResourceSet& activeSet, RenderSVGResourceContainer* resource)
     54         : m_activeSet(activeSet)
     55         , m_resource(resource)
     56     {
     57         m_activeSet.add(m_resource);
     58     }
     59     ~ActiveFrame()
     60     {
     61         m_activeSet.remove(m_resource);
     62     }
     63 
     64     ResourceSet& m_activeSet;
     65     RenderSVGResourceContainer* m_resource;
     66 };
     67 
     68 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderSVGResourceContainer* resource)
     69 {
     70     // If we've traversed this sub-graph before and no cycles were observed, then
     71     // reuse that result.
     72     if (m_dagCache.contains(resource))
     73         return false;
     74 
     75     ActiveFrame frame(m_activeResources, resource);
     76 
     77     RenderObject* node = resource;
     78     while (node) {
     79         // Skip subtrees which are themselves resources. (They will be
     80         // processed - if needed - when they are actually referenced.)
     81         if (node != resource && node->isSVGResourceContainer()) {
     82             node = node->nextInPreOrderAfterChildren(resource);
     83             continue;
     84         }
     85         if (SVGResources* nodeResources = SVGResourcesCache::cachedResourcesForRenderObject(node)) {
     86             // Fetch all the resources referenced by |node|.
     87             ResourceSet nodeSet;
     88             nodeResources->buildSetOfResources(nodeSet);
     89 
     90             // Iterate resources referenced by |node|.
     91             ResourceSet::iterator end = nodeSet.end();
     92             for (ResourceSet::iterator it = nodeSet.begin(); it != end; ++it) {
     93                 if (m_activeResources.contains(*it) || resourceContainsCycles(*it))
     94                     return true;
     95             }
     96         }
     97         node = node->nextInPreOrder(resource);
     98     }
     99 
    100     // No cycles found in (or from) this resource. Add it to the "DAG cache".
    101     m_dagCache.add(resource);
    102     return false;
    103 }
    104 
    105 void SVGResourcesCycleSolver::resolveCycles()
    106 {
    107     ASSERT(m_activeResources.isEmpty());
    108 
    109     // If the starting RenderObject is a resource container itself, then add it
    110     // to the active set (to break direct self-references.)
    111     if (m_renderer->isSVGResourceContainer())
    112         m_activeResources.add(toRenderSVGResourceContainer(m_renderer));
    113 
    114     ResourceSet localResources;
    115     m_resources->buildSetOfResources(localResources);
    116 
    117     // This performs a depth-first search for a back-edge in all the
    118     // (potentially disjoint) graphs formed by the resources referenced by
    119     // |m_renderer|.
    120     ResourceSet::iterator end = localResources.end();
    121     for (ResourceSet::iterator it = localResources.begin(); it != end; ++it) {
    122         if (m_activeResources.contains(*it) || resourceContainsCycles(*it))
    123             breakCycle(*it);
    124     }
    125 
    126     m_activeResources.clear();
    127 }
    128 
    129 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer* resourceLeadingToCycle)
    130 {
    131     ASSERT(resourceLeadingToCycle);
    132     if (resourceLeadingToCycle == m_resources->linkedResource()) {
    133         m_resources->resetLinkedResource();
    134         return;
    135     }
    136 
    137     switch (resourceLeadingToCycle->resourceType()) {
    138     case MaskerResourceType:
    139         ASSERT(resourceLeadingToCycle == m_resources->masker());
    140         m_resources->resetMasker();
    141         break;
    142     case MarkerResourceType:
    143         ASSERT(resourceLeadingToCycle == m_resources->markerStart() || resourceLeadingToCycle == m_resources->markerMid() || resourceLeadingToCycle == m_resources->markerEnd());
    144         if (m_resources->markerStart() == resourceLeadingToCycle)
    145             m_resources->resetMarkerStart();
    146         if (m_resources->markerMid() == resourceLeadingToCycle)
    147             m_resources->resetMarkerMid();
    148         if (m_resources->markerEnd() == resourceLeadingToCycle)
    149             m_resources->resetMarkerEnd();
    150         break;
    151     case PatternResourceType:
    152     case LinearGradientResourceType:
    153     case RadialGradientResourceType:
    154         ASSERT(resourceLeadingToCycle == m_resources->fill() || resourceLeadingToCycle == m_resources->stroke());
    155         if (m_resources->fill() == resourceLeadingToCycle)
    156             m_resources->resetFill();
    157         if (m_resources->stroke() == resourceLeadingToCycle)
    158             m_resources->resetStroke();
    159         break;
    160     case FilterResourceType:
    161         ASSERT(resourceLeadingToCycle == m_resources->filter());
    162         m_resources->resetFilter();
    163         break;
    164     case ClipperResourceType:
    165         ASSERT(resourceLeadingToCycle == m_resources->clipper());
    166         m_resources->resetClipper();
    167         break;
    168     case SolidColorResourceType:
    169         ASSERT_NOT_REACHED();
    170         break;
    171     }
    172 }
    173 
    174 }
    175