Vassil Baroff - Ratola Corp Reporter
	Description • 18 years ago

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1) Gecko/20061024 Iceweasel/2.0 (Debian-2.0+dfsg-1)
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1) Gecko/20061024 Iceweasel/2.0 (Debian-2.0+dfsg-1)

Array.indexOf does not behave as expected. If the last element of the array is equal to the argument of indexOf it leads to an endless loop:

//Sample 1
	var indices = [];
	var haystack = [2,3,2];// if last element = needle
	var needle = 2;
	var idx = haystack.indexOf(needle);
	while (idx != -1) {
		indices.push(idx);
		idx = haystack.indexOf(needle, idx + 1);
	}
	alert(idx + ' idx');// Endless loop

//Sample 2
	var indices = [];
	var haystack = [2,3,2,5];// if last element != needle
	var needle = 2;
	var idx = haystack.indexOf(needle);
	while (idx != -1) {
		indices.push(idx);
		idx = haystack.indexOf(needle, idx + 1);
	}
	alert(idx + ' idx');// Works Ok

//Sample 3
	var indices = [];
	var haystack = [2,3,2];
	var haystackLength = haystack.length;// Temporary work around
	var needle = 2;
	var idx = haystack.indexOf(needle);
	while (idx != -1) {
		indices.push(idx);
		idx = haystack.indexOf(needle, idx + 1);
		if (idx == haystackLength-1){break;}// Temporary work around
	}
	alert(idx + ' idx');

Reproducible: Always

	Andrew Schultz
	Comment 1 • 18 years ago

With a current trunk build:

js> [2].indexOf(2,1); 
0
(should return -1)

==> Javascript

	Jeff Walden [:Waldo] Assignee
	Comment 2 • 18 years ago

Also fixes the following issue noted while reading the relevant docs:

js> [2, 3].lastIndexOf(2, -5) == -1
false

Since there didn't seem to be a set of exhaustive (lastI|i)ndexOf tests with respect to the second argument in the test suite, I wrote such a set, based on the docs on MDC.  I'll attach them after this patch.

	Jeff Walden [:Waldo] Assignee
	Comment 3 • 18 years ago

I'm not sure exactly what the Initial Developer or Contributors should be to this, since it's mostly my work but was inspired by the original testcases provided by others.  Please fix up as necessary at checkin time.

	Jeff Walden [:Waldo] Assignee
	Comment 4 • 18 years ago

Hrm, so for the lastIndexOf bug there's a problem:

http://developer.mozilla.org/en/docs/index.php?title=Core_JavaScript_1.5_Reference:Global_Objects:Array:lastIndexOf&diff=17901&oldid=15793

I think this was a misguided edit, but I also happen to think the semantics change it makes is *good*.  I think there's a lot of logic in saying that the result of lastIndexOf with a second argument less than or equal to this.length will return -1 -- arbitrary clamping to 0 to return 0 iff the searched-for element is in the zeroth position is thoroughly bizarre.

I've also spent some time looking at other implementations to see what they do, via the limitless power of Google searches (for indexOf and lastIndexOf, to be safe -- they seem to get indexOf right, but lastIndexOf is a bit more spotty).

The first implementations I looked at were <http://erik.eae.net/playground/arrayextras/arrayextras.js> and <http://www.nczonline.net/downloads/zArray.zip>, both written shortly after the first article about JS1.6 (which doesn't mention negative-index semantics at all -- <http://www.webreference.com/programming/javascript/ncz/column4/>).  The first did the clamp-to-zero thing, I believe because it was written before the changes noted above.  The second didn't bother handling a negative start index at all.

While continuing down through Google results for "javascript array indexof", I also stumbled across a Safari bug to implement indexOf.  A little effort to find their lastIndexOf bug found <http://bugs.webkit.org/show_bug.cgi?id=6252>.  They implemented this after the semantics-changing wiki edit above, so according to that they implement [2].lastIndexOf(2, -5) == -1.  (Oddly enough, the way I read it they apparently did this even while noting that Firefox did it differently.)

Further down in Google results I found yet another implementation at <http://www.bigbold.com/snippets/posts/show/718>.  Their implementation uses clamp-to-zero semantics.  Later on, <http://www.dustindiaz.com/basement/sugar-arrays.html> uses the don't-clamp semantics.  <http://www.devpro.it/JSL/JSLOpenSource.js> obfuscates intent a bit but uses don't-clamp semantics.  The implementation at <http://forum.mootools.net/topic.php?id=327&page=3> doesn't clamp to 0.

(Also, for those playing along at home, there's a lastIndexOf function at <http://www.go4expert.com/forums/showthread.php?t=974>, but it doesn't have a second argument at all and thus is irrelevant here.)

Those were all the implementations I found in the first 50 results on Google for "javascript array indexof" and "javascript array lastindexof" (quotes not in actual searches).  I'm not sure there are that many other implementations, because result usability started decaying pretty quickly around result 40 in Google.

Brendan, what, if anything, is TG1 saying about lastIndexOf?  The ES4 wiki seems  to indicate that the array extras haven't yet been or won't be standardized <http://developer.mozilla.org/es4/spec/chapter_19_native_objects.html>, which is vaguely odd.  I'd feel much better if this were to be codified and standardized in some non-wiki document for implementers to read to get a precise definition of semantics.

	Jeff Walden [:Waldo] Assignee
	Comment 5 • 18 years ago

