311515 - Skipping holes and undefs while sorting

Status: VERIFIED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

The current implementation of array_sort in jsarray.c includes in the temporally
sorting array unexisting properties (holes) and undefined values and later put
some efforts in sort_compare to ensure hole > undef > any other value.

This can be simplified if holes and undefs would not be included in the working
array but rather just counted. Then after the sorting is done undefs and holes
can be properly inserted at the array end.

Comment 1

[Igor Bukanov]

Attachment: Implementation

Comment 2

[Bob Clary [:bc] (inactive)]

not sure if we have a test for sorting holes/undefined, so just adding this for completeness.

Checking in regress-311515.js;
/cvsroot/mozilla/js/tests/js1_5/Array/regress-311515.js,v  <--  regress-311515.js
initial revision: 1.1
done

Comment 3

[Igor Bukanov]

Comment on attachment 198802 [details] [diff] [review]
Implementation

This is a wrong patch

Comment 4

[Igor Bukanov]

Attachment: Implementation

Comment 5

[Brendan Eich [:brendan]]

Comment on attachment 203678 [details] [diff] [review]
Implementation

Deflecting to mrbkap, who has some jsarray.c major patching under way.

/be

Comment 6

[Igor Bukanov]

Attachment: Implementation (sync with CVS 2006-03-15)

Comment 7

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 215139 [details] [diff] [review]
Implementation (sync with CVS 2006-03-15)

>Index: jsarray.c
>+     * By ECMA 262, 15.4.4.11, undefined property (which we call a "hole")
>+     * always bigger an existing property with value undefined and that

You're missing a couple of words here :-)
By ECMA 262, 15.4.4.11, an undefined property (which we call a "hole") is always bigger than an existing property ...

Looks good otherwise, r=mrbkap.

Comment 8

[Igor Bukanov]

Attachment: Patch to commit with comments fixes.

Comment 9

[Igor Bukanov]

I committed the last patch:

Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.76; previous revision: 3.75
done

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 215165 [details] [diff] [review]
Patch to commit with comments fixes.

>+     * By ECMA 262, 15.4.4.11, an undefined property (which we call a "hole")
>+     * always bigger than an existing property with value undefined and that

Missing "is" before "always bigger".

Also "greater" is better than "bigger", more Mathematical.

>+     * is always bigger then any other property. Thus to sort holes and

s/then/than/

r=me in advance for followup fix if you are game.

/be

Comment 11

[Igor Bukanov]

I committed the spelling fixes:

Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.77; previous revision: 3.76
done

Comment 12

[Igor Bukanov]

Attachment: Patch with spelling fixes

For references here is the patch with all spelling fixes incorporated.

Comment 13

[Bob Clary [:bc] (inactive)]

verified fixed 20060609 win/macppc/linux trunk.