Bug 27329 – Inspector: Properties Should be Sorted more Naturally

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

[Joseph Pecoraro]

Properties shown in the console are sorted with the generic Array.sort() which sorts the properties lexicographically and thus numbers sort as though they were strings:

 "0" < "11" < "6" < "a0" < "a11" < "a6"

A more natural sort would be the alphanum sort:
http://www.davekoelle.com/alphanum.html

Thus:

  "0" < "6" < "11" < "a0" < "a6" < "a11"

Much nicer when looking at arrays.

[Joseph Pecoraro]

Created attachment 32829 [details]
Sort Properties with the Alphanum Sort

This algorithm is my own making based on my understanding of how the sort should behave.  No copyright needed.

[Joseph Pecoraro]

Created attachment 32830 [details]
Comparison Of The Two Sorts

This image shows the comparison of the two sorts on an array with more then 10 elements.  Much easier to read and follow the alphanum sorted list.

[Joseph Pecoraro]

Created attachment 32832 [details]
The Alphanum Algorithm and Sample Tests

Some example tests and the algorithm by itself if you want to play around with values.

[Joseph Pecoraro]

Created attachment 32834 [details]
Benchmark for my "number" test

I thought I might just attach this to show why I chose the weird "number" test in the code.  If you think it should be changed to be more readable, that sounds fine to me.  A number of the alternatives are nearly equal in performance.

[Keishi Hattori]

This looked great so I tried it out.

I noticed
alphaNumSort("01", "1")
will cause an error.

Also, I'm not sure why but while your benchmark showed +NUM+1 to be fastest, alphaNumSort was about 30% faster when I replaced "+chunka+1" with "isNaN(chunka)". 
I used your ["1000X Radonius Maximus", "10X Radonius", ...] array and sorted it 1000 times.

[Keishi Hattori]

I'm sorry. My mistake, I left out the "!". Now it seems the speed is about the same. 

