Bug 23395 - Web Inpsector Debugger's Source List Should Be Sorted
Summary: Web Inpsector Debugger's Source List Should Be Sorted
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Inspector (Deprecated) (show other bugs)
Version: 528+ (Nightly build)
Hardware: All OS X 10.5
: P2 Normal
Assignee: Timothy Hatcher
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-01-16 15:39 PST by boucher
Modified: 2009-03-01 08:53 PST (History)
0 users

See Also:


Attachments
Patch that sorts alphabetically. (1.61 KB, patch)
2009-01-16 15:58 PST, boucher
oliver: review-
Details | Formatted Diff | Diff
Test case for the bug (283 bytes, text/html)
2009-01-16 16:00 PST, boucher
no flags Details
Patch 2, with binary search (3.00 KB, patch)
2009-01-16 19:29 PST, boucher
no flags Details | Formatted Diff | Diff
accidentally neglected to update the change log (2.96 KB, patch)
2009-01-16 19:34 PST, boucher
oliver: review-
Details | Formatted Diff | Diff
updated test case with more items (748 bytes, text/html)
2009-01-16 23:28 PST, boucher
no flags Details
updated patch (3.60 KB, patch)
2009-01-16 23:32 PST, boucher
timothy: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description boucher 2009-01-16 15:39:37 PST
Currently the list of sources isn't in any order. They should be sorted alphabetically.
Comment 1 boucher 2009-01-16 15:58:26 PST
Created attachment 26813 [details]
Patch that sorts alphabetically.

I'll attach a simple test case as well.
Comment 2 boucher 2009-01-16 16:00:36 PST
Created attachment 26814 [details]
Test case for the bug

If you run this before applying the patch, the two sources will appear in reverse alphabetical order, mootools, jquery. This isn't purposeful, its just the way it happens to work out. 

Once applying the patch, they will be listed in alphabetical order.
Comment 3 Oliver Hunt 2009-01-16 17:19:27 PST
Comment on attachment 26813 [details]
Patch that sorts alphabetically.

That results in O(N) insertion time, and O(N^2) if there are lots of items.  Given a loop with an eval inside it this could result in excessively poor performance.

It is probably best to write a function that does a binary search to find the insertion location, and then use that.
Comment 4 boucher 2009-01-16 19:29:27 PST
Created attachment 26822 [details]
Patch 2, with binary search

I think the 90% case is one where you don't have enough scripts to make the performance improvement of a binary search useful (in fact you may make it slower), and I tested it with a few hundred sources with no performance problem.

That being said, here's a version that uses binary search. It adds the function as a utility on Array, following the model of several other utility methods. It takes a comparison function so its reusable by anyone interested in performing a binary search.
Comment 5 boucher 2009-01-16 19:34:58 PST
Created attachment 26823 [details]
accidentally neglected to update the change log
Comment 6 Oliver Hunt 2009-01-16 19:59:32 PST
Comment on attachment 26823 [details]
accidentally neglected to update the change log

This seems awfully convoluted, why not just
function lowerBoundForObjectInSortedList(list, object, comparator) {
    var floor = Math.floor;
    var first = 0;
    var last = list.length - 1;
    while (first <= last)
    {
        var mid = floor((first + last) / 2);
        var c = comparator(object, list[mid]);

        if (c > 0)
            first = mid + 1;
        else if (c < 0)
            last = mid - 1;
        else
        {
            while (mid < length - 1 && comparator(object, list[mid + 1]) == 0)
                mid++;

            return mid;
        }
    }

    return -1;
}

then you just have
insertionIndex = lowerBoundForObjectInSortedList(select.childNodes, option, function(...){...})

Which removes the completely unnecessary use of apply -- `call` would have been better in this case anyway as you have a fixed number of arguments.

My other concern is that your original code would appear to have been untested, line 957 uses aContext which doesn't appear to exist anywhere (and isn't necessary), length also doesn't appear to be defined anywhere, although i can't work out how the code could work at all in this case.
Comment 7 boucher 2009-01-16 23:28:13 PST
Created attachment 26826 [details]
updated test case with more items
Comment 8 boucher 2009-01-16 23:32:49 PST
Created attachment 26827 [details]
updated patch

Doesn't address the issue of what to call the methods, but introduces a generic binary search method on any list object responding to .length and array notation.

Methods for both indexOf and insertionIndexFor. The implementation is the same except the return value, so makes sense to simply provide both.
Comment 9 Timothy Hatcher 2009-02-03 13:22:18 PST
Comment on attachment 26827 [details]
updated patch

The code looks fine, but there are some coding style inconsistencies.

> +        if (select.childNodes)
> +        {

Brace should be on the same line as the if.

> +    while (first <= last)
> +    {

Brace should be on the same line as the while.

> +        else
> +        {

Brace should be on the same line as the else.

> +    return -first-1;

Should be spaces around the subtraction minus sign.

I will fix these up when I land the patch, since I feel bad for letting this sit in review so long.
Comment 10 Timothy Hatcher 2009-03-01 08:53:55 PST
Landed in r41335.