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
37namespace WebCore {
38
39SVGResourcesCycleSolver::SVGResourcesCycleSolver(RenderObject* renderer, SVGResources* resources)
40    : m_renderer(renderer)
41    , m_resources(resources)
42{
43    ASSERT(m_renderer);
44    ASSERT(m_resources);
45}
46
47SVGResourcesCycleSolver::~SVGResourcesCycleSolver()
48{
49}
50
51bool 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
97void 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
164void 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