Bug 23395 – Web Inpsector Debugger's Source List Should Be Sorted

• Component: Web Inspector (Deprecated)
• Status: RESOLVED FIXED

[boucher]

Currently the list of sources isn't in any order. They should be sorted alphabetically.

[boucher]

Created attachment 26813 [details]
Patch that sorts alphabetically.

I'll attach a simple test case as well.

[boucher]

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.

[Oliver Hunt]

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.

[boucher]

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.

[boucher]

Created attachment 26823 [details]
accidentally neglected to update the change log

[Oliver Hunt]

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.

[boucher]

Created attachment 26826 [details]
updated test case with more items

[boucher]

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.

[Timothy Hatcher]

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.

[Timothy Hatcher]

Landed in r41335.