Array.indexOf/lastIndexOf is broken for corner cases

RESOLVED FIXED in mozilla1.8beta5

Status

()

Core
JavaScript Engine
P1
normal
RESOLVED FIXED
12 years ago
6 years ago

People

(Reporter: Igor Bukanov, Assigned: brendan)

Tracking

({fixed1.8, js1.6})

Trunk
mozilla1.8beta5
fixed1.8, js1.6
Points:
---
Bug Flags:
blocking1.8b5 +
blocking1.8rc1 +
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [needs SR shaver], URL)

Attachments

(6 attachments, 1 obsolete attachment)

(Reporter)

Description

12 years ago
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.
(Assignee)

Comment 1

12 years ago
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
Flags: blocking1.8b5+
Keywords: js1.6
OS: Linux → All
Priority: -- → P1
Hardware: PC → All
Target Milestone: --- → mozilla1.8beta5
(Reporter)

Comment 2

12 years ago
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.
(Assignee)

Comment 3

12 years ago
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
(Assignee)

Comment 4

12 years ago
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
Attachment #197834 - Flags: superreview?(shaver)
Attachment #197834 - Flags: review?(mrbkap)
(Assignee)

Comment 5

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

/be
(Reporter)

Comment 6

12 years ago
(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.
(Reporter)

Comment 7

12 years ago
(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.
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 on attachment 197834 [details] [diff] [review]
diff -w version of last patch

Very cool. r=mrbkap
Attachment #197834 - Flags: review?(mrbkap) → review+

Comment 10

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

Updated

12 years ago
Whiteboard: [needs SR shaver]
(Assignee)

Comment 11

12 years ago
Created attachment 198186 [details] [diff] [review]
interdiff against attachment 197832 [details] [diff] [review]

Add hole test to array_extra.

/be
Attachment #198186 - Flags: superreview?(shaver)
Attachment #198186 - Flags: review+
(Assignee)

Comment 12

12 years ago
Created attachment 198187 [details] [diff] [review]
final patch in full
Comment on attachment 198186 [details] [diff] [review]
interdiff against attachment 197832 [details] [diff] [review]

sr=shaver, thanks.
Attachment #198186 - Flags: superreview?(shaver) → superreview+
(Assignee)

Comment 14

12 years ago
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
Assignee: general → brendan
(Assignee)

Updated

12 years ago
Attachment #198187 - Flags: superreview+
Attachment #198187 - Flags: review+
Attachment #198187 - Flags: approval1.8b5?

Comment 15

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

approving for the branch.
Attachment #198187 - Flags: approval1.8b5? → approval1.8b5+
(Assignee)

Comment 16

12 years ago
Fixed on the 1.8 branch too -- thanks.

/be
Status: NEW → RESOLVED
Last Resolved: 12 years ago
Keywords: fixed1.8
Resolution: --- → FIXED

Updated

12 years ago
Attachment #197834 - Flags: superreview?(shaver)

Updated

12 years ago
Depends on: 311082
(Reporter)

Comment 17

12 years ago
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]  ;)
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
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.
Attachment #198856 - Flags: review?(brendan)
(Assignee)

Comment 19

12 years ago
Created attachment 198857 [details] [diff] [review]
fix my blunder

Sorry about that, stupid mistake.

/be
Attachment #198857 - Flags: superreview?(shaver)
Attachment #198857 - Flags: review?(igor3)
Attachment #198857 - Flags: approval1.8rc1?
(Assignee)

Comment 20

12 years ago
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
Status: REOPENED → ASSIGNED
Flags: blocking1.8rc1+
(Assignee)

Comment 21

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

/be
Flags: testcase?
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.
Attachment #198857 - Flags: review+
(Assignee)

Comment 23

12 years ago
(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

Updated

12 years ago
Attachment #198856 - Attachment is obsolete: true
Attachment #198856 - Flags: review?(brendan)
(Assignee)

Updated

12 years ago
Attachment #198857 - Flags: review?(igor3) → review?(igor.bukanov)
(Assignee)

Comment 24

12 years ago
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
(Assignee)

Comment 25

12 years ago
Fixed on trunk.

/be
Status: ASSIGNED → RESOLVED
Last Resolved: 12 years ago12 years ago
Resolution: --- → FIXED
(Reporter)

Updated

12 years ago
Attachment #198857 - Flags: review?(igor.bukanov) → review+

Comment 26

12 years ago
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
Flags: testcase? → testcase+

Updated

12 years ago
Attachment #198857 - Flags: approval1.8rc1? → approval1.8rc1+
(Assignee)

Comment 27

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

/be
(Assignee)

Comment 28

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

/be
(Reporter)

Comment 29

12 years ago
(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 on attachment 198857 [details] [diff] [review]
fix my blunder

sr=shaver, too late to matter.
Attachment #198857 - Flags: superreview?(shaver) → superreview+
You need to log in before you can comment on or make changes to this bug.