Last Comment Bug 310425 - Array.indexOf/lastIndexOf is broken for corner cases
: Array.indexOf/lastIndexOf is broken for corner cases
Status: RESOLVED FIXED
[needs SR shaver]
: fixed1.8, js1.6
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: P1 normal (vote)
: mozilla1.8beta5
Assigned To: Brendan Eich [:brendan]
:
: Jason Orendorff [:jorendorff]
Mentors:
javascript:alert("Expected result is ...
Depends on: 311082
Blocks:
  Show dependency treegraph
 
Reported: 2005-09-29 02:20 PDT by Igor Bukanov
Modified: 2011-08-05 21:32 PDT (History)
5 users (show)
brendan: blocking1.8b5+
brendan: blocking1.8rc1+
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Fix (5.31 KB, patch)
2005-09-29 02:39 PDT, Igor Bukanov
no flags Details | Diff | Splinter Review
based on igor's patch, consolidates IndexToId|PropertyExists (18.52 KB, patch)
2005-09-29 04:13 PDT, Brendan Eich [:brendan]
no flags Details | Diff | Splinter Review
diff -w version of last patch (15.76 KB, patch)
2005-09-29 04:15 PDT, Brendan Eich [:brendan]
mrbkap: review+
Details | Diff | Splinter Review
interdiff against attachment 197832 (444 bytes, patch)
2005-10-01 20:49 PDT, Brendan Eich [:brendan]
brendan: review+
shaver: superreview+
Details | Diff | Splinter Review
final patch in full (19.19 KB, patch)
2005-10-01 20:52 PDT, Brendan Eich [:brendan]
brendan: review+
brendan: superreview+
mscott: approval1.8b5+
Details | Diff | Splinter Review
followup iloop fix -w (980 bytes, patch)
2005-10-07 16:40 PDT, Blake Kaplan (:mrbkap) (PTO until Jan. 2, 2017)
no flags Details | Diff | Splinter Review
fix my blunder (1.26 KB, patch)
2005-10-07 16:41 PDT, Brendan Eich [:brendan]
igor: review+
mrbkap: review+
shaver: superreview+
asa: approval1.8rc1+
Details | Diff | Splinter Review

Description Igor Bukanov 2005-09-29 02:20:46 PDT
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] 2005-09-29 02:25:09 PDT
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 2005-09-29 02:39:40 PDT
Created attachment 197826 [details] [diff] [review]
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] 2005-09-29 04:13:57 PDT
Created attachment 197832 [details] [diff] [review]
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] 2005-09-29 04:15:20 PDT
Created attachment 197834 [details] [diff] [review]
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] 2005-09-29 04:26:56 PDT
Thanks again, Igor!  You helping Norris get these implemented in Rhino, by any
chance? ;-)

/be
Comment 6 Igor Bukanov 2005-09-29 06:35:00 PDT
(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 2005-09-29 06:38:49 PDT
(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 -- probably not reading bugmail closely) 2005-09-29 16:14:49 PDT
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) (PTO until Jan. 2, 2017) 2005-09-30 17:00:50 PDT
Comment on attachment 197834 [details] [diff] [review]
diff -w version of last patch

Very cool. r=mrbkap
Comment 10 Asa Dotzler [:asa] 2005-09-30 18:23:07 PDT
we need to get that super-review here if it's going to make 1.5. 
Comment 11 Brendan Eich [:brendan] 2005-10-01 20:49:38 PDT
Created attachment 198186 [details] [diff] [review]
interdiff against attachment 197832 [details] [diff] [review]

Add hole test to array_extra.

/be
Comment 12 Brendan Eich [:brendan] 2005-10-01 20:52:03 PDT
Created attachment 198187 [details] [diff] [review]
final patch in full
Comment 13 Mike Shaver (:shaver -- probably not reading bugmail closely) 2005-10-01 20:52:19 PDT
Comment on attachment 198186 [details] [diff] [review]
interdiff against attachment 197832 [details] [diff] [review]

sr=shaver, thanks.
Comment 14 Brendan Eich [:brendan] 2005-10-01 23:29:07 PDT
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 2005-10-02 12:33:25 PDT
Comment on attachment 198187 [details] [diff] [review]
final patch in full

approving for the branch.
Comment 16 Brendan Eich [:brendan] 2005-10-02 20:08:25 PDT
Fixed on the 1.8 branch too -- thanks.

/be
Comment 17 Igor Bukanov 2005-10-07 16:27:20 PDT
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) (PTO until Jan. 2, 2017) 2005-10-07 16:40:28 PDT
Created attachment 198856 [details] [diff] [review]
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] 2005-10-07 16:41:18 PDT
Created attachment 198857 [details] [diff] [review]
fix my blunder

Sorry about that, stupid mistake.

/be
Comment 20 Brendan Eich [:brendan] 2005-10-07 16:42:50 PDT
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] 2005-10-07 16:43:49 PDT
Need more testsuite coverage, obviously.  And need a new brain, mine's worn out!

/be
Comment 22 Blake Kaplan (:mrbkap) (PTO until Jan. 2, 2017) 2005-10-07 16:45:37 PDT
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] 2005-10-07 16:48:25 PDT
(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] 2005-10-08 23:15:54 PDT
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] 2005-10-08 23:18:54 PDT
Fixed on trunk.

/be
Comment 26 Bob Clary [:bc:] 2005-10-09 21:41:16 PDT
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] 2005-10-10 21:31:05 PDT
Oops, added fixed1.8 prematurely(!).  Fixed on the branch now.

/be
Comment 28 Brendan Eich [:brendan] 2005-11-07 23:40:08 PST
Patch caused bug 315509, in spite of review and testsuite.  Sorry about that.

/be
Comment 29 Igor Bukanov 2005-11-08 02:49:25 PST
(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 -- probably not reading bugmail closely) 2005-12-10 09:35:39 PST
Comment on attachment 198857 [details] [diff] [review]
fix my blunder

sr=shaver, too late to matter.

Note You need to log in before you can comment on or make changes to this bug.