OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (C) Research In Motion Limited 2010. All rights reserved. | 2 * Copyright (C) Research In Motion Limited 2010. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 29 matching lines...) Expand all Loading... | |
40 , m_resources(resources) | 40 , m_resources(resources) |
41 { | 41 { |
42 ASSERT(m_renderer); | 42 ASSERT(m_renderer); |
43 ASSERT(m_resources); | 43 ASSERT(m_resources); |
44 } | 44 } |
45 | 45 |
46 SVGResourcesCycleSolver::~SVGResourcesCycleSolver() | 46 SVGResourcesCycleSolver::~SVGResourcesCycleSolver() |
47 { | 47 { |
48 } | 48 } |
49 | 49 |
50 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderObject* renderer) con st | 50 class SVGResourcesCycleSolver::ActiveFrame { |
krit
2014/05/28 10:22:30
It seems like it could be a struct. The definition
fs
2014/05/28 11:23:48
I can make it a struct I suppose (see reply to com
| |
51 public: | |
52 ActiveFrame(ResourceSet& activeSet, RenderSVGResourceContainer* resource) | |
53 : m_activeSet(activeSet) | |
54 , m_resource(resource) | |
55 { | |
56 m_activeSet.add(m_resource); | |
57 } | |
58 ~ActiveFrame() | |
59 { | |
60 m_activeSet.remove(m_resource); | |
61 } | |
62 | |
63 private: | |
64 ResourceSet& m_activeSet; | |
65 RenderSVGResourceContainer* m_resource; | |
krit
2014/05/28 10:22:30
With activeSet, you mean visited resources? And m_
fs
2014/05/28 11:23:48
Heh, this was called m_visitedResources in earlier
| |
66 }; | |
67 | |
68 bool SVGResourcesCycleSolver::resourceContainsCycles(RenderSVGResourceContainer* resource) | |
51 { | 69 { |
52 ASSERT(renderer); | 70 // If we've traversed this sub-graph before and no cycles were observed, the n |
krit
2014/05/28 10:22:30
Is that algorithm using any of the known traversal
fs
2014/05/28 11:23:48
It's essentially a (recursive) depth-first travers
| |
71 // reuse that result. | |
72 if (m_dagCache.contains(resource)) | |
73 return false; | |
53 | 74 |
54 // First (first loop iteration) operate on the resources of the given | 75 ActiveFrame frame(m_activeResources, resource); |
55 // renderer. | 76 |
56 // <marker id="a"> <path marker-start="url(#b)"/> ... | 77 RenderObject* child = resource; |
57 // <marker id="b" marker-start="url(#a)"/> | 78 while (child) { |
58 // Then operate on the child resources of the given renderer. | 79 // Skip subtrees which are themselves resources. (They will be |
59 // <marker id="a"> <path marker-start="url(#b)"/> ... | 80 // processed - if needed - when they are actually referenced.) |
60 // <marker id="b"> <path marker-start="url(#a)"/> ... | 81 if (child != resource && child->isSVGResourceContainer()) { |
61 for (RenderObject* child = renderer; child; child = child->nextInPreOrder(re nderer)) { | 82 child = child->nextInPreOrderAfterChildren(resource); |
62 SVGResources* childResources = SVGResourcesCache::cachedResourcesForRend erObject(child); | |
63 if (!childResources) | |
64 continue; | 83 continue; |
84 } | |
85 if (SVGResources* childResources = SVGResourcesCache::cachedResourcesFor RenderObject(child)) { | |
86 // Fetch all the resources referenced by |child|. | |
87 ResourceSet childSet; | |
88 childResources->buildSetOfResources(childSet); | |
65 | 89 |
66 // A child of the given 'resource' contains resources. | 90 // Iterate resources referenced by |child|. |
67 HashSet<RenderSVGResourceContainer*> childSet; | 91 ResourceSet::iterator end = childSet.end(); |
68 childResources->buildSetOfResources(childSet); | 92 for (ResourceSet::iterator it = childSet.begin(); it != end; ++it) { |
93 if (m_activeResources.contains(*it) || resourceContainsCycles(*i t)) | |
94 return true; | |
95 } | |
96 } | |
97 child = child->nextInPreOrder(resource); | |
98 } | |
69 | 99 |
70 // Walk all child resources and check whether they reference any resourc e contained in the resources set. | 100 // No cycles found in (or from) this resource. Add it to the "DAG cache". |
71 HashSet<RenderSVGResourceContainer*>::iterator end = childSet.end(); | 101 m_dagCache.add(resource); |
72 for (HashSet<RenderSVGResourceContainer*>::iterator it = childSet.begin( ); it != end; ++it) { | |
73 if (m_allResources.contains(*it)) | |
74 return true; | |
75 } | |
76 } | |
77 return false; | 102 return false; |
78 } | 103 } |
79 | 104 |
80 void SVGResourcesCycleSolver::resolveCycles() | 105 void SVGResourcesCycleSolver::resolveCycles() |
81 { | 106 { |
82 ASSERT(m_allResources.isEmpty()); | 107 ASSERT(m_activeResources.isEmpty()); |
83 | 108 |
84 #if DEBUG_CYCLE_DETECTION > 0 | 109 // Add the first resource container from the ancestor-chain (including the |
85 fprintf(stderr, "\nBefore cycle detection:\n"); | 110 // renderer itself) to the resource path. (This is an optimization that |
86 m_resources->dump(m_renderer); | 111 // will reduce the number of steps by one for cycles back onto the |
87 #endif | 112 // "initiating" resource.) |
113 RenderObject* parent = m_renderer; | |
114 do { | |
krit
2014/05/28 10:22:30
why not while() {}? parent is not checked here.
fs
2014/05/28 11:23:48
m_renderer is assumed non-null (asserted in constr
| |
115 if (parent->isSVGResourceContainer()) { | |
116 m_activeResources.add(toRenderSVGResourceContainer(parent)); | |
117 break; | |
118 } | |
119 parent = parent->parent(); | |
120 } while (parent); | |
88 | 121 |
89 // Stash all resources into a HashSet for the ease of traversing. | 122 ResourceSet localResources; |
90 HashSet<RenderSVGResourceContainer*> localResources; | |
91 m_resources->buildSetOfResources(localResources); | 123 m_resources->buildSetOfResources(localResources); |
92 ASSERT(!localResources.isEmpty()); | |
93 | 124 |
94 // Add all parent resource containers to the HashSet. | 125 ResourceSet::iterator end = localResources.end(); |
95 HashSet<RenderSVGResourceContainer*> parentResources; | 126 for (ResourceSet::iterator it = localResources.begin(); it != end; ++it) { |
96 RenderObject* parent = m_renderer->parent(); | 127 if (m_activeResources.contains(*it) || resourceContainsCycles(*it)) |
97 while (parent) { | 128 breakCycle(*it); |
98 if (parent->isSVGResourceContainer()) | |
99 parentResources.add(toRenderSVGResourceContainer(parent)); | |
100 parent = parent->parent(); | |
101 } | 129 } |
102 | 130 |
103 #if DEBUG_CYCLE_DETECTION > 0 | 131 m_activeResources.clear(); |
104 fprintf(stderr, "\nDetecting wheter any resources references any of followin g objects:\n"); | |
105 { | |
106 fprintf(stderr, "Local resources:\n"); | |
107 HashSet<RenderSVGResourceContainer*>::iterator end = localResources.end( ); | |
108 for (HashSet<RenderSVGResourceContainer*>::iterator it = localResources. begin(); it != end; ++it) | |
109 fprintf(stderr, "|> %s: object=%p (node=%p)\n", (*it)->renderName(), *it, (*it)->node()); | |
110 | |
111 fprintf(stderr, "Parent resources:\n"); | |
112 end = parentResources.end(); | |
113 for (HashSet<RenderSVGResourceContainer*>::iterator it = parentResources .begin(); it != end; ++it) | |
114 fprintf(stderr, "|> %s: object=%p (node=%p)\n", (*it)->renderName(), *it, (*it)->node()); | |
115 } | |
116 #endif | |
117 | |
118 // Build combined set of local and parent resources. | |
119 m_allResources = localResources; | |
120 HashSet<RenderSVGResourceContainer*>::iterator end = parentResources.end(); | |
121 for (HashSet<RenderSVGResourceContainer*>::iterator it = parentResources.beg in(); it != end; ++it) | |
122 m_allResources.add(*it); | |
123 | |
124 // If we're a resource, add ourselves to the HashSet. | |
125 if (m_renderer->isSVGResourceContainer()) | |
126 m_allResources.add(toRenderSVGResourceContainer(m_renderer)); | |
127 | |
128 ASSERT(!m_allResources.isEmpty()); | |
129 | |
130 // The job of this function is to determine wheter any of the 'resources' as sociated with the given 'renderer' | |
131 // references us (or wheter any of its kids references us) -> that's a cycle , we need to find and break it. | |
132 end = localResources.end(); | |
133 for (HashSet<RenderSVGResourceContainer*>::iterator it = localResources.begi n(); it != end; ++it) { | |
134 RenderSVGResourceContainer* resource = *it; | |
135 if (parentResources.contains(resource) || resourceContainsCycles(resourc e)) | |
136 breakCycle(resource); | |
137 } | |
138 | |
139 #if DEBUG_CYCLE_DETECTION > 0 | |
140 fprintf(stderr, "\nAfter cycle detection:\n"); | |
141 m_resources->dump(m_renderer); | |
142 #endif | |
143 | |
144 m_allResources.clear(); | |
145 } | 132 } |
146 | 133 |
147 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer* resourceLea dingToCycle) | 134 void SVGResourcesCycleSolver::breakCycle(RenderSVGResourceContainer* resourceLea dingToCycle) |
148 { | 135 { |
149 ASSERT(resourceLeadingToCycle); | 136 ASSERT(resourceLeadingToCycle); |
150 if (resourceLeadingToCycle == m_resources->linkedResource()) { | 137 if (resourceLeadingToCycle == m_resources->linkedResource()) { |
151 m_resources->resetLinkedResource(); | 138 m_resources->resetLinkedResource(); |
152 return; | 139 return; |
153 } | 140 } |
154 | 141 |
(...skipping 28 matching lines...) Expand all Loading... | |
183 ASSERT(resourceLeadingToCycle == m_resources->clipper()); | 170 ASSERT(resourceLeadingToCycle == m_resources->clipper()); |
184 m_resources->resetClipper(); | 171 m_resources->resetClipper(); |
185 break; | 172 break; |
186 case SolidColorResourceType: | 173 case SolidColorResourceType: |
187 ASSERT_NOT_REACHED(); | 174 ASSERT_NOT_REACHED(); |
188 break; | 175 break; |
189 } | 176 } |
190 } | 177 } |
191 | 178 |
192 } | 179 } |
OLD | NEW |