Bug 13147 - RenderTableCell::sortBorderStyles does not meet qsort's contract
Summary: RenderTableCell::sortBorderStyles does not meet qsort's contract
Status: RESOLVED DUPLICATE of bug 39966
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 523.x (Safari 3)
Hardware: All OS X 10.4
: P2 Normal
Assignee: Dave Hyatt
Depends on:
Reported: 2007-03-21 13:04 PDT by Patrick
Modified: 2010-09-22 03:16 PDT (History)
1 user (show)

See Also:

Patch to use a stable sort instead. (1.34 KB, patch)
2007-03-21 14:00 PDT, Dave Hyatt
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Patrick 2007-03-21 13:04:17 PDT
When sorting CollapsedBorderStyles with qsort, the comparator function (compareBorderStylesForQSort) does not honor the requirement that cmp(a, b) == cmp(b, a). This does not appear for the qsort implementation on the Mac but if you use a bubblesort instead of qsort, the problem appears.

The issue is that two borders differ only by color and so compareBorders() returns the first parameter each time it is called. This means that calling compareBorders(a, b) != compareBorders(b, a) and thus compareBorderStylesForQSort(a, b) != compareBorderStylesForQSort(b, a) and so an infinite loop can occur because the sorting algorithm will constantly swap the two values.
Comment 1 Dave Hyatt 2007-03-21 14:00:46 PDT
Created attachment 13748 [details]
Patch to use a stable sort instead.

This patch switching border style comparison to use a stable sort instead.
Comment 2 Patrick 2007-03-22 10:08:05 PDT
stable_sort will work but it is not the correct solution. A better solution is to fix the comparison function so that a < b => b > a.
Comment 3 Steve Block 2010-09-22 03:16:41 PDT
It looks to me like this is fixed with http://trac.webkit.org/changeset/67862 (https://bugs.webkit.org/show_bug.cgi?id=39966) as compareBorders() now returns 0 in the case when borders differ only in colour.

> if (border1.precedence() == border2.precedence()) 
>     return 0;

*** This bug has been marked as a duplicate of bug 39966 ***