Bug 233214

Created attachment 444437 [details] Patch

Comment on attachment 444437 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=444437&action=review > Source/WebCore/ChangeLog:15 > + caller knows that applying the filter function was not successful. "knows whether applying the filter function was successful" > Source/WebCore/platform/graphics/filters/FEConvolveMatrix.cpp:400 > // Rare situation, not optimizied for speed (pre-existing) "optimized" > Source/WebCore/platform/graphics/filters/FilterEffect.cpp:148 > if (hasResult()) > - return; > + return true; Is it the case that we should never call FilterEffect::apply() twice on the same object? Wondering if we should `ASSERT(!hasResult())` here before returning true if we do have a result already. > Source/WebCore/svg/graphics/filters/SVGFilter.cpp:108 > + lastEffect()->clearResultsRecursive(); Will you change this in a later patch to be non-recursive? > Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:186 > + if (stack.contains(effect)) SVG filters are unlikely to have very deep filter effect trees, but this will cause buildExpression to take O(n^2) time (where n is the depth of the expression tree). Can we either keep a side HashSet or (better) a bool on the FilterEffect that gets set and cleared as the effect is pushed to and popped from the stack? > Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:189 > + expression.insert(0, effect); This will also cause buildExpression to take O(n^2) time (where n is the total number of effects), if we keep inserting items at the front. Instead you could append them to the end, and as a final step, reverse the vector.

Comment on attachment 444437 [details] Patch r- to see another version with comments addressed.

Comment on attachment 444437 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=444437&action=review >> Source/WebCore/ChangeLog:15 >> + caller knows that applying the filter function was not successful. > > "knows whether applying the filter function was successful" Fixed. >> Source/WebCore/platform/graphics/filters/FEConvolveMatrix.cpp:400 >> // Rare situation, not optimizied for speed > > (pre-existing) "optimized" Fixed. >> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:148 >> + return true; > > Is it the case that we should never call FilterEffect::apply() twice on the same object? Wondering if we should `ASSERT(!hasResult())` here before returning true if we do have a result already. Consider the following filter: <svg width="7.5cm" height="5cm" viewBox="0 0 200 120"> <defs> <filter id="MyFilter" filterUnits="userSpaceOnUse" x="0" y="0" width="200" height="120"> <feGaussianBlur in="SourceAlpha" stdDeviation="4" result="blur"/> <feOffset in="blur" dx="4" dy="4" result="offsetBlur"/> <feSpecularLighting in="blur" surfaceScale="5" specularConstant=".75" specularExponent="20" lighting-color="#bbbbbb" result="specOut"> <fePointLight x="-5000" y="-10000" z="20000"/> </feSpecularLighting> <feComposite in="specOut" in2="SourceAlpha" operator="in" result="specOut"/> <feComposite in="SourceGraphic" in2="specOut" operator="arithmetic" k1="0" k2="1" k3="1" k4="0" result="litPaint"/> <feMerge> <feMergeNode in="offsetBlur"/> <feMergeNode in="litPaint"/> </feMerge> </filter> </defs> </svg> This should generate the following tree of FilterEffects: (1) FEMerge (2) FEOffset (offsetBlur) (3) FEGaussianBlur (blur) (4) SourceAlpha (5) SoureGraphic (6) FEComposite (litPaint) (7) SoureGraphic (8) FEComposite (specOut 2) (9) FESpecularLighting (specOut 1) (10) FEGaussianBlur (blur) (11) SourceAlpha (12) SoureGraphic (13) SourceAlpha (14) SoureGraphic The order of applying this tree with and without this patch is the following: (5) SoureGraphic (4) SourceAlpha (3) FEGaussianBlur (blur) (2) FEOffset (offsetBlur) (7) SoureGraphic (12) SoureGraphic (11) SourceAlpha (10) FEGaussianBlur (blur) (9) FESpecularLighting (specOut 1) (14) SoureGraphic (13) SourceAlpha (8) FEComposite (specOut 2) (6) FEComposite (litPaint) (1) FEMerge As you can see some FilterEffects are referenced more than once in this order because there are referenced multiple times in the filter. So once a FilterEffect is applied we should return true and this is a legitimate case. This order of applying the FilterEffects is what SVGFilterBuilder::buildExpression() will return. >> Source/WebCore/svg/graphics/filters/SVGFilter.cpp:108 >> + lastEffect()->clearResultsRecursive(); > > Will you change this in a later patch to be non-recursive? Fixed. >> Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:186 >> + if (stack.contains(effect)) > > SVG filters are unlikely to have very deep filter effect trees, but this will cause buildExpression to take O(n^2) time (where n is the depth of the expression tree). Can we either keep a side HashSet or (better) a bool on the FilterEffect that gets set and cleared as the effect is pushed to and popped from the stack? buildEffectExpression() just flattens the recursion we used to do in FilterEffect::apply(). We also drop applying the SVG filters if the number nodes in the tree is more than 100 nodes, see SVGFilterBuilder::buildFilterEffects. So the size of expression and stack should not be more than 100 at any point. >> Source/WebCore/svg/graphics/filters/SVGFilterBuilder.cpp:189 >> + expression.insert(0, effect); > > This will also cause buildExpression to take O(n^2) time (where n is the total number of effects), if we keep inserting items at the front. Instead you could append them to the end, and as a final step, reverse the vector. Done.

Created attachment 444459 [details] Patch

(In reply to Said Abou-Hallawa from comment #4) > As you can see some FilterEffects are referenced more than once in this > order because there are referenced multiple times in the filter. So once a > FilterEffect is applied we should return true and this is a legitimate case. I see now. > > SVG filters are unlikely to have very deep filter effect trees, but this will cause buildExpression to take O(n^2) time (where n is the depth of the expression tree). Can we either keep a side HashSet or (better) a bool on the FilterEffect that gets set and cleared as the effect is pushed to and popped from the stack? > > buildEffectExpression() just flattens the recursion we used to do in > FilterEffect::apply(). We also drop applying the SVG filters if the number > nodes in the tree is more than 100 nodes, see > SVGFilterBuilder::buildFilterEffects. So the size of expression and stack > should not be more than 100 at any point. OK so worst case we perform (100 * 99) / 2 = 4950 comparisons while searching through the stack. Might be worth a comment here to point out that in practice this won't be a problem?

(In reply to Cameron McCormack (:heycam) from comment #6) > OK so worst case we perform (100 * 99) / 2 = 4950 comparisons while > searching through the stack. Might be worth a comment here to point out > that in practice this won't be a problem? (I meant: (100 * 101) / 2 = 5050.)

<rdar://problem/85490380>

Committed r285916 (244325@main): <https://commits.webkit.org/244325@main> All reviewed patches have been landed. Closing bug and clearing flags on attachment 444459 [details].