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