Shaver, seeing as you did the implementation of lastIndexOf, you might have some insight into the lastIndexOf snafu described here.

	Mike Shaver (:shaver emeritus)
	Comment 6 • 18 years ago

I don't have any detailed recollections of this issue, sorry.  What hazy recollections I do have are that lastIndexOf for Array was to ape that of String in its index handling, if that helps.

	Jeff Walden [:Waldo] Assignee
	Comment 7 • 18 years ago

(In reply to comment #6)
> What hazy recollections I do have are that lastIndexOf for Array was to ape
> that of String in its index handling, if that helps.

lastIndexOf doesn't try to make negative numbers map to an offset from the length of the string, so the behaviors aren't quite comparable.  (This is possibly even reasonable, for strings; I haven't thought about it very hard.)  That said, its defined behavior for negative numbers (not just negative and less than the length of the string numbers) is clamp-to-zero, so the following holds:

js> var negativeValue = -1;
js> "f".lastIndexOf("f", negativeValue) == 0
true
js> "af".lastIndexOf("f", negativeValue) == -1
true

String.prototype.lastIndexOf not handling negative indexes makes me think the behaviors aren't sufficiently comparable to say that for index < -length, clamp-to-zero over returning -1 is what should happen, looking at it from a compatibility standpoint.

	Brendan Eich [:brendan]
	Comment 8 • 18 years ago

Comment on attachment 248895 [details] [diff] [review]
Patch

>         if (start < 0) {
>             start += length;
>-            i = (start < 0) ? 0 : (jsuint)start;
>+            if (start < 0) {
>+                if (isLast)
>+                    goto not_found;
>+                else

else after goto is a non-sequitur.

>+                    i = 0;
>+            } else {

It's also arbitrary control flow (the entire rest of the control flow excluded by the goto, not just i = 0;, should be else'ed -- or of course there should be no else (the right answer).

>+                i = (jsuint)start;
>+            }
>         } else if (start >= length) {
>-            i = length - 1;
>+            if (isLast)
>+                i = length - 1;
>+            else
>+                goto not_found;
>         } else {

Ditto.

I wish String.prototype.indexOf and lastIndexOf were more Pythonic:

$ python2.5
>>> "hello".rfind('o', -2)
4
>>> "hello".rfind('o', -6)
4
>>> "hello".rfind('o', -10)
4
>>> "hello".rfind('o', -1)
4
>>> "hello".rfind('l', -1)
-1

We have a chance here to make Array.prototype.*ndexOf better; let's clamp rather than fail.

I'll see about whether we could ever fix the string methods for ES4.

/be

	Brendan Eich [:brendan]
	Comment 9 • 18 years ago

iloop DOS fix, easy to take in patch releases.

/be

	Jeff Walden [:Waldo] Assignee
	Comment 10 • 18 years ago

(In reply to comment #8)
> We have a chance here to make Array.prototype.*ndexOf better; let's clamp
> rather than fail.

To be clear: you're saying that for an index less than the length of the string, Array.prototype.lastIndexOf returns -1, or does it search only the first character?  The patch is the former, but the way I was using the term "clamp" was in reference to the latter.

Also, note that clamping to 0 with Array.prototype.lastIndexOf(needle, index) can't be directly compared to the the clamping Python does: it should be compared to string.rfind(needle, 0, index) -- which for a sufficiently negative index becomes string.rfind(needle, 0, 0) == -1.  JS just omits a third argument and makes the second argument a start for indexOf or an end for lastIndexOf, which is perhaps less consistent but makes lastIndexOf take the index you'd most likely want to use with it.


> iloop DOS fix, easy to take in patch releases.

To be clear, the iloop wasn't in SpiderMonkey but rather in code being run by SpiderMonkey (as a result of the indexing bug fixed by the patch).

Also of note: the example in comment 0 is exactly the last example on <http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:indexOf>, so the example may be in use elsewhere.

	Brendan Eich [:brendan]
	Comment 11 • 18 years ago

Comment on attachment 248951 [details] [diff] [review]
Like this?

Got it, thanks.  We may regret lack of trailing slice args in ES4/JS2, which will support slice syntax.

/be

	Jeff Walden [:Waldo] Assignee
	Comment 12 • 18 years ago

Fixed on trunk.

I'll send an email to the MDC list tomorrow about the change to see if we can figure out why/how it happened.  It's somewhat disturbing that the change in semantics wasn't described in the edit message and also wasn't noticed by people scanning the recent changes feed/pages (especially since that's the only page documenting semantics and has been used by numerous other implementers since the array extras were added to SpiderMonkey).

	Jeff Walden [:Waldo] Assignee
	Comment 13 • 18 years ago

(In reply to comment #12)
> I'll send an email to the MDC list tomorrow

http://groups-beta.google.com/group/mozilla.dev.mdc/browse_frm/thread/4f117202a753fc00/9681431f4da6304e

	Jay Patel [:jay]
	Comment 14 • 18 years ago

Comment on attachment 248951 [details] [diff] [review]
Like this?

Approved for both branches, a=jay for drivers.

	Jeff Walden [:Waldo] Assignee
	Comment 15 • 18 years ago

Fixed on both branches as well.

	Bob Clary [:bc] (inactive)
	Comment 16 • 18 years ago

/cvsroot/mozilla/js/tests/js1_5/Array/regress-364104.js,v  <--  regress-364104.js
initial revision: 1.1

	Bob Clary [:bc] (inactive)
	Comment 17 • 18 years ago

verified fixed 1.8.0, 1.8.1, 1.9.0 2007-01-23 win/mac*/linux