Bug 27329 - Inspector: Properties Should be Sorted more Naturally
Summary: Inspector: Properties Should be Sorted more Naturally
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: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-07-15 21:35 PDT by Joseph Pecoraro
Modified: 2009-07-25 02:45 PDT (History)
3 users (show)

See Also:


Attachments
Sort Properties with the Alphanum Sort (2.37 KB, patch)
2009-07-15 21:39 PDT, Joseph Pecoraro
oliver: review-
Details | Formatted Diff | Diff
Comparison Of The Two Sorts (68.35 KB, image/png)
2009-07-15 21:40 PDT, Joseph Pecoraro
no flags Details
The Alphanum Algorithm and Sample Tests (1.93 KB, application/x-javascript)
2009-07-15 21:42 PDT, Joseph Pecoraro
no flags Details
Benchmark for my "number" test (1.30 KB, application/x-javascript)
2009-07-15 21:51 PDT, Joseph Pecoraro
no flags Details
Best Way to Sort Leading Zeros? (98.22 KB, image/png)
2009-07-16 07:49 PDT, Joseph Pecoraro
no flags Details
AlphaNumSort (Like Finder on leading zeros) (2.64 KB, patch)
2009-07-16 08:36 PDT, Joseph Pecoraro
joepeck: review-
Details | Formatted Diff | Diff
Sort is Applied Correctly, only When Displaying (4.09 KB, patch)
2009-07-16 09:35 PDT, Joseph Pecoraro
timothy: review-
Details | Formatted Diff | Diff
Fixed Based on Review (4.39 KB, patch)
2009-07-23 14:16 PDT, Joseph Pecoraro
no flags Details | Formatted Diff | Diff
Fixed Based on Review (4.38 KB, patch)
2009-07-23 14:17 PDT, Joseph Pecoraro
kmccullough: review+
Details | Formatted Diff | Diff
Improved Comment Based on Review (4.46 KB, patch)
2009-07-24 21:10 PDT, Joseph Pecoraro
oliver: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Joseph Pecoraro 2009-07-15 21:35:34 PDT
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.
Comment 1 Joseph Pecoraro 2009-07-15 21:39:40 PDT
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.
Comment 2 Joseph Pecoraro 2009-07-15 21:40:45 PDT
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.
Comment 3 Joseph Pecoraro 2009-07-15 21:42:16 PDT
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.
Comment 4 Joseph Pecoraro 2009-07-15 21:51:39 PDT
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.
Comment 5 Keishi Hattori 2009-07-16 00:47:40 PDT
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.
Comment 6 Keishi Hattori 2009-07-16 00:53:41 PDT
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.
Comment 7 Oliver Hunt 2009-07-16 01:26:47 PDT
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 @@
> +2009-07-15  Joseph Pecoraro  <joepeck02@gmail.com>
> +
> +        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  <agl@google.com>
>  
>          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
Comment 8 Joseph Pecoraro 2009-07-16 07:46:42 PDT
(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().
Comment 9 Joseph Pecoraro 2009-07-16 07:49:07 PDT
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?
Comment 10 Joseph Pecoraro 2009-07-16 08:36:27 PDT
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.
Comment 11 Joseph Pecoraro 2009-07-16 09:05:44 PDT
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.
Comment 12 Joseph Pecoraro 2009-07-16 09:35:32 PDT
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
...
Comment 13 Eric Seidel (no email) 2009-07-20 15:07:10 PDT
Does this use code from http://www.davekoelle.com/alphanum.html?  if so, it needs to carry that license (LGPL).
Comment 14 Joseph Pecoraro 2009-07-20 15:31:00 PDT
(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.
Comment 15 Timothy Hatcher 2009-07-23 11:46:01 PDT
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.
Comment 16 Joseph Pecoraro 2009-07-23 14:16:16 PDT
Created attachment 33371 [details]
Fixed Based on Review
Comment 17 Joseph Pecoraro 2009-07-23 14:17:58 PDT
Created attachment 33372 [details]
Fixed Based on Review
Comment 18 Joseph Pecoraro 2009-07-23 14:21:39 PDT
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.
Comment 19 Kevin McCullough 2009-07-24 14:36:27 PDT
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.
Comment 20 Joseph Pecoraro 2009-07-24 21:10:34 PDT
Created attachment 33484 [details]
Improved Comment Based on Review
Comment 21 Joseph Pecoraro 2009-07-24 21:11:49 PDT
(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.
Comment 22 Oliver Hunt 2009-07-25 02:45:10 PDT
Committed r46391