(In reply to comment #5)
> This looked great so I tried it out.
> 
> I noticed
> alphaNumSort("01", "1")
> will cause an error.
> 
> Also, I'm not sure why but while your benchmark showed +NUM+1 to be fastest,
> alphaNumSort was about 30% faster when I replaced "+chunka+1" with
> "isNaN(chunka)". 
> I used your ["1000X Radonius Maximus", "10X Radonius", ...] array and sorted it
> 1000 times.

[Oliver Hunt]

Comment on attachment 32829 [details]
Sort Properties with the Alphanum Sort

> Index: WebCore/ChangeLog
> ===================================================================
> --- WebCore/ChangeLog	(revision 45964)
> +++ WebCore/ChangeLog	(working copy)
> @@ -1,3 +1,13 @@
> [phone]  Joseph Pecoraro  <[e-mail]>
> +
> +        Reviewed by NOBODY (OOPS!).
> +
> +        Inspector: Properties Should be Sorted more Naturally
> +        https://bugs.webkit.org/show_bug.cgi?id=27329
> +
> +        * inspector/front-end/utilities.js:
> +        (Object.sortedProperties): added alphaNumSort sorting function
> +
>  2009-07-15  Adam Langley  <[e-mail]>
>  
>          No review: reverting previous change.
> Index: WebCore/inspector/front-end/utilities.js
> ===================================================================
> --- WebCore/inspector/front-end/utilities.js	(revision 45963)
> +++ WebCore/inspector/front-end/utilities.js	(working copy)
> @@ -1,5 +1,5 @@
>  /*
> - * Copyright (C) 2007 Apple Inc.  All rights reserved.
> + * Copyright (C) 2007, 2009 Apple Inc.  All rights reserved.
>   *
>   * Redistribution and use in source and binary forms, with or without
>   * modification, are permitted provided that the following conditions
> @@ -96,10 +96,43 @@ Object.describe = function(obj, abbrevia
>  
>  Object.sortedProperties = function(obj)
>  {
> +
> +    function alphaNumSort(a,b) {
> +        a = a.toString();
> +        b = b.toString();
In our usage alphaNumSort is always passed strings so these toString calls are unnecessary, and are definitely not free, so you shouldn't have them

> +        if (a===b)
should have spaces around ===

> +            return 0;
> +
> +        var diff = 0;
> +        var chunk = /^\d+|^\D+/;
> +        var chunka, chunkb, anum, bnum;
> +        while (diff === 0) {
> +            if (!a && b)
> +                return -1;
> +            if (!b && a)
> +                return 1;
> +            chunka = a.match(chunk)[0];
> +            chunkb = b.match(chunk)[0];
> +            anum = +chunka+1; // quick falsey check if its a number
> +            bnum = +chunkb+1; // quick falsey check if its a number
This seems unnecessarily complex -- why "+1" ?  aside from that the second + should have spaces on either side.

> +            if (anum && !bnum)
> +                return -1;
> +            if (bnum && !anum)
> +                return 1;
> +            if (anum && bnum)
> +                diff = chunka - chunkb;
> +            else if (chunka !== chunkb)
> +                return (chunka<chunkb) ? -1 : 1;
Should have spaces around <

> +            a = a.substring(chunka.length);
> +            b = b.substring(chunkb.length);
> +        }
> +        return diff;
> +    }
> +    

Otherwise this basically seems fine, just needs my comments addressed

[Joseph Pecoraro]

(In reply to comment #5)

> I noticed
>   alphaNumSort("01", "1")
> will cause an error.

Wow, excellent point.  Leading zeros really complicates things.  I just wrote a modified version (unfortunately much dirtier) to be me my desired sort for leading zeros.  However, this may be a little too stringent, as this really is a corner case and I resort to using regex again.

  ["000", "001", "002", "003", "00", "01", "02", "0", "1", "2"]

Note that `ls` and the Finder each produce different results.  I'll attach a picture in a second.


(In reply to comment #6)
> I'm sorry. My mistake, I left out the "!". Now it seems the speed is about the
> same. 

You're right, I just ran the same benchmarks.  Because it is clearer and basically the same performance, I'll switch to !isNaN().


(In reply to comment #7)
> This seems unnecessarily complex -- why "+1" ?  aside from that
> the second + should have spaces on either side.

The + 1 was to prevent 0 from being a "falsey" value because I later use it in an if statement.  However this has been changed to the !isNaN() version.  Cleaner.


> >  Object.sortedProperties = function(obj)
> >  {
> > +
> > +    function alphaNumSort(a,b) {
> > +        a = a.toString();
> > +        b = b.toString();
> In our usage alphaNumSort is always passed strings so these toString calls are
> unnecessary, and are definitely not free, so you shouldn't have them

Done.  This is certainly correct for sortedProperties.  Good catch.  In my generic tests I had all sorts of values.  If somebody feels this is worth leaving a comment "// alphaNumSort only sorts strings" when they land this patch, so anyone wanting to use the sort knows it only works on strings, that might be nice.


> > +        if (a===b)
> should have spaces around ===

Done.  As well as all other style changes.


> Otherwise this basically seems fine, just needs my comments addressed

Thanks for the review.  Good catch on the toString().

[Joseph Pecoraro]

Created attachment 32871 [details]
Best Way to Sort Leading Zeros?

My algorithm, `ls`, and Finder all sort differently.  Which would be the best to use?

[Joseph Pecoraro]

Created attachment 32873 [details]
AlphaNumSort (Like Finder on leading zeros)

Keishi liked Finder's sort the best.  And indeed that is probably the best performing because it didn't require using any more regular expressions (although it treats 0 as a special case, which is disappointing but possible to do without regular expressions in the algorithm).  Give this one a shot.

And if you feel as though "!+chunk" is clearer as "!Number(chunk)" then please change it.  I actually prefer the former.

[Joseph Pecoraro]

Comment on attachment 32873 [details]
AlphaNumSort (Like Finder on leading zeros)

Apparently sorting happens in multiple places.

It works for:
obj={a:[0,1,2,3,4,5,6,7,8,9,10,11,12]}

But it doesn't even get run for:
obj = { '0':0, '00':0, '000':0, '01':0, '1':0, '2':0, '02':0, '001':0, '002':0 }

I should look into when sorts are applied.

[Joseph Pecoraro]

Created attachment 32879 [details]
Sort is Applied Correctly, only When Displaying

This only applies the sort when needed in the ObjectPropertiesSection.  Typeahead/Autocompletion uses the default sort().
Both test cases pass:

> obj={a:[0,1,2,3,4,5,6,7,8,9,10,11,12]};
> obj
...

> obj = {'0':0,'00':0,'000':0,'01':0,'1':0,'2':0,'02':0,'001':0,'002':0};
> obj
...

[Eric Seidel (no email)]

Does this use code from http://www.davekoelle.com/alphanum.html?  if so, it needs to carry that license (LGPL).

[Joseph Pecoraro]

(In reply to comment #13)
> Does this use code from http://www.davekoelle.com/alphanum.html?  if so, it
> needs to carry that license (LGPL).

I mentioned that link in the first comment, but I also stated:

(In comment #2)
> This algorithm is my own making based on my understanding of how
> the sort should behave.  No copyright needed.

If you still feel as thought the license should be applied let me know.

[Timothy Hatcher]

Comment on attachment 32879 [details]
Sort is Applied Correctly, only When Displaying

> +                    if ( !+chunka && !+chunkb ) // chunks are strings of all 0s (special case)

No need for spaces on the inside of the parenthesis.

> +            }
> +            else if (chunka !== chunkb)

The else should be on on the same lien as the curly brace.

Maybe move the sort function to Utilities.js so it could be used by other callers?

I think sorting the completions this way would be good too.

[Joseph Pecoraro]

Created attachment 33371 [details]
Fixed Based on Review

[Joseph Pecoraro]

Created attachment 33372 [details]
Fixed Based on Review

[Joseph Pecoraro]

NOTES:
 - I removed the "==" because no two Object Properties are going to be the same.

(In reply to comment #15)
> No need for spaces on the inside of the parenthesis.

Done.


> The else should be on on the same line as the curly brace.

Done.


> Maybe move the sort function to Utilities.js so it could be used by other
> callers?

Because this sort is specialized to work on Strings and where no two objects passed in are going to be equal, I kept this inside ObjectProperties with a comment on how to make it more generic.  If you'd rather put the generic version into utilities (performance aside) then let me know.


> I think sorting the completions this way would be good too.

I assume (untested) that a javascript based sort like this would run much slower then the built-in sort.  Since the auto-completion runs quite often I decided to keep the completion using the default sort.

[Kevin McCullough]

Comment on attachment 33372 [details]
Fixed Based on Review


> +        //  - check if a == b

You should add your comment here that you don't need to check 'a == b' because no two object properties are going to be the same thing.

[Joseph Pecoraro]

Created attachment 33484 [details]
Improved Comment Based on Review

[Joseph Pecoraro]

(In reply to comment #19)
> You should add your comment here that you don't need to check 'a == b' because
> no two object properties are going to be the same thing.

Done.

[Oliver Hunt]

Committed r46391