JavaScriptCore:
[WebKit-https.git] / JavaScriptCore / kjs / array_object.cpp
1 // -*- c-basic-offset: 2 -*-
2 /*
3  *  This file is part of the KDE libraries
4  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
5  *  Copyright (C) 2003 Apple Computer, Inc.
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Lesser General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Lesser General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Lesser General Public
18  *  License along with this library; if not, write to the Free Software
19  *  Foundation, Inc., 51 Franklin Steet, Fifth Floor, Boston, MA  02110-1301  USA
20  *
21  */
22
23 #include "config.h"
24 #include "array_object.h"
25
26 #include "error_object.h"
27 #include "internal.h"
28 #include "interpreter.h"
29 #include "object.h"
30 #include "operations.h"
31 #include "reference_list.h"
32 #include "types.h"
33 #include "value.h"
34 #include "HashSet.h"
35
36 #include "array_object.lut.h"
37
38 #include <stdio.h>
39 #include <assert.h>
40
41 using namespace KJS;
42
43 // ------------------------------ ArrayInstanceImp -----------------------------
44
45 const unsigned sparseArrayCutoff = 10000;
46
47 const ClassInfo ArrayInstanceImp::info = {"Array", 0, 0, 0};
48
49 ArrayInstanceImp::ArrayInstanceImp(ObjectImp *proto, unsigned initialLength)
50   : ObjectImp(proto)
51   , length(initialLength)
52   , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)
53   , capacity(storageLength)
54   , storage(capacity ? (ValueImp **)fastCalloc(capacity, sizeof(ValueImp *)) : 0)
55 {
56 }
57
58 ArrayInstanceImp::ArrayInstanceImp(ObjectImp *proto, const List &list)
59   : ObjectImp(proto)
60   , length(list.size())
61   , storageLength(length)
62   , capacity(storageLength)
63   , storage(capacity ? (ValueImp **)fastMalloc(sizeof(ValueImp *) * capacity) : 0)
64 {
65   ListIterator it = list.begin();
66   unsigned l = length;
67   for (unsigned i = 0; i < l; ++i) {
68     storage[i] = it++;
69   }
70 }
71
72 ArrayInstanceImp::~ArrayInstanceImp()
73 {
74   fastFree(storage);
75 }
76
77 ValueImp *ArrayInstanceImp::lengthGetter(ExecState *exec, const Identifier& propertyName, const PropertySlot& slot)
78 {
79   return jsNumber(static_cast<ArrayInstanceImp *>(slot.slotBase())->length);
80 }
81
82 bool ArrayInstanceImp::getOwnPropertySlot(ExecState *exec, const Identifier& propertyName, PropertySlot& slot)
83 {
84   if (propertyName == lengthPropertyName) {
85     slot.setCustom(this, lengthGetter);
86     return true;
87   }
88
89   bool ok;
90   unsigned index = propertyName.toArrayIndex(&ok);
91   if (ok) {
92     if (index >= length)
93       return false;
94     if (index < storageLength) {
95       ValueImp *v = storage[index];
96       if (!v || v->isUndefined())
97         return false;      
98       slot.setValueSlot(this, &storage[index]);
99       return true;
100     }
101   }
102
103   return ObjectImp::getOwnPropertySlot(exec, propertyName, slot);
104 }
105
106 bool ArrayInstanceImp::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
107 {
108   if (index >= length)
109     return false;
110   if (index < storageLength) {
111     ValueImp *v = storage[index];
112     if (!v || v->isUndefined())
113       return false;
114     slot.setValueSlot(this, &storage[index]);
115     return true;
116   }
117
118   return ObjectImp::getOwnPropertySlot(exec, index, slot);
119 }
120
121 // Special implementation of [[Put]] - see ECMA 15.4.5.1
122 void ArrayInstanceImp::put(ExecState *exec, const Identifier &propertyName, ValueImp *value, int attr)
123 {
124   if (propertyName == lengthPropertyName) {
125     setLength(value->toUInt32(exec), exec);
126     return;
127   }
128   
129   bool ok;
130   unsigned index = propertyName.toArrayIndex(&ok);
131   if (ok) {
132     put(exec, index, value, attr);
133     return;
134   }
135   
136   ObjectImp::put(exec, propertyName, value, attr);
137 }
138
139 void ArrayInstanceImp::put(ExecState *exec, unsigned index, ValueImp *value, int attr)
140 {
141   if (index < sparseArrayCutoff && index >= storageLength) {
142     resizeStorage(index + 1);
143   }
144
145   if (index >= length) {
146     length = index + 1;
147   }
148
149   if (index < storageLength) {
150     storage[index] = value;
151     return;
152   }
153   
154   assert(index >= sparseArrayCutoff);
155   ObjectImp::put(exec, Identifier::from(index), value, attr);
156 }
157
158 bool ArrayInstanceImp::deleteProperty(ExecState *exec, const Identifier &propertyName)
159 {
160   if (propertyName == lengthPropertyName)
161     return false;
162   
163   bool ok;
164   uint32_t index = propertyName.toUInt32(&ok);
165   if (ok) {
166     if (index >= length)
167       return true;
168     if (index < storageLength) {
169       storage[index] = 0;
170       return true;
171     }
172   }
173   
174   return ObjectImp::deleteProperty(exec, propertyName);
175 }
176
177 bool ArrayInstanceImp::deleteProperty(ExecState *exec, unsigned index)
178 {
179   if (index >= length)
180     return true;
181   if (index < storageLength) {
182     storage[index] = 0;
183     return true;
184   }
185   
186   return ObjectImp::deleteProperty(exec, Identifier::from(index));
187 }
188
189 ReferenceList ArrayInstanceImp::propList(ExecState *exec, bool recursive)
190 {
191   ReferenceList properties = ObjectImp::propList(exec,recursive);
192
193   // avoid fetching this every time through the loop
194   ValueImp *undefined = jsUndefined();
195
196   for (unsigned i = 0; i < storageLength; ++i) {
197     ValueImp *imp = storage[i];
198     if (imp && imp != undefined) {
199       properties.append(Reference(this, i));
200     }
201   }
202   return properties;
203 }
204
205 void ArrayInstanceImp::resizeStorage(unsigned newLength)
206 {
207     if (newLength < storageLength) {
208       memset(storage + newLength, 0, sizeof(ValueImp *) * (storageLength - newLength));
209     }
210     if (newLength > capacity) {
211       unsigned newCapacity;
212       if (newLength > sparseArrayCutoff) {
213         newCapacity = newLength;
214       } else {
215         newCapacity = (newLength * 3 + 1) / 2;
216         if (newCapacity > sparseArrayCutoff) {
217           newCapacity = sparseArrayCutoff;
218         }
219       }
220       storage = (ValueImp **)fastRealloc(storage, newCapacity * sizeof (ValueImp *));
221       memset(storage + capacity, 0, sizeof(ValueImp *) * (newCapacity - capacity));
222       capacity = newCapacity;
223     }
224     storageLength = newLength;
225 }
226
227 void ArrayInstanceImp::setLength(unsigned newLength, ExecState *exec)
228 {
229   if (newLength <= storageLength) {
230     resizeStorage(newLength);
231   }
232
233   if (newLength < length) {
234     ReferenceList sparseProperties;
235     
236     _prop.addSparseArrayPropertiesToReferenceList(sparseProperties, this);
237     
238     ReferenceListIterator it = sparseProperties.begin();
239     while (it != sparseProperties.end()) {
240       Reference ref = it++;
241       bool ok;
242       unsigned index = ref.getPropertyName(exec).toArrayIndex(&ok);
243       if (ok && index > newLength) {
244         ref.deleteValue(exec);
245       }
246     }
247   }
248   
249   length = newLength;
250 }
251
252 void ArrayInstanceImp::mark()
253 {
254   ObjectImp::mark();
255   unsigned l = storageLength;
256   for (unsigned i = 0; i < l; ++i) {
257     ValueImp *imp = storage[i];
258     if (imp && !imp->marked())
259       imp->mark();
260   }
261 }
262
263 static ExecState *execForCompareByStringForQSort;
264
265 static int compareByStringForQSort(const void *a, const void *b)
266 {
267     ExecState *exec = execForCompareByStringForQSort;
268     ValueImp *va = *(ValueImp **)a;
269     ValueImp *vb = *(ValueImp **)b;
270     if (va->isUndefined()) {
271         return vb->isUndefined() ? 0 : 1;
272     }
273     if (vb->isUndefined()) {
274         return -1;
275     }
276     return compare(va->toString(exec), vb->toString(exec));
277 }
278
279 void ArrayInstanceImp::sort(ExecState *exec)
280 {
281     int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
282     
283     execForCompareByStringForQSort = exec;
284     qsort(storage, lengthNotIncludingUndefined, sizeof(ValueImp *), compareByStringForQSort);
285     execForCompareByStringForQSort = 0;
286 }
287
288 struct CompareWithCompareFunctionArguments {
289     CompareWithCompareFunctionArguments(ExecState *e, ObjectImp *cf)
290         : exec(e)
291         , compareFunction(cf)
292         , globalObject(e->dynamicInterpreter()->globalObject())
293     {
294         arguments.append(jsUndefined());
295         arguments.append(jsUndefined());
296     }
297
298     ExecState *exec;
299     ObjectImp *compareFunction;
300     List arguments;
301     ObjectImp *globalObject;
302 };
303
304 static CompareWithCompareFunctionArguments *compareWithCompareFunctionArguments;
305
306 static int compareWithCompareFunctionForQSort(const void *a, const void *b)
307 {
308     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
309
310     ValueImp *va = *(ValueImp **)a;
311     ValueImp *vb = *(ValueImp **)b;
312     if (va->isUndefined()) {
313         return vb->isUndefined() ? 0 : 1;
314     }
315     if (vb->isUndefined()) {
316         return -1;
317     }
318
319     args->arguments.clear();
320     args->arguments.append(va);
321     args->arguments.append(vb);
322     double compareResult = args->compareFunction->call
323         (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
324     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
325 }
326
327 void ArrayInstanceImp::sort(ExecState *exec, ObjectImp *compareFunction)
328 {
329     int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
330     
331     CompareWithCompareFunctionArguments args(exec, compareFunction);
332     compareWithCompareFunctionArguments = &args;
333     qsort(storage, lengthNotIncludingUndefined, sizeof(ValueImp *), compareWithCompareFunctionForQSort);
334     compareWithCompareFunctionArguments = 0;
335 }
336
337 unsigned ArrayInstanceImp::pushUndefinedObjectsToEnd(ExecState *exec)
338 {
339     ValueImp *undefined = jsUndefined();
340
341     unsigned o = 0;
342     
343     for (unsigned i = 0; i != storageLength; ++i) {
344         ValueImp *v = storage[i];
345         if (v && v != undefined) {
346             if (o != i)
347                 storage[o] = v;
348             o++;
349         }
350     }
351     
352     ReferenceList sparseProperties;
353     _prop.addSparseArrayPropertiesToReferenceList(sparseProperties, this);
354     unsigned newLength = o + sparseProperties.length();
355
356     if (newLength > storageLength) {
357       resizeStorage(newLength);
358     } 
359
360     ReferenceListIterator it = sparseProperties.begin();
361     while (it != sparseProperties.end()) {
362       Reference ref = it++;
363       storage[o] = ref.getValue(exec);
364       ObjectImp::deleteProperty(exec, ref.getPropertyName(exec));
365       o++;
366     }
367     
368     if (newLength != storageLength)
369         memset(storage + o, 0, sizeof(ValueImp *) * (storageLength - o));
370     
371     return o;
372 }
373
374 // ------------------------------ ArrayPrototypeImp ----------------------------
375
376 const ClassInfo ArrayPrototypeImp::info = {"Array", &ArrayInstanceImp::info, &arrayTable, 0};
377
378 /* Source for array_object.lut.h
379 @begin arrayTable 16
380   toString       ArrayProtoFuncImp::ToString       DontEnum|Function 0
381   toLocaleString ArrayProtoFuncImp::ToLocaleString DontEnum|Function 0
382   concat         ArrayProtoFuncImp::Concat         DontEnum|Function 1
383   join           ArrayProtoFuncImp::Join           DontEnum|Function 1
384   pop            ArrayProtoFuncImp::Pop            DontEnum|Function 0
385   push           ArrayProtoFuncImp::Push           DontEnum|Function 1
386   reverse        ArrayProtoFuncImp::Reverse        DontEnum|Function 0
387   shift          ArrayProtoFuncImp::Shift          DontEnum|Function 0
388   slice          ArrayProtoFuncImp::Slice          DontEnum|Function 2
389   sort           ArrayProtoFuncImp::Sort           DontEnum|Function 1
390   splice         ArrayProtoFuncImp::Splice         DontEnum|Function 2
391   unshift        ArrayProtoFuncImp::UnShift        DontEnum|Function 1
392   every          ArrayProtoFuncImp::Every          DontEnum|Function 5
393   forEach        ArrayProtoFuncImp::ForEach        DontEnum|Function 5
394   some           ArrayProtoFuncImp::Some           DontEnum|Function 5
395 @end
396 */
397
398 // ECMA 15.4.4
399 ArrayPrototypeImp::ArrayPrototypeImp(ExecState *exec,
400                                      ObjectPrototypeImp *objProto)
401   : ArrayInstanceImp(objProto, 0)
402 {
403   setInternalValue(jsNull());
404 }
405
406 bool ArrayPrototypeImp::getOwnPropertySlot(ExecState *exec, const Identifier& propertyName, PropertySlot& slot)
407 {
408   return getStaticFunctionSlot<ArrayProtoFuncImp, ArrayInstanceImp>(exec, &arrayTable, this, propertyName, slot);
409 }
410
411 // ------------------------------ ArrayProtoFuncImp ----------------------------
412
413 ArrayProtoFuncImp::ArrayProtoFuncImp(ExecState *exec, int i, int len)
414   : InternalFunctionImp(
415     static_cast<FunctionPrototypeImp*>(exec->lexicalInterpreter()->builtinFunctionPrototype())
416     ), id(i)
417 {
418   put(exec,lengthPropertyName,jsNumber(len),DontDelete|ReadOnly|DontEnum);
419 }
420
421 bool ArrayProtoFuncImp::implementsCall() const
422 {
423   return true;
424 }
425
426 static ValueImp *getProperty(ExecState *exec, ObjectImp *obj, unsigned index)
427 {
428     PropertySlot slot;
429     if (!obj->getPropertySlot(exec, index, slot))
430         return NULL;
431     return slot.getValue(exec, index);
432 }
433
434 // ECMA 15.4.4
435 ValueImp *ArrayProtoFuncImp::callAsFunction(ExecState *exec, ObjectImp *thisObj, const List &args)
436 {
437   unsigned length = thisObj->get(exec,lengthPropertyName)->toUInt32(exec);
438
439   ValueImp *result = 0; // work around gcc 4.0 bug in uninitialized variable warning
440   
441   switch (id) {
442   case ToLocaleString:
443   case ToString:
444
445     if (!thisObj->inherits(&ArrayInstanceImp::info))
446       return throwError(exec, TypeError);
447
448     // fall through
449   case Join: {
450     static HashSet< ObjectImp*, PointerHash<ObjectImp*> > visitedElems;
451     if (visitedElems.contains(thisObj))
452       return jsString("");
453     UString separator = ",";
454     UString str = "";
455
456     visitedElems.insert(thisObj);
457     if (!args[0]->isUndefined())
458       separator = args[0]->toString(exec);
459     for (unsigned int k = 0; k < length; k++) {
460       if (k >= 1)
461         str += separator;
462       
463       ValueImp *element = thisObj->get(exec, k);
464       if (element->isUndefinedOrNull())
465         continue;
466
467       bool fallback = false;
468       if (id == ToLocaleString) {
469         ObjectImp *o = element->toObject(exec);
470         ValueImp *conversionFunction = o->get(exec, toLocaleStringPropertyName);
471         if (conversionFunction->isObject() && static_cast<ObjectImp *>(conversionFunction)->implementsCall()) {
472           str += static_cast<ObjectImp *>(conversionFunction)->call(exec, o, List())->toString(exec);
473         } else {
474           // try toString() fallback
475           fallback = true;
476         }
477       }
478
479       if (id == ToString || id == Join || fallback) {
480         if (element->isObject()) {
481           ObjectImp *o = static_cast<ObjectImp *>(element);
482           ValueImp *conversionFunction = o->get(exec, toStringPropertyName);
483           if (conversionFunction->isObject() && static_cast<ObjectImp *>(conversionFunction)->implementsCall()) {
484             str += static_cast<ObjectImp *>(conversionFunction)->call(exec, o, List())->toString(exec);
485           } else {
486             return throwError(exec, RangeError, "Can't convert " + o->className() + " object to string");
487           }
488         } else {
489           str += element->toString(exec);
490         }
491       }
492
493       if ( exec->hadException() )
494         break;
495     }
496     visitedElems.remove(thisObj);
497     result = jsString(str);
498     break;
499   }
500   case Concat: {
501     ObjectImp *arr = static_cast<ObjectImp *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
502     int n = 0;
503     ValueImp *curArg = thisObj;
504     ObjectImp *curObj = static_cast<ObjectImp *>(thisObj);
505     ListIterator it = args.begin();
506     for (;;) {
507       if (curArg->isObject() &&
508           curObj->inherits(&ArrayInstanceImp::info)) {
509         unsigned int k = 0;
510         // Older versions tried to optimize out getting the length of thisObj
511         // by checking for n != 0, but that doesn't work if thisObj is an empty array.
512         length = curObj->get(exec,lengthPropertyName)->toUInt32(exec);
513         while (k < length) {
514           if (ValueImp *v = getProperty(exec, curObj, k))
515             arr->put(exec, n, v);
516           n++;
517           k++;
518         }
519       } else {
520         arr->put(exec, n, curArg);
521         n++;
522       }
523       if (it == args.end())
524         break;
525       curArg = *it;
526       curObj = static_cast<ObjectImp *>(it++); // may be 0
527     }
528     arr->put(exec,lengthPropertyName, jsNumber(n), DontEnum | DontDelete);
529
530     result = arr;
531     break;
532   }
533   case Pop:{
534     if (length == 0) {
535       thisObj->put(exec, lengthPropertyName, jsNumber(length), DontEnum | DontDelete);
536       result = jsUndefined();
537     } else {
538       result = thisObj->get(exec, length - 1);
539       thisObj->put(exec, lengthPropertyName, jsNumber(length - 1), DontEnum | DontDelete);
540     }
541     break;
542   }
543   case Push: {
544     for (int n = 0; n < args.size(); n++)
545       thisObj->put(exec, length + n, args[n]);
546     length += args.size();
547     thisObj->put(exec,lengthPropertyName, jsNumber(length), DontEnum | DontDelete);
548     result = jsNumber(length);
549     break;
550   }
551   case Reverse: {
552
553     unsigned int middle = length / 2;
554
555     for (unsigned int k = 0; k < middle; k++) {
556       unsigned lk1 = length - k - 1;
557       ValueImp *obj2 = getProperty(exec, thisObj, lk1);
558       ValueImp *obj = getProperty(exec, thisObj, k);
559
560       if (obj2) 
561         thisObj->put(exec, k, obj2);
562       else
563         thisObj->deleteProperty(exec, k);
564
565       if (obj)
566         thisObj->put(exec, lk1, obj);
567       else
568         thisObj->deleteProperty(exec, lk1);
569     }
570     result = thisObj;
571     break;
572   }
573   case Shift: {
574     if (length == 0) {
575       thisObj->put(exec, lengthPropertyName, jsNumber(length), DontEnum | DontDelete);
576       result = jsUndefined();
577     } else {
578       result = thisObj->get(exec, 0);
579       for(unsigned int k = 1; k < length; k++) {
580         if (ValueImp *obj = getProperty(exec, thisObj, k))
581           thisObj->put(exec, k-1, obj);
582         else
583           thisObj->deleteProperty(exec, k-1);
584       }
585       thisObj->deleteProperty(exec, length - 1);
586       thisObj->put(exec, lengthPropertyName, jsNumber(length - 1), DontEnum | DontDelete);
587     }
588     break;
589   }
590   case Slice: {
591     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
592
593     // We return a new array
594     ObjectImp *resObj = static_cast<ObjectImp *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
595     result = resObj;
596     double begin = 0;
597     if (!args[0]->isUndefined()) {
598         begin = args[0]->toInteger(exec);
599         if (begin >= 0) { // false for NaN
600             if (begin > length)
601                 begin = length;
602         } else {
603             begin += length;
604             if (!(begin >= 0)) // true for NaN
605                 begin = 0;
606         }
607     }
608     double end = length;
609     if (!args[1]->isUndefined()) {
610       end = args[1]->toInteger(exec);
611       if (end < 0) { // false for NaN
612         end += length;
613         if (end < 0)
614           end = 0;
615       } else {
616         if (!(end <= length)) // true for NaN
617           end = length;
618       }
619     }
620
621     //printf( "Slicing from %d to %d \n", begin, end );
622     int n = 0;
623     int b = static_cast<int>(begin);
624     int e = static_cast<int>(end);
625     for(int k = b; k < e; k++, n++) {
626       if (ValueImp *v = getProperty(exec, thisObj, k))
627         resObj->put(exec, n, v);
628     }
629     resObj->put(exec, lengthPropertyName, jsNumber(n), DontEnum | DontDelete);
630     break;
631   }
632   case Sort:{
633 #if 0
634     printf("KJS Array::Sort length=%d\n", length);
635     for ( unsigned int i = 0 ; i<length ; ++i )
636       printf("KJS Array::Sort: %d: %s\n", i, thisObj->get(exec, i)->toString(exec).ascii() );
637 #endif
638     ObjectImp *sortFunction = NULL;
639     if (!args[0]->isUndefined())
640       {
641         sortFunction = args[0]->toObject(exec);
642         if (!sortFunction->implementsCall())
643           sortFunction = NULL;
644       }
645     
646     if (thisObj->classInfo() == &ArrayInstanceImp::info) {
647       if (sortFunction)
648         ((ArrayInstanceImp *)thisObj)->sort(exec, sortFunction);
649       else
650         ((ArrayInstanceImp *)thisObj)->sort(exec);
651       result = thisObj;
652       break;
653     }
654
655     if (length == 0) {
656       thisObj->put(exec, lengthPropertyName, jsNumber(0), DontEnum | DontDelete);
657       result = thisObj;
658       break;
659     }
660
661     // "Min" sort. Not the fastest, but definitely less code than heapsort
662     // or quicksort, and much less swapping than bubblesort/insertionsort.
663     for ( unsigned int i = 0 ; i<length-1 ; ++i )
664       {
665         ValueImp *iObj = thisObj->get(exec,i);
666         unsigned int themin = i;
667         ValueImp *minObj = iObj;
668         for ( unsigned int j = i+1 ; j<length ; ++j )
669           {
670             ValueImp *jObj = thisObj->get(exec,j);
671             double cmp;
672             if (jObj->isUndefined()) {
673               cmp = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
674             } else if (minObj->isUndefined()) {
675               cmp = -1;
676             } else if (sortFunction) {
677                 List l;
678                 l.append(jObj);
679                 l.append(minObj);
680                 cmp = sortFunction->call(exec, exec->dynamicInterpreter()->globalObject(), l)->toNumber(exec);
681             } else {
682               cmp = (jObj->toString(exec) < minObj->toString(exec)) ? -1 : 1;
683             }
684             if ( cmp < 0 )
685               {
686                 themin = j;
687                 minObj = jObj;
688               }
689           }
690         // Swap themin and i
691         if ( themin > i )
692           {
693             //printf("KJS Array::Sort: swapping %d and %d\n", i, themin );
694             thisObj->put( exec, i, minObj );
695             thisObj->put( exec, themin, iObj );
696           }
697       }
698 #if 0
699     printf("KJS Array::Sort -- Resulting array:\n");
700     for ( unsigned int i = 0 ; i<length ; ++i )
701       printf("KJS Array::Sort: %d: %s\n", i, thisObj->get(exec, i)->toString(exec).ascii() );
702 #endif
703     result = thisObj;
704     break;
705   }
706   case Splice: {
707     // 15.4.4.12 - oh boy this is huge
708     ObjectImp *resObj = static_cast<ObjectImp *>(exec->lexicalInterpreter()->builtinArray()->construct(exec,List::empty()));
709     result = resObj;
710     int begin = args[0]->toUInt32(exec);
711     if ( begin < 0 )
712       begin = maxInt( begin + length, 0 );
713     else
714       begin = minInt( begin, length );
715     unsigned int deleteCount = minInt( maxInt( args[1]->toUInt32(exec), 0 ), length - begin );
716
717     //printf( "Splicing from %d, deleteCount=%d \n", begin, deleteCount );
718     for(unsigned int k = 0; k < deleteCount; k++) {
719       if (ValueImp *v = getProperty(exec, thisObj, k+begin))
720         resObj->put(exec, k, v);
721     }
722     resObj->put(exec, lengthPropertyName, jsNumber(deleteCount), DontEnum | DontDelete);
723
724     unsigned int additionalArgs = maxInt( args.size() - 2, 0 );
725     if ( additionalArgs != deleteCount )
726     {
727       if ( additionalArgs < deleteCount )
728       {
729         for ( unsigned int k = begin; k < length - deleteCount; ++k )
730         {
731           if (ValueImp *v = getProperty(exec, thisObj, k+deleteCount))
732             thisObj->put(exec, k+additionalArgs, v);
733           else
734             thisObj->deleteProperty(exec, k+additionalArgs);
735         }
736         for ( unsigned int k = length ; k > length - deleteCount + additionalArgs; --k )
737           thisObj->deleteProperty(exec, k-1);
738       }
739       else
740       {
741         for ( unsigned int k = length - deleteCount; (int)k > begin; --k )
742         {
743           if (ValueImp *obj = getProperty(exec, thisObj, k + deleteCount - 1))
744             thisObj->put(exec, k + additionalArgs - 1, obj);
745           else
746             thisObj->deleteProperty(exec, k+additionalArgs-1);
747         }
748       }
749     }
750     for ( unsigned int k = 0; k < additionalArgs; ++k )
751     {
752       thisObj->put(exec, k+begin, args[k+2]);
753     }
754     thisObj->put(exec, lengthPropertyName, jsNumber(length - deleteCount + additionalArgs), DontEnum | DontDelete);
755     break;
756   }
757   case UnShift: { // 15.4.4.13
758     unsigned int nrArgs = args.size();
759     for ( unsigned int k = length; k > 0; --k )
760     {
761       if (ValueImp *v = getProperty(exec, thisObj, k - 1))
762         thisObj->put(exec, k+nrArgs-1, v);
763       else
764         thisObj->deleteProperty(exec, k+nrArgs-1);
765     }
766     for ( unsigned int k = 0; k < nrArgs; ++k )
767       thisObj->put(exec, k, args[k]);
768     result = jsNumber(length + nrArgs);
769     thisObj->put(exec, lengthPropertyName, result, DontEnum | DontDelete);
770     break;
771   }
772   case Every:
773   case ForEach:
774   case Some: {
775     //Documentation for these three is available at:
776     //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:every
777     //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:forEach
778     //http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:some
779     
780     ObjectImp *eachFunction = args[0]->toObject(exec);
781     
782     if (!eachFunction->implementsCall())
783       return throwError(exec, TypeError);
784     
785     ObjectImp *applyThis = args[1]->isUndefinedOrNull() ? exec->dynamicInterpreter()->globalObject() :  args[1]->toObject(exec);
786     
787     if (id == Some || id == Every)
788       result = jsBoolean(id == Every);
789     else
790       result = thisObj;
791     
792     for (unsigned k = 0; k < length && !exec->hadException(); ++k) {
793       
794       List eachArguments;
795       
796       eachArguments.append(thisObj->get(exec, k));
797       eachArguments.append(jsNumber(k));
798       eachArguments.append(thisObj);
799       
800       bool predicateResult = eachFunction->call(exec, applyThis, eachArguments)->toBoolean(exec);
801       
802       if (id == Every && !predicateResult) {
803         result = jsBoolean(false);
804         break;
805       }
806       if (id == Some && predicateResult) {
807         result = jsBoolean(true);
808         break;
809       }
810     }
811     break;
812   }
813     
814   default:
815     assert(0);
816     result = 0;
817     break;
818   }
819   return result;
820 }
821
822 // ------------------------------ ArrayObjectImp -------------------------------
823
824 ArrayObjectImp::ArrayObjectImp(ExecState *exec,
825                                FunctionPrototypeImp *funcProto,
826                                ArrayPrototypeImp *arrayProto)
827   : InternalFunctionImp(funcProto)
828 {
829   // ECMA 15.4.3.1 Array.prototype
830   put(exec, prototypePropertyName, arrayProto, DontEnum|DontDelete|ReadOnly);
831
832   // no. of arguments for constructor
833   put(exec, lengthPropertyName, jsNumber(1), ReadOnly|DontDelete|DontEnum);
834 }
835
836 bool ArrayObjectImp::implementsConstruct() const
837 {
838   return true;
839 }
840
841 // ECMA 15.4.2
842 ObjectImp *ArrayObjectImp::construct(ExecState *exec, const List &args)
843 {
844   // a single numeric argument denotes the array size (!)
845   if (args.size() == 1 && args[0]->isNumber()) {
846     uint32_t n = args[0]->toUInt32(exec);
847     if (n != args[0]->toNumber(exec))
848       return throwError(exec, RangeError, "Array size is not a small enough positive integer.");
849     return new ArrayInstanceImp(exec->lexicalInterpreter()->builtinArrayPrototype(), n);
850   }
851
852   // otherwise the array is constructed with the arguments in it
853   return new ArrayInstanceImp(exec->lexicalInterpreter()->builtinArrayPrototype(), args);
854 }
855
856 bool ArrayObjectImp::implementsCall() const
857 {
858   return true;
859 }
860
861 // ECMA 15.6.1
862 ValueImp *ArrayObjectImp::callAsFunction(ExecState *exec, ObjectImp */*thisObj*/, const List &args)
863 {
864   // equivalent to 'new Array(....)'
865   return construct(exec,args);
866 }