In RenderTableCell.cpp, compareBorders() is used to implement compareBorderStylesForQSort(). But it's not stable. When compareBorderStylesForQSort(a, b) returns 1, compareBorderStylesForQSort(b, a) can return 1 or 0. We should pass a stable compare function to qsort().
Created attachment 57485 [details] the patch
Comment on attachment 57485 [details] the patch Please add a test case, or explain why making one isn't possible (sounds like it should be possible).
(In reply to comment #2) > (From update of attachment 57485 [details]) > Please add a test case, or explain why making one isn't possible (sounds like it should be possible). it's a hard job, because it relies on the implementation of qsort()
Can a test be made that crashes on any common implementation? The bug title says "crash", so surely this was observed in practice?
(In reply to comment #4) > Can a test be made that crashes on any common implementation? The bug title says "crash", so surely this was observed in practice? Sorry, the title is probably misleading. I have seen it crashed in armcc's qsort(), and using stable compare function fixed it. I cannot reproduce it on Safari win32. But in general, the compare functions passed to sorting algorithm (including qsort, stable_sort, and sorted containers like std::set/map) should be written in a reliable way and should give consistent result. The compare function passed to qsort should always make this true: compare(a, b) == -compare(b, a). The old code uses a function that can make compare(a, b) == 1 and compare(b, a) == 0. The behavior of running qsort() with it is undetermined.
Can you add a test that crashes on armcc without this fix?
(In reply to comment #6) > Can you add a test that crashes on armcc without this fix? I'll give a try.
Created attachment 57990 [details] the test case
(In reply to comment #6) > Can you add a test that crashes on armcc without this fix? Finally got a test case that can reproduce the crash. Do you think it should go into LayoutTest?
Created attachment 58026 [details] Test case
Created attachment 58027 [details] the patch that fixes the problem
Comment on attachment 58027 [details] the patch that fixes the problem Is there a way to fix this without writing a whole new copy of the compareBorders function? That's quite undesirable, because we can have real problems if the two functions get out of sync. What's the particular thing in the original function that makes it inconsistent? The word "stable" has a specific meaning in sorting contexts. It means a sorting algorithm that does not reorder equal items in the array being sorted. Using the term stable in the title of the new version of the compareBorders function is imprecise and confusing since it already has a specific meaning for sorting.
(In reply to comment #12) > (From update of attachment 58027 [details]) > Is there a way to fix this without writing a whole new copy of the compareBorders function? That's quite undesirable, because we can have real problems if the two functions get out of sync. What's the particular thing in the original function that makes it inconsistent? > The word "stable" has a specific meaning in sorting contexts. It means a sorting algorithm that does not reorder equal items in the array being sorted. Using the term stable in the title of the new version of the compareBorders function is imprecise and confusing since it already has a specific meaning for sorting. 1) The existing compareBorders function is mainly used to choose a border style from 2. It looks buggy for example the santiy check ignore the BHIDDEN check. If border 1 doesn't exist and border 2 is hidden, it doesn't return an empty border value as it's supposed to do. In fact, !border1.exists() rarely happens. Also, this function returns border1 when 2 border styles are equal, and the old compareBorderStylesForQSort implementation only checks the return value once and assumes the returned value is the bigger one. so it can get compareBorderStylesForQSort(a, b) == 1 and compare...ForQSort(b, a) == 1. > return border1.precedence() >= border2.precedence() ? border1 : border2; When both borders are BHIDDEN, the result is compareBorderStylesForQSort(a, b) == -1 and compare...ForQSort(b, a) == -1. I'll try to make them use same code. 2) I thought about that, too, but couldn't find a good name. how about consistentCompare? or? rename stableCompareBorders to compareBorderStyles, but rename compareBorders to chooseBorderBetween?
Comment on attachment 58027 [details] the patch that fixes the problem there's a bug in there. HIDDEN border should take precedence.
Created attachment 58041 [details] Fixed bugs. use same function for both qsort and other cases Also fixed a bug in the old function: when both borders have NONE style, it didn't continue comparing any more. But it should continue checking other properties in this case according to the comment: // (2) Borders with a style of 'none' have the lowest priority. Only if the border properties of all // the elements meeting at this edge are 'none' will the border be omitted (but note that 'none' is // the default value for the border style.) // (3) If none of the styles are 'hidden' and at least one of them is not 'none', then narrow borders
Comment on attachment 58041 [details] Fixed bugs. use same function for both qsort and other cases oops wrong patch.
Created attachment 58042 [details] updated patch
Attachment 58041 [details] did not build on qt: Build output: http://webkit-commit-queue.appspot.com/results/3086190
Attachment 58041 [details] did not build on chromium: Build output: http://webkit-commit-queue.appspot.com/results/3095208
Also, FireFox renders the test case in the way different from webkit browsers. FireFox renders some borders around a few elements. WebKit browsers like Safari and Qt port don't render any border. My patch makes webkit do the similar thing as FireFox. I'm not sure if FireFox is doing the right thing. Any expert?
(In reply to comment #20) > Also, FireFox renders the test case in the way different from webkit browsers. FireFox renders some borders around a few elements. WebKit browsers like Safari and Qt port don't render any border. My patch makes webkit do the similar thing as FireFox. I'm not sure if FireFox is doing the right thing. Any expert? Please ignore this
FYI, Daniel Bates has tested this patch on mac, and it passed all tests. He also ran pixels test for LayoutTests/table and LayoutTest/fast/table and did not notice any significant differences. Thanks, Dan.
Comment on attachment 58042 [details] updated patch > + Make compareBorders() a consistent compare function which can used be by qsort(). "which can be used by..." > + Also fixed a bug in previous implementation that it didn't continue comparing when > + both borders have NONE style. If that's a separate bug it should have a separate patch and test case, and be fixed before this one. (See http://trac.webkit.org/wiki/CodeReview) Alternatively, leave that part out of this patch (keeping the behavior of the old implementation) and create a follow-up bug after this has landed. > // Sanity check the values passed in. If either is null, return the other. You might want to reword comments like the above one, since the function now returns an int, not one of its arguments. > // Rule #2 above. A style of 'none' has lowest priority and always loses to any other border. > - if (border2.style() == BNONE) > - return border1; > + if (border2.style() == BNONE) { > + if (border1.style() != BNONE) > + return 1; > + } > if (border1.style() == BNONE) > - return border2; > + return -1; It looks like -1 is always returned when both have style BNONE. Shouldn't it be 0, like for BHIDDEN? > @@ -767,10 +785,7 @@ static int compareBorderStylesForQSort(const void* pa, const void* pb) > const CollapsedBorderValue* b = static_cast<const CollapsedBorderValue*>(pb); > if (*a == *b) > return 0; > - CollapsedBorderValue borderWithHigherPrecedence = compareBorders(*a, *b); > - if (*a == borderWithHigherPrecedence) > - return 1; > - return -1; > + return compareBorders(*a, *b); > } Nice! In general I like that compareBorders() returns an int rather than a border; the name is better suited now than before. :) As for chooseBorder(), I'm not able to come up with a better name.
(In reply to comment #23) > (From update of attachment 58042 [details]) > > - if (border2.style() == BNONE) > > - return border1; > > + if (border2.style() == BNONE) { > > + if (border1.style() != BNONE) > > + return 1; > > + } > > if (border1.style() == BNONE) > > - return border2; > > + return -1; > It looks like -1 is always returned when both have style BNONE. Shouldn't it be 0, like for BHIDDEN? Nice catch! Actuall when both borders have style BNONE, we should continue comparing with other criteria. so it should > > "else" if (border1.style() == BNONE)
Comment on attachment 58042 [details] updated patch Review cancelled because of the bug Kent found.
(In reply to comment #24) > (In reply to comment #23) > > (From update of attachment 58042 [details] [details]) > > > > - if (border2.style() == BNONE) > > > - return border1; > > > + if (border2.style() == BNONE) { > > > + if (border1.style() != BNONE) > > > + return 1; > > > + } > > > if (border1.style() == BNONE) > > > - return border2; > > > + return -1; > > It looks like -1 is always returned when both have style BNONE. Shouldn't it be 0, like for BHIDDEN? > > Nice catch! Actuall when both borders have style BNONE, we should continue comparing with other criteria. so it should > > > > > "else" if (border1.style() == BNONE) I'm not very sure. I'll keep the old behavior (just return 0) and open another bug for that.
Created attachment 62429 [details] Fix comments & keep old behavior for BNONE style
Comment on attachment 58026 [details] Test case Commit-queue won't land this, please land manually.
(In reply to comment #28) > (From update of attachment 58026 [details]) > Commit-queue won't land this, please land manually. ha. thanks!
Why won't it land it?
Comment on attachment 62429 [details] Fix comments & keep old behavior for BNONE style Clearing flags on attachment: 62429 Committed r67862: <http://trac.webkit.org/changeset/67862>
Comment on attachment 58026 [details] Test case give a try...
"This" was the other patch, the one with test. I thought commit queue didn't like multiple patches per bug.
Comment on attachment 58026 [details] Test case commit queue says: Building and testing without the patch as a sanity check 5 minutes ago Unable to build and test patch I'll manually commit it
(In reply to comment #34) > (From update of attachment 58026 [details]) > commit queue says: Building and testing without the patch as a sanity check 5 minutes ago Unable to build and test patch > > I'll manually commit it This just means the cq had trouble building. (likely due to tree redness). It's a non-fatal error.
(In reply to comment #35) > This just means the cq had trouble building. (likely due to tree redness). It's a non-fatal error. The commit-queue will always comment in the bug if it hits a fatal error.
(In reply to comment #33) > "This" was the other patch, the one with test. I thought commit queue didn't like multiple patches per bug. The commit-queue can handle multiple patches per bug. It didn't used to like them, no. :) I wouldn't say they're recommended, but the cq will try and process patches in attachment order per-bug. it also won't close a bug after landing if there are still non-obsolete patches on that bug.
Comment on attachment 58026 [details] Test case Rejecting patch 58026 from commit-queue. Failed to run "[u'git', u'svn', u'dcommit']" exit_code: 1 Last 500 characters of output: repository/webkit/trunk ... M LayoutTests/ChangeLog A LayoutTests/tables/sort-collapsed-border-styles.html A repository hook failed: Commit blocked by pre-commit hook (exit code 1) with output: The following files contain tab characters: trunk/LayoutTests/tables/sort-collapsed-border-styles.html Please use spaces instead to indent. If you must commit a file with tabs, use svn propset to set the "allow-tabs" property. at /usr/local/git/libexec/git-core/git-svn line 572 Full output: http://queues.webkit.org/results/4026079
Created attachment 68135 [details] test case (tab removed)
Comment on attachment 68135 [details] test case (tab removed) with the tab removed
When I tried manually committing it. I got this: RA layer request failed: MKACTIVITY of '/repository/webkit/!svn/act/9569dd30-c4f c-11df-b9b0-c0cdfa48311f': 403 Forbidden (http://svn.webkit.org) at C:\Git/libex ec/git-core/git-svn line 3945
This appears to have hung the commit-cluster again. I'm investigating. It's not your fault, it should not be possible for a patch to hang the cluster. :)
(In reply to comment #42) > This appears to have hung the commit-cluster again. I'm investigating. It's not your fault, it should not be possible for a patch to hang the cluster. :) I did type wrong user/password more than one time. I haven't pushed a commit by myself for very long time. I cannot live without CQ :)
After this revision landed, fast/repaint/table-cell-collapsed-border.html started generating a different result and so is causing failures on the Chromium build bots. I am not certain whether the new result is still valid or not, but I suspect it's now drawing the borders in a different order and generating invalid results. Please run this test and validate whether the results are still valid - I don't want to revert your CL when it's possible we just need to rebaseline the test expectations.
Did this get landed manually and the bug not updated?
Looks like it landed as r67862.
Closing, per above.
(In reply to comment #47) > Closing, per above. The test case is still not landed...
(In reply to comment #44) > After this revision landed, fast/repaint/table-cell-collapsed-border.html started generating a different result and so is causing failures on the Chromium build bots. I am not certain whether the new result is still valid or not, but I suspect it's now drawing the borders in a different order and generating invalid results. > > Please run this test and validate whether the results are still valid - I don't want to revert your CL when it's possible we just need to rebaseline the test expectations. The patch fixes the compare function passed to qsort. So it is not surprising that it invalidates some old test result. I will check with fast/repaint/table-cell-collapsed-border.html.
(In reply to comment #44) > After this revision landed, fast/repaint/table-cell-collapsed-border.html started generating a different result and so is causing failures on the Chromium build bots. I am not certain whether the new result is still valid or not, but I suspect it's now drawing the borders in a different order and generating invalid results. > > Please run this test and validate whether the results are still valid - I don't want to revert your CL when it's possible we just need to rebaseline the test expectations. I noticed even the 2 table-cell-collapsed-border-expected.png files in chromium-linux and chromium-win are different. The new result is reverse of the old result: the actual result in chromium-win build is expected result in chromium-linux, and the actual result in chromium-linux is the expected result in chromium-win. I guess it must be due to the difference between 2 qsort algorithms in handling equal items.
OK, so I'll rebaseline the tests then. Thanks for verifying that they are correct.
Ideally we don’t want test results that are different on different platforms because of qsort. Maybe we can change things around so the sort is stable?
(In reply to comment #52) > Ideally we don’t want test results that are different on different platforms because of qsort. Maybe we can change things around so the sort is stable? 2 ways I can see: 1. use stable_sort instead of qsort to avoid changing the order of 2 equal items 2. make compare function never return 0 Seems 2) is very hard to be done gracefully. Also in most cases there are not too many collapsed border styles to sort. So probably 1) is acceptable?
*** Bug 13147 has been marked as a duplicate of this bug. ***
(In reply to comment #53) > 2 ways I can see: > > 1. use stable_sort instead of qsort to avoid changing the order of 2 equal items > 2. make compare function never return 0 > > Seems 2) is very hard to be done gracefully. Also in most cases there are not too many collapsed border styles to sort. So probably 1) is acceptable? I’m not sure what order the borders are in beforehand. It seems fine to use stable_sort instead of qsort if the order beforehand is something well defined. In other words, what is the ordering we want to apply to otherwise equal border styles? Some sort of document order? I guess this bug may not be the right place to discuss this, but it would be nice to get this tidy.
(In reply to comment #55) > (In reply to comment #53) > > 2 ways I can see: > > > > 1. use stable_sort instead of qsort to avoid changing the order of 2 equal items > > 2. make compare function never return 0 > > > > Seems 2) is very hard to be done gracefully. Also in most cases there are not too many collapsed border styles to sort. So probably 1) is acceptable? > > I’m not sure what order the borders are in beforehand. It seems fine to use stable_sort instead of qsort if the order beforehand is something well defined. > > In other words, what is the ordering we want to apply to otherwise equal border styles? Some sort of document order? > Seems the pre-sort order is: 1) order of children nodes 2) for each child node: left border, right, top and then bottom
try the test case
Comment on attachment 68135 [details] test case (tab removed) Rejecting attachment 68135 [details] from commit-queue. Failed to run "['./Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=cr-jail-3', 'build-and-test', '--no-clean', '--no-update', '--test', '--non-interactive']" exit_code: 2 Last 500 characters of output: sts/websocket/tests/workers ...... http/tests/workers ..... http/tests/xhtmlmp . http/tests/xmlhttprequest ............................................................................................................................................................................ http/tests/xmlhttprequest/web-apps ............... http/tests/xmlhttprequest/workers ......... 635.73s total testing time 22228 test cases (99%) succeeded 1 test case (<1%) was new 13 test cases (<1%) had stderr output Full output: http://queues.webkit.org/results/7325106
The commit-queue should give you a better message here, but your patch is missing expectation files for your new tests.
This test shoudl be dump as text. Are you sure this is a reduced test case? it looks like it might be way bigger than necessary.
(In reply to comment #60) > This test shoudl be dump as text. > Are you sure this is a reduced test case? it looks like it might be way bigger than necessary. Probably bigger than necessary. I used it to reprodce a crash in qsort with the old compare function. I didn't see rvct's qsort code, and just blindly tried different combinations and got a crash. Also, to test the sorting algorithm, problably the longer the better? Anyway the code has been changed from using qsort to using std::sort. Not sure if this test case is still important to us. Maybe leaving it to this bug is good enough?
I'm confused as to the status of this bug.