Bug 6252 – JavaScript 1.6 Array.lastIndexOf

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

[Justin Haygood]

Just to match our indexOf implementation, here is the corresponding lastIndexOf.

[Justin Haygood]

Created attachment 5301 [details]
Array.lastIndexOf implementation

Testcases for several edge cases in:

tests/mozilla/js1_6/Array/regress-310425-01.js
tests/mozilla/js1_6/Array/regress-310425-02.js

[Maciej Stachowiak]

Shouldn't index be capped at length - 1, not length, since a[length] is off the end of the array?

+    if (d > 0) {
+        if (d > length)
+            index = length;

(you'd have to cast (length -1) to unsigned since for length 0 it could be -1).

A test case that would see the difference is something like:

a = new Array();
a.length = 1;
alert(a.lastIndexOf(undefined,1));

I think the right answer is 0 but the code here would give 1.

[Maciej Stachowiak]

Comment on attachment 5301 [details]
Array.lastIndexOf implementation

r- due to possible minor bug, otherwise looks fine.

[Justin Haygood]

(In reply to comment #3)
> (From update of attachment 5301 [details] [edit])
> r- due to possible minor bug, otherwise looks fine.
> 
javascript:var a = new Array();a.length=1;alert(a.lastIndexOf(undefined,1))
gives me an alert with -1.

[David Kilzer (:ddkilzer)]

*** Bug 5382 has been marked as a duplicate of this bug. ***

[Justin Haygood]

Created attachment 6777 [details]
Updated lastIndexOf implementation

Updated implementation, should take care of the minor bug. No testcase yet, not even tested until I get a replacement machine.

[Darin Adler]

Comment on attachment 6777 [details]
Updated lastIndexOf implementation

This code looks like it won't work in a couple of ways:

    1) If 0 is passed it looks like it will search the entire array, but that's not what the documentation seems to call for.

    2) The for loop seems to stop with index == 1, so it will miss index == 0.

In any case, we need a test case and change log to land a change like this. Please add a test case that covers both of these issues and test the code before putting it up for review again.

[Karl Schramm]

Created attachment 8961 [details]
lastIndexOf improved patch

This patch should fix some of the problems seen in the previous iterations. However, there's a confusing bit in the docs about what to do when the index is negative:

"Note that even when the index is negative, the array is still searched from back to front. If the calculated index is less than 0, -1 is returned, i.e. the array will not be searched."

The second sentence seems to contradict the first (is the array searched or not??). This patch went with the second sentence. Firefox, it seems, went with the first.

When that mess gets sorted this patch will need a changelog & a test case.

[Vladimir Olexa (vladinecko)]

Created attachment 10094 [details]
lastIndexOf javascript mozilla extension function

Actually, the specs are neither ambiguous nor contradicting. What they're saying is that if the index is negative, calculate a new index by offsetting it from the end of the array. If the calculated index is negative (e.g., array length is 3 and index passed in is -5), then return -1. This patch fixes this scenario adds that additional functionality.

[Vladimir Olexa (vladinecko)]

Created attachment 10095 [details]
lastIndexOf javascript patch

please see my comment above.

[David Kilzer (:ddkilzer)]

Comment on attachment 10095 [details]
lastIndexOf javascript patch

>+      double d = args[1]->toInteger(exec);

Why are you converting an int back to a double here?

[Vladimir Olexa (vladinecko)]

(In reply to comment #11)
> Why are you converting an int back to a double here?
> 

because the variable "length" is declared as unsigned and declaring "d" as int would break a lot of things in the comparisons for obvious reasons. i didn't want to investigate why "length" was declared as unsigned (although it's cast as int anyway) because that would require going through all functions that use it and making sure it's not going to break anything. this can definitely be done but i think it's beyond the scope of this particular bug. 

[Vladimir Olexa (vladinecko)]

(In reply to comment #11)
> Why are you converting an int back to a double here?
> 

also, i didn't touch that piece of code anyway since it's already been implemented in IndexOf case and no bugs were raised regarding that. actually, IndexOf and LastIndexOf are practically identical, only logic behind is a little different so there was only a little to change to go from one to the other.

[Darin Adler]

Comment on attachment 10095 [details]
lastIndexOf javascript patch

Generally looks good!

I see a number of minor mistakes:

+          index = static_cast<unsigned> (d);

It makes no sense to cast d to unsigned here. The types involved are int and double. This should be changed to a cast to int. Also, we don't use a space after the ">" and before the "(".

+      if ((d + length) < 0)
+          return jsNumber(-1);
+      if (d < 0)
+          d += length;      

I think it's a shame that this adds length to d twice. How about this instead:

    if (d < 0) {
        d += length;      
        if (d < 0)
            return jsNumber(-1);
    }

Or it could be structured more like the IndexOf version above.

+      for (; index >= 0; --index) {
+          JSValue* e = getProperty(exec, thisObj, index);
+          if (!e)
+              e = jsUndefined();
+          if (strictEqual(exec, searchElement, e))
+          return jsNumber(index);
+          }

Indentation above is incorrect. The return statement needs to be indented and the ending brace needs to be outdented.

There are other indentation problems: The top two comment lines are not indented the same amount, the ending brace for the entire case is at the wrong level, the return statement doesn't line up with the rest of the code, and there's a stray tab character in the patch (so we'll get an error due to the pre-commit test that checks for tabs).

I'd also like to see a new test that tests all the different edge cases. It's nice that this fixes some JavaScript tests, but ideally you'd have a new test like the one we added when we added indexOf (see LayoutTests/fast/js/array-indexof.html for that one).
None of these are major, but I'm going to mark this review- so that we can fix some or all of these issues. The biggest one for me would be having a test.

[Vladimir Olexa (vladinecko)]

(In reply to comment #14)
> (From update of attachment 10095 [details] [edit])
> +      if ((d + length) < 0)
> +          return jsNumber(-1);
> +      if (d < 0)
> +          d += length;      
> 
> I think it's a shame that this adds length to d twice. How about this instead:
> 
>     if (d < 0) {
>         d += length;      
>         if (d < 0)
>             return jsNumber(-1);
>     }

sounds good. i have a couple of questions about the above statement, however. i had a similar short version of the if block as you proposed before but at the end decided to go with my version since in case (d+length) is negative, the script stops before performing other tests and thus saves an extra operation. but then again, if it's not less than zero then it adds an expense of an extra addition comparison so it's kind of 50-50. what do you think? 

[Darin Adler]

(In reply to comment #15)
> (In reply to comment #14)
> > (From update of attachment 10095 [details] [edit] [edit])
> > +      if ((d + length) < 0)
> > +          return jsNumber(-1);
> > +      if (d < 0)
> > +          d += length;      
> > 
> > I think it's a shame that this adds length to d twice. How about this instead:
> > 
> >     if (d < 0) {
> >         d += length;      
> >         if (d < 0)
> >             return jsNumber(-1);
> >     }
> 
> sounds good. i have a couple of questions about the above statement, however. i
> had a similar short version of the if block as you proposed before but at the
> end decided to go with my version since in case (d+length) is negative, the
> script stops before performing other tests and thus saves an extra operation.
> but then again, if it's not less than zero then it adds an expense of an extra
> addition comparison so it's kind of 50-50. what do you think? 
This is not super-important, but I'd be happy to explain my thinking.

When making a decision like this I consider what's the normal case and what's exceptional. In the common case, d is not negative, and in that case my suggested code does only a single branch. It's not as important to optimize the "highly negative" case because that one usually reflects an error in a script. It's usually best to structure things so that the normal case has as few branches as possible.

We need to be sure this does the right thing in the NaN case as well as negative and positive infinity -- the best way to ensure those is to make sure we have test cases that cover those.

[Vladimir Olexa (vladinecko)]

Created attachment 10132 [details]
lastIndexOf javascript patch REVISION

This my modified patch from before with following changes:

- minimized the if block ala Darin's suggestion
- fixed indentation issues
- added test cases

[Darin Adler]

Comment on attachment 10132 [details]
lastIndexOf javascript patch REVISION

Looks good. r=me

[Alexey Proskuryakov]

Committed revision 15952.