Bug 5227 – Array indexOf() extension for JavaScript 1.5 Core

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Justin Haygood]

Implements indexOf()

Can't test since JSCore on Win32 is b0rked.

Testcases are attatched, however they aren't in the right form. I know the
geniuses there at Apple can properly format it tho!

[Justin Haygood]

Created attachment 4137 [details]
Adds indexOf support to Array object

[Justin Haygood]

Created attachment 4138 [details]
Testcase

Testcase.. works perfectly in Firefox 1.4 (using Gecko 1.8b4)

[Justin Haygood]

Created attachment 4139 [details]
Adds indexOf support to Array object

Silly rabbit, you have to break out of a case or it'll fall through!

[Eric Seidel (no email)]

Comment on attachment 4139 [details]
Adds indexOf support to Array object

-	   Every, ForEach, Some };
+		  Every, ForEach, Some, IndexOf };

Has tabs instead of spaces.  Please fix that first.

Also, please include your test case as part of the diff (make landing easier).

Also your if statements do not follow the coding guidlines (one line ifs have
no {}:
http://webkit.opendarwin.org/blog/?page_id=25

Please correct these small oversights and resubmit.  Thanks for the patch!

[Justin Haygood]

Created attachment 4147 [details]
Fixes Complaints

[Justin Haygood]

Created attachment 4148 [details]
Testcase

Testcase. I can't include it as part of the cvs diff, since I don't have a Mac
to use cvs-create-patch on (it doesn't like Windows)

[Justin Haygood]

Created attachment 4149 [details]
Expected Results of Testcase

[Eric Seidel (no email)]

Comment on attachment 4147 [details]
Fixes Complaints

As I said on IRC:

1.  Basically all of the comments should go away.  Comments rot even faster
than code.  The goal is to make your code as readable as possible.  If you ever
find it too long/too complex to be readable, we suggest using static inline
functions with descriptive names.

2.  if statements shoudl be broken into two lines, per our coding style
guidelines:
http://webkit.opendarwin.org/blog/?page_id=25

if (foo) doFoo();
should be
if (foo)
    doFoo();

[Justin Haygood]

Created attachment 4152 [details]
Implements indexOf

[Justin Haygood]

Comment on attachment 4152 [details]
Implements indexOf

* Uses a better check for equality than before (thank you MacDome!)
* Follows Code Style Guidelines
* Gets Rid of All Junk Comments

[Justin Haygood]

Created attachment 4153 [details]
implements indexof

Bla, Forgot one if

[Eric Seidel (no email)]

Comment on attachment 4153 [details]
implements indexof

We discussed this on IRC more.	this one fails to return correctly when value
not found.  I also suggested renaming index to indexFrom, and a cleaner way to
have the if statements.

[Justin Haygood]

Created attachment 4157 [details]
Implements indexOf, addressing all concerns hopefully :-D

Test Case Coming Soon

[Darin Adler]

Comment on attachment 4157 [details]
Implements indexOf, addressing all concerns hopefully :-D

Thanks for your work on this! There are still a few things to fix and
investigate.

JavaScript method implementations should almost never look at the size of the
args array. That's because most methods ignore extra arguments. By checking
specifically for a size of 2, this method won't ignore such extra arguments
properly.

We need to test Gecko with extra arguments to see what the desired behavior is
for compatibility.

I'd suggest simply checking args[1] to see if it's undefined, rather than
looking at args.size(). The list class always gives undefined rather than doing
something bad when you use an index greater than the end of the list, for just
this reason.

The code to call throwError should return after the call. Despite its name,
throwError does not do a C++ throw, and we don't want to fall into the
subsequent code.

There's no need for a break after a return statement, so that should be
removed.

We need a test case for when indexOf is called with no arguments at all. Does
it find the index of "undefined" in the test array in that case or does it do
something else? What about when the looked-for thing is "null"? Does that match
"undefined" or not? We also need test cases for when it's called with extra
arguments.

I also think it's slightly ugly to have a local variable called fromIndex yet
use it for indexing through the entire array in a loop. Instead perhaps it
should be named something like "i" or "index".

We need a test case for when the index is a very large number, too large to fit
in a 32-bit integer, and a very small number, too small to fit. Also for
negative and positive infinity as well as NaN and negative 0. Note how
functions like splice use a double rather than an int to hold the index when
doing the range check and how they use toInteger rather than toUInt32. There's
a reason for that, which is handling very large or very small numbers; toUInt32
will instead return 0 or a value that's modulo the range of 32-bit integers,
which is almost certainly incorrect.

[Justin Haygood]

(In reply to comment #14)
> (From update of attachment 4157 [details] [edit])
> Thanks for your work on this! There are still a few things to fix and
> investigate.
> 
> JavaScript method implementations should almost never look at the size of the
> args array. That's because most methods ignore extra arguments. By checking
> specifically for a size of 2, this method won't ignore such extra arguments
> properly.

Changed. Gecko ignores extra arguments
> 
> We need to test Gecko with extra arguments to see what the desired behavior is
> for compatibility.
> 
> I'd suggest simply checking args[1] to see if it's undefined, rather than
> looking at args.size(). The list class always gives undefined rather than doing
> something bad when you use an index greater than the end of the list, for just
> this reason.
> 
> The code to call throwError should return after the call. Despite its name,
> throwError does not do a C++ throw, and we don't want to fall into the
> subsequent code.
> 
> There's no need for a break after a return statement, so that should be
> removed.
> 
> We need a test case for when indexOf is called with no arguments at all. Does
> it find the index of "undefined" in the test array in that case or does it do
> something else? What about when the looked-for thing is "null"? Does that match
> "undefined" or not? We also need test cases for when it's called with extra
> arguments.

Gecko returns -1.

> 
> I also think it's slightly ugly to have a local variable called fromIndex yet
> use it for indexing through the entire array in a loop. Instead perhaps it
> should be named something like "i" or "index".

I originally had it index. Blame MacDome for the fromIndex suggestion. I prefer
index as well.

> 
> We need a test case for when the index is a very large number, too large to fit
> in a 32-bit integer, and a very small number, too small to fit. Also for
> negative and positive infinity as well as NaN and negative 0. Note how
> functions like splice use a double rather than an int to hold the index when
> doing the range check and how they use toInteger rather than toUInt32. There's
> a reason for that, which is handling very large or very small numbers; toUInt32
> will instead return 0 or a value that's modulo the range of 32-bit integers,
> which is almost certainly incorrect.
> 

It uses double now. I have it following Gecko's lead here.

Patch and TestCase coming right up.

[Justin Haygood]

Created attachment 4182 [details]
indexOf compatible with Gecko.

All of Darin's suggestions have been rolled in. It also has a few safety
catches to make it safer to call and not crash or do some weird thing.

[Justin Haygood]

Created attachment 4183 [details]
Testcase

Updated testcase

[Justin Haygood]

Created attachment 4184 [details]
Updated Expected Results, taken using Gecko's lead

[Maciej Stachowiak]

Throwing a range error when the from index is negative even after adding the length is wrong. Gecko 
docs say:

"If the calculated index is less than 0, the whole array will be searched."

And this matches Firefox behavior.

Please fix this point and add a test case for a negative range bigger than the size of the array (since the 
current tests aren't covering this case). I also suggest testing a discontiguous array.

And finally, one of the if statements still has spaces inside the ifs.

Patch looks good, other than this one bug and the style issue.

[Justin Haygood]

Created attachment 4236 [details]
indexOf Compatible with Gecko, addresses concerns made by mjs, fixes style issues

Only one problem I have with this patch. I had to remove the NaN test from the
patch, since someone removed ConstantValues::NaN, so if it fails due to it not
being a number, don't blame me :-D

[Justin Haygood]

Created attachment 4237 [details]
Updated Testcase

It adds a testcase for that one missing item. Don't know what a discontiguous
array is

[Justin Haygood]

Created attachment 4238 [details]
Updated Expected Results (Taken using Firefox 1.4.1)

Taken using Firefox 1.4.1, as per the lead we want to follow.

[Darin Adler]

Comment on attachment 4236 [details]
indexOf Compatible with Gecko, addresses concerns made by mjs, fixes style issues

There's a missing space after the first if before the "(" character. Must fix
that.

The right way to check if something is undefined is to use the isUndefined()
function rather than checking != explicitly against ConstantValues::undefined.
Probably OK this way, but not idiomatic.

The check of args[0] against undefined could just do an early return rather
than if/else. Just a suggestion: optional.

[Justin Haygood]

Created attachment 4246 [details]
indexOf Compatible with Gecko

Anything else need changing?

[Darin Adler]

Comment on attachment 4246 [details]
indexOf Compatible with Gecko

I'm sorry to be such a pain. This is nearly perfect, but...

+    if (args[1]->isUndefined() == false) {

The above should be !args[1]->isUndefined() -- we don't use == false for
booleans.

+    else
+	 searchElement = args[0];

The above should not include the optional else; since the if case returns
there's no need to have an else.

Otherwise, ready to go!

[Justin Haygood]

Created attachment 4270 [details]
indexOf Compatible with Gecko

Please let this be the last one!

[Darin Adler]

Comment on attachment 4270 [details]
indexOf Compatible with Gecko

r=me

[Darin Adler]

I did more testing, and this final version does not correctly match Gecko. I added more test cases to 
demonstrate ways it falls short and I have a revised version of my own.

[Darin Adler]

Comment on attachment 4270 [details]
indexOf Compatible with Gecko

Testing this one I see that it actually crashes on the test case. I have made a
revised version of both the function and the test.

[Darin Adler]

Created attachment 4277 [details]
new patch, including the test case

Here's what I did:

- added null and undefined elements to the test case array to test behavior in
those cases
- removed special case for an undefined arg0, because Gecko's behavior is to
search for an undefined value
- changed the length of the function from 2 to 1, because that's the length in
Gecko
- changed the type of the index used in the loop to unsigned, and just used
double when processing the fromIndex argument, being careful to handle
overflow, underflow, and NaN correctly
- added a check for a null pointer for the result of getProperty, since that's
what we get for missing array elements (was causing a crash)
- made the early exit from the loop just use a return to eliminate the need to
check index outside the loop

There are still some minor loose ends I think. The test doesn't test multiple
elements in the array with the same value, nor is there a good test to ensure
that the comparison done by strictEqual is the right one.

[Justin Haygood]

> There are still some minor loose ends I think. The test doesn't test multiple
> elements in the array with the same value, nor is there a good test to ensure
> that the comparison done by strictEqual is the right one.

Well, you only need to know the address of the first element with the same
value, it should return the second it finds it, so that's not a loose end.

[Eric Seidel (no email)]

Comment on attachment 4277 [details]
new patch, including the test case

Personally I would have chosen something other than "d" as a variable name, as
it's often used as the "private" pointer in impls (it's also not very
descriptive).

2.  Why set e = jsUndefined() and then check equals?  Under what conditions
does getProperty fail (return NULL) such that matching that index with
undefined is OK?

Otherwise looks good.

[Darin Adler]

I like "d" for this -- it's used the same way elsewhere in JavaScriptCore. But I could be convinced otherwise 
in a pinch.

[Eric Seidel (no email)]

Comment on attachment 4277 [details]
new patch, including the test case

Darin notes on IRC we're missing at least a few more tests:

1.  where the array has more than one of the same value
2. where the target is another object using the array prototype
3. "===" rule vs. "==" rule.

The code looks fine.  Justin, please add these 3 more tests, and we'll land.

[Darin Adler]

I added the additional testing, and I'm going to land this now.