I have seen infinite recursion in this function with Fuzz bugs. Also there is nothing in this function prevents it from visiting the same renderer multiple times. Since we allow cycles in SVGDocumentExtensions reference sets, we can look at the SVG resource dependency relationship as a graph not a tree. So we should be clear in the implementation of this function that we are traversing a parent tree and a dependency graph. We can use the BFS algorithm to make the function clearer and easier to read. We should use a "visited" flag to prevent a node from being visited twice.
Created attachment 327087 [details] Patch
<rdar://problem/35593936>
Comment on attachment 327087 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=327087&action=review This algorithm uses more hash table lookups than the old one did. The old algorithm was careful to make both add and contains share a single hash table lookup. I think the best alternative for a new algorithm would be to replace both the Vector and HashSet with a single ListHashSet. We can add new elements to the set as we discover them, and use an iterator to walk through them in the order they were added. The ListHashSet supports iterating through the set as we add items to it. This makes both discoveredObjects and markedObjects into a single hash table and means we will only hash each item once. It will take a little bit of careful restructuring, but should work fine. > Source/WebCore/ChangeLog:8 > + Use the BFS algorithm to make the function clearer and easier to read. Does BFS mean breadth-first search? > Source/WebCore/rendering/svg/RenderSVGResource.cpp:161 > + if (RenderSVGResourceFilter* filter = resources->filter()) I suggest auto* here. > Source/WebCore/rendering/svg/RenderSVGResource.cpp:164 > + if (RenderSVGResourceMasker* masker = resources->masker()) I suggest auto* here. > Source/WebCore/rendering/svg/RenderSVGResource.cpp:167 > + if (RenderSVGResourceClipper* clipper = resources->clipper()) I suggest auto* here. > Source/WebCore/rendering/svg/RenderSVGResource.cpp:190 > + if (parent && !markedObjects.contains(parent) && !discoveredObjects.contains(parent)) { Vector::contains is a potentially expensive operation that can make the algorithm O(n^2). Since we need to do contains, we should be using a ListHashSet instead of a Vector. > Source/WebCore/rendering/svg/RenderSVGResource.cpp:193 > + downcast<RenderSVGResourceContainer>(object)->removeAllClientsFromCache(); To avoid a null check that the compiler might or might not otherwise be able to remove, we should write: downcast<SVGResourceContainer>(*object).removeAllClientsFromCache(); > Source/WebCore/rendering/svg/RenderSVGResource.cpp:195 > + discoveredObjects.insert(0, parent); Vector::insert is a potentially expensive operation that can make the algorithm O(n^2). That’s why we would normally use Deque/append/takeFirst instead of Vector/insert(0)/takeLast. But since we want to do the contains operation as well, we should use ListHashSet/add/takeFirst. Except that I think we should probably use ListHashSet/add and an iterator and not remove things from the set at all, iterate instead. That will visit nodes in a different order, but I think that’s OK. > Source/WebCore/rendering/svg/RenderSVGResource.cpp:199 > + if (!element || !element->isSVGElement()) This should be: if (!is<SVGElement>(element)) > Source/WebCore/rendering/svg/RenderSVGResource.cpp:205 > + HashSet<SVGElement*>* dependencies = element->document().accessSVGExtensions().setOfElementsReferencingTarget(downcast<SVGElement>(element)); I suggest auto* here.