OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
11 // with the distribution. | 11 // with the distribution. |
12 // * Neither the name of Google Inc. nor the names of its | 12 // * Neither the name of Google Inc. nor the names of its |
13 // contributors may be used to endorse or promote products derived | 13 // contributors may be used to endorse or promote products derived |
14 // from this software without specific prior written permission. | 14 // from this software without specific prior written permission. |
15 // | 15 // |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 // This file relies on the fact that the following declarations have been made | 28 // This file relies on the fact that the following declarations have been made |
29 // in runtime.js: | 29 // in runtime.js: |
30 // const $Array = global.Array; | 30 // var $Array = global.Array; |
31 | 31 |
32 // ------------------------------------------------------------------- | 32 // ------------------------------------------------------------------- |
33 | 33 |
34 // Global list of arrays visited during toString, toLocaleString and | 34 // Global list of arrays visited during toString, toLocaleString and |
35 // join invocations. | 35 // join invocations. |
36 var visited_arrays = new InternalArray(); | 36 var visited_arrays = new InternalArray(); |
37 | 37 |
38 | 38 |
39 // Gets a sorted array of array keys. Useful for operations on sparse | 39 // Gets a sorted array of array keys. Useful for operations on sparse |
40 // arrays. Dupes have not been removed. | 40 // arrays. Dupes have not been removed. |
(...skipping 709 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
750 return %SmiLexicographicCompare(x, y); | 750 return %SmiLexicographicCompare(x, y); |
751 } | 751 } |
752 x = ToString(x); | 752 x = ToString(x); |
753 y = ToString(y); | 753 y = ToString(y); |
754 if (x == y) return 0; | 754 if (x == y) return 0; |
755 else return x < y ? -1 : 1; | 755 else return x < y ? -1 : 1; |
756 }; | 756 }; |
757 } | 757 } |
758 var receiver = %GetDefaultReceiver(comparefn); | 758 var receiver = %GetDefaultReceiver(comparefn); |
759 | 759 |
760 function InsertionSort(a, from, to) { | 760 var InsertionSort = function InsertionSort(a, from, to) { |
761 for (var i = from + 1; i < to; i++) { | 761 for (var i = from + 1; i < to; i++) { |
762 var element = a[i]; | 762 var element = a[i]; |
763 for (var j = i - 1; j >= from; j--) { | 763 for (var j = i - 1; j >= from; j--) { |
764 var tmp = a[j]; | 764 var tmp = a[j]; |
765 var order = %_CallFunction(receiver, tmp, element, comparefn); | 765 var order = %_CallFunction(receiver, tmp, element, comparefn); |
766 if (order > 0) { | 766 if (order > 0) { |
767 a[j + 1] = tmp; | 767 a[j + 1] = tmp; |
768 } else { | 768 } else { |
769 break; | 769 break; |
770 } | 770 } |
771 } | 771 } |
772 a[j + 1] = element; | 772 a[j + 1] = element; |
773 } | 773 } |
774 } | 774 }; |
775 | 775 |
776 function QuickSort(a, from, to) { | 776 var QuickSort = function QuickSort(a, from, to) { |
777 // Insertion sort is faster for short arrays. | 777 // Insertion sort is faster for short arrays. |
778 if (to - from <= 10) { | 778 if (to - from <= 10) { |
779 InsertionSort(a, from, to); | 779 InsertionSort(a, from, to); |
780 return; | 780 return; |
781 } | 781 } |
782 // Find a pivot as the median of first, last and middle element. | 782 // Find a pivot as the median of first, last and middle element. |
783 var v0 = a[from]; | 783 var v0 = a[from]; |
784 var v1 = a[to - 1]; | 784 var v1 = a[to - 1]; |
785 var middle_index = from + ((to - from) >> 1); | 785 var middle_index = from + ((to - from) >> 1); |
786 var v2 = a[middle_index]; | 786 var v2 = a[middle_index]; |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
834 } while (order > 0); | 834 } while (order > 0); |
835 %_SwapElements(a, i, high_start); | 835 %_SwapElements(a, i, high_start); |
836 if (order < 0) { | 836 if (order < 0) { |
837 %_SwapElements(a, i, low_end); | 837 %_SwapElements(a, i, low_end); |
838 low_end++; | 838 low_end++; |
839 } | 839 } |
840 } | 840 } |
841 } | 841 } |
842 QuickSort(a, from, low_end); | 842 QuickSort(a, from, low_end); |
843 QuickSort(a, high_start, to); | 843 QuickSort(a, high_start, to); |
844 } | 844 }; |
845 | 845 |
846 // Copy elements in the range 0..length from obj's prototype chain | 846 // Copy elements in the range 0..length from obj's prototype chain |
847 // to obj itself, if obj has holes. Return one more than the maximal index | 847 // to obj itself, if obj has holes. Return one more than the maximal index |
848 // of a prototype property. | 848 // of a prototype property. |
849 function CopyFromPrototype(obj, length) { | 849 var CopyFromPrototype = function CopyFromPrototype(obj, length) { |
850 var max = 0; | 850 var max = 0; |
851 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { | 851 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { |
852 var indices = %GetArrayKeys(proto, length); | 852 var indices = %GetArrayKeys(proto, length); |
853 if (indices.length > 0) { | 853 if (indices.length > 0) { |
854 if (indices[0] == -1) { | 854 if (indices[0] == -1) { |
855 // It's an interval. | 855 // It's an interval. |
856 var proto_length = indices[1]; | 856 var proto_length = indices[1]; |
857 for (var i = 0; i < proto_length; i++) { | 857 for (var i = 0; i < proto_length; i++) { |
858 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { | 858 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { |
859 obj[i] = proto[i]; | 859 obj[i] = proto[i]; |
860 if (i >= max) { max = i + 1; } | 860 if (i >= max) { max = i + 1; } |
861 } | 861 } |
862 } | 862 } |
863 } else { | 863 } else { |
864 for (var i = 0; i < indices.length; i++) { | 864 for (var i = 0; i < indices.length; i++) { |
865 var index = indices[i]; | 865 var index = indices[i]; |
866 if (!IS_UNDEFINED(index) && | 866 if (!IS_UNDEFINED(index) && |
867 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { | 867 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { |
868 obj[index] = proto[index]; | 868 obj[index] = proto[index]; |
869 if (index >= max) { max = index + 1; } | 869 if (index >= max) { max = index + 1; } |
870 } | 870 } |
871 } | 871 } |
872 } | 872 } |
873 } | 873 } |
874 } | 874 } |
875 return max; | 875 return max; |
876 } | 876 }; |
877 | 877 |
878 // Set a value of "undefined" on all indices in the range from..to | 878 // Set a value of "undefined" on all indices in the range from..to |
879 // where a prototype of obj has an element. I.e., shadow all prototype | 879 // where a prototype of obj has an element. I.e., shadow all prototype |
880 // elements in that range. | 880 // elements in that range. |
881 function ShadowPrototypeElements(obj, from, to) { | 881 var ShadowPrototypeElements = function(obj, from, to) { |
882 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { | 882 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { |
883 var indices = %GetArrayKeys(proto, to); | 883 var indices = %GetArrayKeys(proto, to); |
884 if (indices.length > 0) { | 884 if (indices.length > 0) { |
885 if (indices[0] == -1) { | 885 if (indices[0] == -1) { |
886 // It's an interval. | 886 // It's an interval. |
887 var proto_length = indices[1]; | 887 var proto_length = indices[1]; |
888 for (var i = from; i < proto_length; i++) { | 888 for (var i = from; i < proto_length; i++) { |
889 if (proto.hasOwnProperty(i)) { | 889 if (proto.hasOwnProperty(i)) { |
890 obj[i] = void 0; | 890 obj[i] = void 0; |
891 } | 891 } |
892 } | 892 } |
893 } else { | 893 } else { |
894 for (var i = 0; i < indices.length; i++) { | 894 for (var i = 0; i < indices.length; i++) { |
895 var index = indices[i]; | 895 var index = indices[i]; |
896 if (!IS_UNDEFINED(index) && from <= index && | 896 if (!IS_UNDEFINED(index) && from <= index && |
897 proto.hasOwnProperty(index)) { | 897 proto.hasOwnProperty(index)) { |
898 obj[index] = void 0; | 898 obj[index] = void 0; |
899 } | 899 } |
900 } | 900 } |
901 } | 901 } |
902 } | 902 } |
903 } | 903 } |
904 } | 904 }; |
905 | 905 |
906 function SafeRemoveArrayHoles(obj) { | 906 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) { |
907 // Copy defined elements from the end to fill in all holes and undefineds | 907 // Copy defined elements from the end to fill in all holes and undefineds |
908 // in the beginning of the array. Write undefineds and holes at the end | 908 // in the beginning of the array. Write undefineds and holes at the end |
909 // after loop is finished. | 909 // after loop is finished. |
910 var first_undefined = 0; | 910 var first_undefined = 0; |
911 var last_defined = length - 1; | 911 var last_defined = length - 1; |
912 var num_holes = 0; | 912 var num_holes = 0; |
913 while (first_undefined < last_defined) { | 913 while (first_undefined < last_defined) { |
914 // Find first undefined element. | 914 // Find first undefined element. |
915 while (first_undefined < last_defined && | 915 while (first_undefined < last_defined && |
916 !IS_UNDEFINED(obj[first_undefined])) { | 916 !IS_UNDEFINED(obj[first_undefined])) { |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
951 // For compatability with Webkit, do not expose elements in the prototype. | 951 // For compatability with Webkit, do not expose elements in the prototype. |
952 if (i in obj.__proto__) { | 952 if (i in obj.__proto__) { |
953 obj[i] = void 0; | 953 obj[i] = void 0; |
954 } else { | 954 } else { |
955 delete obj[i]; | 955 delete obj[i]; |
956 } | 956 } |
957 } | 957 } |
958 | 958 |
959 // Return the number of defined elements. | 959 // Return the number of defined elements. |
960 return first_undefined; | 960 return first_undefined; |
961 } | 961 }; |
962 | 962 |
963 var length = TO_UINT32(this.length); | 963 var length = TO_UINT32(this.length); |
964 if (length < 2) return this; | 964 if (length < 2) return this; |
965 | 965 |
966 var is_array = IS_ARRAY(this); | 966 var is_array = IS_ARRAY(this); |
967 var max_prototype_element; | 967 var max_prototype_element; |
968 if (!is_array) { | 968 if (!is_array) { |
969 // For compatibility with JSC, we also sort elements inherited from | 969 // For compatibility with JSC, we also sort elements inherited from |
970 // the prototype chain on non-Array objects. | 970 // the prototype chain on non-Array objects. |
971 // We do this by copying them to this object and sorting only | 971 // We do this by copying them to this object and sorting only |
(...skipping 394 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1366 // object. | 1366 // object. |
1367 %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM); | 1367 %SetProperty($Array.prototype, "constructor", $Array, DONT_ENUM); |
1368 | 1368 |
1369 // Set up non-enumerable functions on the Array object. | 1369 // Set up non-enumerable functions on the Array object. |
1370 InstallFunctions($Array, DONT_ENUM, $Array( | 1370 InstallFunctions($Array, DONT_ENUM, $Array( |
1371 "isArray", ArrayIsArray | 1371 "isArray", ArrayIsArray |
1372 )); | 1372 )); |
1373 | 1373 |
1374 var specialFunctions = %SpecialArrayFunctions({}); | 1374 var specialFunctions = %SpecialArrayFunctions({}); |
1375 | 1375 |
1376 function getFunction(name, jsBuiltin, len) { | 1376 var getFunction = function(name, jsBuiltin, len) { |
1377 var f = jsBuiltin; | 1377 var f = jsBuiltin; |
1378 if (specialFunctions.hasOwnProperty(name)) { | 1378 if (specialFunctions.hasOwnProperty(name)) { |
1379 f = specialFunctions[name]; | 1379 f = specialFunctions[name]; |
1380 } | 1380 } |
1381 if (!IS_UNDEFINED(len)) { | 1381 if (!IS_UNDEFINED(len)) { |
1382 %FunctionSetLength(f, len); | 1382 %FunctionSetLength(f, len); |
1383 } | 1383 } |
1384 return f; | 1384 return f; |
1385 } | 1385 }; |
1386 | 1386 |
1387 // Set up non-enumerable functions of the Array.prototype object and | 1387 // Set up non-enumerable functions of the Array.prototype object and |
1388 // set their names. | 1388 // set their names. |
1389 // Manipulate the length of some of the functions to meet | 1389 // Manipulate the length of some of the functions to meet |
1390 // expectations set by ECMA-262 or Mozilla. | 1390 // expectations set by ECMA-262 or Mozilla. |
1391 InstallFunctions($Array.prototype, DONT_ENUM, $Array( | 1391 InstallFunctions($Array.prototype, DONT_ENUM, $Array( |
1392 "toString", getFunction("toString", ArrayToString), | 1392 "toString", getFunction("toString", ArrayToString), |
1393 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString), | 1393 "toLocaleString", getFunction("toLocaleString", ArrayToLocaleString), |
1394 "join", getFunction("join", ArrayJoin), | 1394 "join", getFunction("join", ArrayJoin), |
1395 "pop", getFunction("pop", ArrayPop), | 1395 "pop", getFunction("pop", ArrayPop), |
(...skipping 22 matching lines...) Expand all Loading... |
1418 // exposed to user code. | 1418 // exposed to user code. |
1419 // Adding only the functions that are actually used. | 1419 // Adding only the functions that are actually used. |
1420 SetUpLockedPrototype(InternalArray, $Array(), $Array( | 1420 SetUpLockedPrototype(InternalArray, $Array(), $Array( |
1421 "join", getFunction("join", ArrayJoin), | 1421 "join", getFunction("join", ArrayJoin), |
1422 "pop", getFunction("pop", ArrayPop), | 1422 "pop", getFunction("pop", ArrayPop), |
1423 "push", getFunction("push", ArrayPush) | 1423 "push", getFunction("push", ArrayPush) |
1424 )); | 1424 )); |
1425 } | 1425 } |
1426 | 1426 |
1427 SetUpArray(); | 1427 SetUpArray(); |
OLD | NEW |