CCLayerSorter performs "topological sort", which enforces that nodes are ordered correctly only when there is a dependency between them. Nodes that are not dependent on each other (explicitly or transitively) can be in any order. In CCLayerSorter, when there are no explicit dependencies between two layers, we end up reversing the order of those layers (because we use removeLast() to get the next item efficiently). But it turns out that ordering matters -- we should be preserving the ordering of layers that WebCore gave us when there is no other constraint on ordering of particular layers. - The "theoretically correct" solution is to make these additional "preserve ordering" dependencies explicit in the topological sort. However, this will mean that we always create O(n^2) edges for n nodes, which will hurt scalability of the implementation. - The simpler solution, which I prefer, is simply to preserve the original ordering of the list of layers, when there are no explicit dependencies that require different ordering. This can be done simply by using a FIFO queue instead of the current removeLast() stack-like behavior. I'll proceed with the simpler solution unless someone finds a good reason to do the theoretically correct one =) I already verified this will fix http://code.google.com/p/chromium/issues/detail?id=89955 It might also address http://code.google.com/p/chromium/issues/detail?id=99564 http://code.google.com/p/chromium/issues/detail?id=102943 http://code.google.com/p/chromium/issues/detail?id=102663
Created attachment 120246 [details] includes fix and appropriate unit test
Does this fix the issues in the linked crbugs?
Attachment 120246 [details] did not pass style-queue: Failed to run "['Tools/Scripts/update-webkit']" exit_code: 9 Updating OpenSource First, rewinding head to replay your work on top of it... Applying: Inform the scrolling coordinator when scrollbar layers come and go Using index info to reconstruct a base tree... <stdin>:474806: trailing whitespace. [Chromium] DatabaseTrackerChromium: iterating DatabaseSet races with Database disposal on worker thread <stdin>:474827: trailing whitespace. Nothing to test, just removing redundant code. Correct behavior tested by <stdin>:475346: trailing whitespace. warning: 3 lines add whitespace errors. Falling back to patching base and 3-way merge... warning: too many files (created: 167528 deleted: 3), skipping inexact rename detection Auto-merging LayoutTests/ChangeLog CONFLICT (content): Merge conflict in LayoutTests/ChangeLog Auto-merging LayoutTests/platform/chromium/test_expectations.txt CONFLICT (content): Merge conflict in LayoutTests/platform/chromium/test_expectations.txt Auto-merging Source/WebCore/ChangeLog CONFLICT (content): Merge conflict in Source/WebCore/ChangeLog Auto-merging Source/WebCore/page/ScrollingCoordinator.h CONFLICT (content): Merge conflict in Source/WebCore/page/ScrollingCoordinator.h Auto-merging Source/WebCore/page/mac/ScrollingCoordinatorMac.mm CONFLICT (content): Merge conflict in Source/WebCore/page/mac/ScrollingCoordinatorMac.mm Auto-merging Source/WebCore/platform/ScrollView.cpp Auto-merging Source/WebCore/rendering/RenderLayerCompositor.cpp CONFLICT (content): Merge conflict in Source/WebCore/rendering/RenderLayerCompositor.cpp Auto-merging Source/WebKit2/ChangeLog CONFLICT (content): Merge conflict in Source/WebKit2/ChangeLog Auto-merging Tools/ChangeLog CONFLICT (content): Merge conflict in Tools/ChangeLog Auto-merging Tools/Scripts/build-webkit Auto-merging Tools/Scripts/webkitdirs.pm CONFLICT (content): Merge conflict in Tools/Scripts/webkitdirs.pm Failed to merge in the changes. Patch failed at 0001 Inform the scrolling coordinator when scrollbar layers come and go When you have resolved this problem run "git rebase --continue". If you would prefer to skip this patch, instead run "git rebase --skip". To restore the original branch and stop rebasing run "git rebase --abort". rebase refs/remotes/origin/master: command returned error: 1 Died at Tools/Scripts/update-webkit line 158. If any of these errors are false positives, please file a bug against check-webkit-style.
Comment on attachment 120246 [details] includes fix and appropriate unit test (In reply to comment #2) > Does this fix the issues in the linked crbugs? It does fix it for http://code.google.com/p/chromium/issues/detail?id=89955 I'll check the other issues soon, and let you know. Will also update to tip of tree and submit new patch.
Tested on osx, this patch does fix: http://code.google.com/p/chromium/issues/detail?id=89955 http://code.google.com/p/chromium/issues/detail?id=99564 It does not fix: http://code.google.com/p/chromium/issues/detail?id=102943 http://code.google.com/p/chromium/issues/detail?id=102663 From the problems I see on those two issues, it looks like those remaining two issues also need an additional bugfix separate from this one.
Awesome news. When you get a new patch ready, I think this looks like a good thing for Vangelis to check over.
Created attachment 120255 [details] updated to tip of tree, removed one inconsistent comment
(In reply to comment #6) > Awesome news. When you get a new patch ready, I think this looks like a good thing for Vangelis to check over. I verified couple of other issues along with http://code.google.com/p/chromium/issues/detail?id=89955 which are related with preserve-3d property but they are not getting fixed with this patch. I am attaching the sample html pages which are still reproducible with the patch.
Created attachment 120266 [details] Sample page with 3d transformations having preserver-3d property.
Created attachment 120267 [details] Another sample page with preserve-3d property and 3d transformations
(In reply to comment #8) > (In reply to comment #6) > > Awesome news. When you get a new patch ready, I think this looks like a good thing for Vangelis to check over. > > I verified couple of other issues along with http://code.google.com/p/chromium/issues/detail?id=89955 which are related with preserve-3d property but they are not getting fixed with this patch. > > I am attaching the sample html pages which are still reproducible with the patch. Ravi, can you please clarify, the original test case on 89955 does get fixed properly with this patch? I will double-check, but I expect these other tests will need to be fixed in a separate bug that fixes z-ordering tie-breakers (which I did not change on this patch). Thanks again for bringing up these additional cases!
(In reply to comment #11) > (In reply to comment #8) > > (In reply to comment #6) > > > Awesome news. When you get a new patch ready, I think this looks like a good thing for Vangelis to check over. > > > > I verified couple of other issues along with http://code.google.com/p/chromium/issues/detail?id=89955 which are related with preserve-3d property but they are not getting fixed with this patch. > > > > I am attaching the sample html pages which are still reproducible with the patch. > > Ravi, can you please clarify, the original test case on 89955 does get fixed properly with this patch? Yes the test case of 89955 is fixed with the patch. > > I will double-check, but I expect these other tests will need to be fixed in a separate bug that fixes z-ordering tie-breakers (which I did not change on this patch). I added the new tests to this bug because 92720 was duped to 89955. Since you are planning to re-open 92720 after verification (as per last comments on 89955 and 92720) this patch is fine with me. > > Thanks again for bringing up these additional cases!
Comment on attachment 120255 [details] updated to tip of tree, removed one inconsistent comment View in context: https://bugs.webkit.org/attachment.cgi?id=120255&action=review That's a great find, Shawn! I suspect that part of the problem is also the usage of m_zRange. It's value is calculated based on the max difference between all the Z values found in the group of layers (line 325). However, if all the layers to be sorted are on the same plane then m_zRange = 0 which means that we could mistakenly create dependencies between them. I think we should specify the exit threshold in line 263 as something like max(m_range * 0.01 , 0.01) . > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:432 > + // z-index/layout ordering). To preserve this ordering, we use You should probably rework this comment to not mention Vector::removeLast() as this reference only makes sense in the context of a diff with the previous implementation. It should suffice to say that "to preserve this ordering we process the nodes in the order they were stored with" or something like that.
(In reply to comment #13) > (From update of attachment 120255 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=120255&action=review > > That's a great find, Shawn! > > I suspect that part of the problem is also the usage of m_zRange. It's value is calculated based on the max difference between all the Z values found in the group of layers (line 325). However, if all the layers to be sorted are on the same plane then m_zRange = 0 which means that we could mistakenly create dependencies between them. I think we should specify the exit threshold in line 263 as something like max(m_range * 0.01 , 0.01) . After more investigation: Thanks to these additional test cases and Vangelis's insight... the next problem to address is definitely incorrect dependencies that get added due to numerical error. But it turns out its not because of exitThreshold. The exitThreshold only saves computation once the difference is large enough. but incorrect dependencies are still created whenever zDiff is not exactly zero. The fix is to add an epsilon in CCLayerSorter::checkOverlap (if zDiff > epsilon, if zDiff < epsilon). I verified this solves Ravi's useful test cases. However, this is a little bit fragile - there could always be the rare website that needs a different epsilon to work correctly. Vangelis do you think there exists a more robust fix? I can think of revisiting the triangle-triangle test code, to see if we can compute what is in front of what in a more numerically robust way, but I don't know that code yet, so I'm not convinced it will ultimately solve the problem. By the way, this epsilon fix does not fix http://code.google.com/p/chromium/issues/detail?id=102943 or http://code.google.com/p/chromium/issues/detail?id=102663 ... I think those pages might not even be triggering the layerSorter.
(In reply to comment #14) > (In reply to comment #13) > > (From update of attachment 120255 [details] [details]) > > View in context: https://bugs.webkit.org/attachment.cgi?id=120255&action=review > > > > That's a great find, Shawn! > > > > I suspect that part of the problem is also the usage of m_zRange. It's value is calculated based on the max difference between all the Z values found in the group of layers (line 325). However, if all the layers to be sorted are on the same plane then m_zRange = 0 which means that we could mistakenly create dependencies between them. I think we should specify the exit threshold in line 263 as something like max(m_range * 0.01 , 0.01) . > > After more investigation: > > Thanks to these additional test cases and Vangelis's insight... the next problem to address is definitely incorrect dependencies that get added due to numerical error. But it turns out its not because of exitThreshold. The exitThreshold only saves computation once the difference is large enough. but incorrect dependencies are still created whenever zDiff is not exactly zero. > > The fix is to add an epsilon in CCLayerSorter::checkOverlap (if zDiff > epsilon, if zDiff < epsilon). > > I verified this solves Ravi's useful test cases. However, this is a little bit fragile - there could always be the rare website that needs a different epsilon to work correctly. > > Vangelis do you think there exists a more robust fix? I can think of revisiting the triangle-triangle test code, to see if we can compute what is in front of what in a more numerically robust way, but I don't know that code yet, so I'm not convinced it will ultimately solve the problem. I think the epsilon approach is our best bet at the moment. With floating point math there will always be numerical issues around testing for equality. We could presumably also scale the epsilon value by the total z scale in the scene but cap it to some fairly low value (e.g. 0.001). Out of curiosity, for the examples we fail, what's the magnitude of the zDiff? > > By the way, this epsilon fix does not fix http://code.google.com/p/chromium/issues/detail?id=102943 or http://code.google.com/p/chromium/issues/detail?id=102663 ... I think those pages might not even be triggering the layerSorter.
> I think the epsilon approach is our best bet at the moment. With floating point math there will always be numerical issues around testing for equality. We could presumably also scale the epsilon value by the total z scale in the scene but cap it to some fairly low value (e.g. 0.001). Out of curiosity, for the examples we fail, what's the magnitude of the zDiff? zDiff is on the order of +/- .0001, however, I would expect that this magnitude changes based on how error accumulates in the transforms for the layer. I'm submitting a new patch soon that includes both fixes.
Created attachment 121001 [details] includes both bugfixes
Created attachment 121004 [details] merged the existing exitThreshold and new nonZeroThreshold
Comment on attachment 121004 [details] merged the existing exitThreshold and new nonZeroThreshold View in context: https://bugs.webkit.org/attachment.cgi?id=121004&action=review > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:266 > + float nonZeroThreshold = max(m_zRange * 0.001, 0.001); Do we need to lower the range multiplier to 0.001 from 0.01 ? I realize that this is all somewhat inaccurate but I'm curious if it's necessary to change the existing value in order to solve the case where m_zRange == 0.0 (which is the source of the issue here).
Comment on attachment 121004 [details] merged the existing exitThreshold and new nonZeroThreshold View in context: https://bugs.webkit.org/attachment.cgi?id=121004&action=review >> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:266 >> + float nonZeroThreshold = max(m_zRange * 0.001, 0.001); > > Do we need to lower the range multiplier to 0.001 from 0.01 ? I realize that this is all somewhat inaccurate but I'm curious if it's necessary to change the existing value in order to solve the case where m_zRange == 0.0 (which is the source of the issue here). Discussed offline with Vangelis. It wasn't necessary to change the order of magnitude, and to minimize the change this patch incurs, I'll submit a new patch right now that doesn't change the original exitThreshold.
Created attachment 121026 [details] un-merged exitThreshold and nonZeroThreshold again
Comment on attachment 121026 [details] un-merged exitThreshold and nonZeroThreshold again Looks good! Thanks, Shawn.
Comment on attachment 121026 [details] un-merged exitThreshold and nonZeroThreshold again R=me based on Vangelis' unofficial review
Comment on attachment 121026 [details] un-merged exitThreshold and nonZeroThreshold again Clearing flags on attachment: 121026 Committed r104002: <http://trac.webkit.org/changeset/104002>
All reviewed patches have been landed. Closing bug.
(In reply to comment #24) > (From update of attachment 121026 [details]) > Clearing flags on attachment: 121026 > > Committed r104002: <http://trac.webkit.org/changeset/104002> Thanks Shawn for the fix. It helps us a lot. :)