310425 - Array.indexOf/lastIndexOf is broken for corner cases

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Igor Bukanov]

The current implementation of Array.indexOf/ Array.lastIndexOf has the following
2 issues:

1. [].lastIndexOf(undefined, -1) gives 0 instead of -1. This is due to
lastIndexOf implementation always querying array[0] for negative indexes even if
length is 0.

2. var x = []; x[1 << 30] = 1; var index = x.lastIndexOf(1); sets index to
undefined, not 1 << 30, since code assumes that array index would always fit
JSVAL_INT_MAX. Thus it would return INT_TO_JSVAL(1 << 30) which is JSVAL_VOID.

Similar problem holds for indexOf but it would really long time to run
x.indexOf() since the code would loop through 1 << 30 non-existing elements.

Comment 1

[Brendan Eich [:brendan]]

Thanks for filing this -- not sure shaver is able to jump on it.  I'm in
Tallinn, Estonia for ACM ICFP, but may take a crack at fixing it.

/be

Comment 2

[Igor Bukanov]

Attachment: Fix

Patch consolidates indexOf/lastIndexOf implementation into single
array_indexOfHelper which immediately returns -1 for array with length 0.
Otherwise it runs the search loop that would properly wrap found index into
JSVAL.

Comment 3

[Brendan Eich [:brendan]]

Attachment: based on igor's patch, consolidates IndexToId|PropertyExists

Also cleans up a few minor things from the old days.  Just to cut down on code
size a bit more, use js_NewNumberValue in array_indexOfHelper.

/be

Comment 4

[Brendan Eich [:brendan]]

Attachment: diff -w version of last patch

This should be good for 1.8b5 with a little review and testing (someone run the
testsuite, my battery's low here!).

/be

Comment 5

[Brendan Eich [:brendan]]

Thanks again, Igor!  You helping Norris get these implemented in Rhino, by any
chance? ;-)

/be

Comment 6

[Igor Bukanov]

(In reply to comment #5)
> You helping Norris get these implemented in Rhino, by any chance? ;-)

This was how I discovered the bug trying to get semantics of the extras from
jsarray.c to copy it into bug 310323 and bug 310342.

Comment 7

[Igor Bukanov]

(In reply to comment #3)
> Also cleans up a few minor things from the old days.  Just to cut down on code
> size a bit more, use js_NewNumberValue in array_indexOfHelper.

But should then foreach and friend also skip over non-existing indexes for
consistency with the rest of code? It would also speedup that
Array(UINT_MAX).forEach(...) from bug 310405.

Comment 8

[Mike Shaver (:shaver emeritus)]

Yes, I think we do want to be consistent here.  indexOf and lastIndexOf aren't
explicitly specified here, but the docs for forEach say that the array is
treated as "dense":

http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:forEach#Description

I'm happy to rev that, though it's late in the game to get that into Firefox 1.5.

Comment 9

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 197834 [details] [diff] [review]
diff -w version of last patch

Very cool. r=mrbkap

Comment 10

[Asa Dotzler [:asa]]

we need to get that super-review here if it's going to make 1.5. 

Comment 11

[Brendan Eich [:brendan]]

Attachment: interdiff against attachment 197832

Add hole test to array_extra.

/be

Comment 12

[Brendan Eich [:brendan]]

Attachment: final patch in full

Comment 13

[Mike Shaver (:shaver emeritus)]

Comment on attachment 198186 [details] [diff] [review]
interdiff against attachment 197832 [details] [diff] [review]

sr=shaver, thanks.

Comment 14

[Brendan Eich [:brendan]]

Asa, we're doing extra reviews voluntarily, js/src requires only one level.  I
just checked this patch into the trunk.  It should go into the 1.8 branch ASAP.

/be

Comment 15

[Scott MacGregor]

Comment on attachment 198187 [details] [diff] [review]
final patch in full

approving for the branch.

Comment 16

[Brendan Eich [:brendan]]

Fixed on the 1.8 branch too -- thanks.

/be

Comment 17

[Igor Bukanov]

The committed "fix" added infinite loop bug for any array with holes like in

Array(1).indexOf(1)

oo was not in the attachment 197826 [details] [diff] [review]  ;)

Comment 18

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: followup iloop fix -w

I don't know if Igor was going to attach a fix, but this does the trick.

Comment 19

[Brendan Eich [:brendan]]

Attachment: fix my blunder

Sorry about that, stupid mistake.

/be

Comment 20

[Brendan Eich [:brendan]]

mrbkap, sorry -- no IRC connection here, didn't know you were patching too.  I
restored the better loop structure Igor's original patch used, so I'd rather go
with that.  Feel free to review too.

/be

Comment 21

[Brendan Eich [:brendan]]

Need more testsuite coverage, obviously.  And need a new brain, mine's worn out!

/be

Comment 22

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 198857 [details] [diff] [review]
fix my blunder

Our patches are actually equivilant, with yours simply moving the incrementing
condition out of the loop header... It's a matter of style at this point.

Comment 23

[Brendan Eich [:brendan]]

(In reply to comment #22)
> (From update of attachment 198857 [details] [diff] [review] [edit])
> Our patches are actually equivilant, with yours simply moving the incrementing
> condition out of the loop header... It's a matter of style at this point.

Yeah, that's what I said ("better loop structure").  Igor's style wins.  If you
can't put something in most parts of for (;;), it's better to put nothing in any
part.  Or so I always say!  (I think ken and dmr agree... ;-)

/be

Comment 24

[Brendan Eich [:brendan]]

Fixed on trunk (r=mrbkap suffices).

Happy to get extra reviewe, but mrbkap's should suffice for the branch too. 
This bug should be fixed for 1.8 / Firefox 1.5.

/be

Comment 25

[Brendan Eich [:brendan]]

Fixed on trunk.

/be

Comment 26

[Bob Clary [:bc] (inactive)]

Checking in regress-310425-01.js;
/cvsroot/mozilla/js/tests/js1_6/Array/regress-310425-01.js,v  <-- 
regress-310425-01.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/js1_6/Array/regress-310425-02.js,v
done
Checking in regress-310425-02.js;
/cvsroot/mozilla/js/tests/js1_6/Array/regress-310425-02.js,v  <-- 
regress-310425-02.js
initial revision: 1.1
done

Comment 27

[Brendan Eich [:brendan]]

Oops, added fixed1.8 prematurely(!).  Fixed on the branch now.

/be

Comment 28

[Brendan Eich [:brendan]]

Patch caused bug 315509, in spite of review and testsuite.  Sorry about that.

/be

Comment 29

[Igor Bukanov]

(In reply to comment #28)
> Patch caused bug 315509, in spite of review and testsuite.  Sorry about that.
> 
> /be
> 

If one passes -O3 to GCC, then it prints:

jsarray.c: In function ‘array_unshift’:
jsarray.c:1117: warning: ‘id2’ may be used uninitialized in this function

Unfortunately -O or even -O2/-Os is not enough to trigger this warning with GCC 4.0.1 :(

Comment 30

[Mike Shaver (:shaver emeritus)]

Comment on attachment 198857 [details] [diff] [review]
fix my blunder

sr=shaver, too late to matter.