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