OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 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 |
(...skipping 20 matching lines...) Expand all Loading... |
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. |
41 function GetSortedArrayKeys(array, intervals) { | 41 function GetSortedArrayKeys(array, indices) { |
42 var length = intervals.length; | 42 var keys = new InternalArray(); |
43 var keys = []; | 43 if (IS_NUMBER(indices)) { |
44 for (var k = 0; k < length; k++) { | 44 // It's an interval |
45 var key = intervals[k]; | 45 var limit = indices; |
46 if (key < 0) { | 46 for (var i = 0; i < limit; ++i) { |
47 var j = -1 - key; | 47 var e = array[i]; |
48 var limit = j + intervals[++k]; | 48 if (!IS_UNDEFINED(e) || i in array) { |
49 for (; j < limit; j++) { | 49 keys.push(i); |
50 var e = array[j]; | |
51 if (!IS_UNDEFINED(e) || j in array) { | |
52 keys.push(j); | |
53 } | |
54 } | 50 } |
55 } else { | 51 } |
56 // The case where key is undefined also ends here. | 52 } else { |
| 53 var length = indices.length; |
| 54 for (var k = 0; k < length; ++k) { |
| 55 var key = indices[k]; |
57 if (!IS_UNDEFINED(key)) { | 56 if (!IS_UNDEFINED(key)) { |
58 var e = array[key]; | 57 var e = array[key]; |
59 if (!IS_UNDEFINED(e) || key in array) { | 58 if (!IS_UNDEFINED(e) || key in array) { |
60 keys.push(key); | 59 keys.push(key); |
61 } | 60 } |
62 } | 61 } |
63 } | 62 } |
| 63 %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort); |
64 } | 64 } |
65 %_CallFunction(keys, function(a, b) { return a - b; }, ArraySort); | |
66 return keys; | 65 return keys; |
67 } | 66 } |
68 | 67 |
69 | 68 |
70 function SparseJoinWithSeparator(array, len, convert, separator) { | 69 function SparseJoinWithSeparator(array, len, convert, separator) { |
71 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); | 70 var keys = GetSortedArrayKeys(array, %GetArrayKeys(array, len)); |
72 var totalLength = 0; | 71 var totalLength = 0; |
73 var elements = new InternalArray(keys.length * 2); | 72 var elements = new InternalArray(keys.length * 2); |
74 var previousKey = -1; | 73 var previousKey = -1; |
75 for (var i = 0; i < keys.length; i++) { | 74 for (var i = 0; i < keys.length; i++) { |
(...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
210 var e_obj = ToObject(e); | 209 var e_obj = ToObject(e); |
211 return %ToString(e_obj.toLocaleString()); | 210 return %ToString(e_obj.toLocaleString()); |
212 } | 211 } |
213 } | 212 } |
214 | 213 |
215 | 214 |
216 // This function implements the optimized splice implementation that can use | 215 // This function implements the optimized splice implementation that can use |
217 // special array operations to handle sparse arrays in a sensible fashion. | 216 // special array operations to handle sparse arrays in a sensible fashion. |
218 function SmartSlice(array, start_i, del_count, len, deleted_elements) { | 217 function SmartSlice(array, start_i, del_count, len, deleted_elements) { |
219 // Move deleted elements to a new array (the return value from splice). | 218 // Move deleted elements to a new array (the return value from splice). |
220 // Intervals array can contain keys and intervals. See comment in Concat. | 219 var indices = %GetArrayKeys(array, start_i + del_count); |
221 var intervals = %GetArrayKeys(array, start_i + del_count); | 220 if (IS_NUMBER(indices)) { |
222 var length = intervals.length; | 221 var limit = indices; |
223 for (var k = 0; k < length; k++) { | 222 for (var i = start_i; i < limit; ++i) { |
224 var key = intervals[k]; | 223 var current = array[i]; |
225 if (key < 0) { | 224 if (!IS_UNDEFINED(current) || i in array) { |
226 var j = -1 - key; | 225 deleted_elements[i - start_i] = current; |
227 var interval_limit = j + intervals[++k]; | |
228 if (j < start_i) { | |
229 j = start_i; | |
230 } | 226 } |
231 for (; j < interval_limit; j++) { | 227 } |
232 // ECMA-262 15.4.4.12 line 10. The spec could also be | 228 } else { |
233 // interpreted such that %HasLocalProperty would be the | 229 var length = indices.length; |
234 // appropriate test. We follow KJS in consulting the | 230 for (var k = 0; k < length; ++k) { |
235 // prototype. | 231 var key = indices[k]; |
236 var current = array[j]; | |
237 if (!IS_UNDEFINED(current) || j in array) { | |
238 deleted_elements[j - start_i] = current; | |
239 } | |
240 } | |
241 } else { | |
242 if (!IS_UNDEFINED(key)) { | 232 if (!IS_UNDEFINED(key)) { |
243 if (key >= start_i) { | 233 if (key >= start_i) { |
244 // ECMA-262 15.4.4.12 line 10. The spec could also be | |
245 // interpreted such that %HasLocalProperty would be the | |
246 // appropriate test. We follow KJS in consulting the | |
247 // prototype. | |
248 var current = array[key]; | 234 var current = array[key]; |
249 if (!IS_UNDEFINED(current) || key in array) { | 235 if (!IS_UNDEFINED(current) || key in array) { |
250 deleted_elements[key - start_i] = current; | 236 deleted_elements[key - start_i] = current; |
251 } | 237 } |
252 } | 238 } |
253 } | 239 } |
254 } | 240 } |
255 } | 241 } |
256 } | 242 } |
257 | 243 |
258 | 244 |
259 // This function implements the optimized splice implementation that can use | 245 // This function implements the optimized splice implementation that can use |
260 // special array operations to handle sparse arrays in a sensible fashion. | 246 // special array operations to handle sparse arrays in a sensible fashion. |
261 function SmartMove(array, start_i, del_count, len, num_additional_args) { | 247 function SmartMove(array, start_i, del_count, len, num_additional_args) { |
262 // Move data to new array. | 248 // Move data to new array. |
263 var new_array = new InternalArray(len - del_count + num_additional_args); | 249 var new_array = new InternalArray(len - del_count + num_additional_args); |
264 var intervals = %GetArrayKeys(array, len); | 250 var indices = %GetArrayKeys(array, len); |
265 var length = intervals.length; | 251 if (IS_NUMBER(indices)) { |
266 for (var k = 0; k < length; k++) { | 252 var limit = indices; |
267 var key = intervals[k]; | 253 for (var i = 0; i < start_i && i < limit; ++i) { |
268 if (key < 0) { | 254 var current = array[i]; |
269 var j = -1 - key; | 255 if (!IS_UNDEFINED(current) || i in array) { |
270 var interval_limit = j + intervals[++k]; | 256 new_array[i] = current; |
271 while (j < start_i && j < interval_limit) { | |
272 // The spec could also be interpreted such that | |
273 // %HasLocalProperty would be the appropriate test. We follow | |
274 // KJS in consulting the prototype. | |
275 var current = array[j]; | |
276 if (!IS_UNDEFINED(current) || j in array) { | |
277 new_array[j] = current; | |
278 } | |
279 j++; | |
280 } | 257 } |
281 j = start_i + del_count; | 258 } |
282 while (j < interval_limit) { | 259 for (var i = start_i + del_count; i < limit; ++i) { |
283 // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also be | 260 var current = array[i]; |
284 // interpreted such that %HasLocalProperty would be the | 261 if (!IS_UNDEFINED(current) || i in array) { |
285 // appropriate test. We follow KJS in consulting the | 262 new_array[i - del_count + num_additional_args] = current; |
286 // prototype. | |
287 var current = array[j]; | |
288 if (!IS_UNDEFINED(current) || j in array) { | |
289 new_array[j - del_count + num_additional_args] = current; | |
290 } | |
291 j++; | |
292 } | 263 } |
293 } else { | 264 } |
| 265 } else { |
| 266 var length = indices.length; |
| 267 for (var k = 0; k < length; ++k) { |
| 268 var key = indices[k]; |
294 if (!IS_UNDEFINED(key)) { | 269 if (!IS_UNDEFINED(key)) { |
295 if (key < start_i) { | 270 if (key < start_i) { |
296 // The spec could also be interpreted such that | |
297 // %HasLocalProperty would be the appropriate test. We follow | |
298 // KJS in consulting the prototype. | |
299 var current = array[key]; | 271 var current = array[key]; |
300 if (!IS_UNDEFINED(current) || key in array) { | 272 if (!IS_UNDEFINED(current) || key in array) { |
301 new_array[key] = current; | 273 new_array[key] = current; |
302 } | 274 } |
303 } else if (key >= start_i + del_count) { | 275 } else if (key >= start_i + del_count) { |
304 // ECMA-262 15.4.4.12 lines 24 and 41. The spec could also | |
305 // be interpreted such that %HasLocalProperty would be the | |
306 // appropriate test. We follow KJS in consulting the | |
307 // prototype. | |
308 var current = array[key]; | 276 var current = array[key]; |
309 if (!IS_UNDEFINED(current) || key in array) { | 277 if (!IS_UNDEFINED(current) || key in array) { |
310 new_array[key - del_count + num_additional_args] = current; | 278 new_array[key - del_count + num_additional_args] = current; |
311 } | 279 } |
312 } | 280 } |
313 } | 281 } |
314 } | 282 } |
315 } | 283 } |
316 // Move contents of new_array into this array | 284 // Move contents of new_array into this array |
317 %MoveArrayContents(new_array, array); | 285 %MoveArrayContents(new_array, array); |
(...skipping 562 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
880 } | 848 } |
881 }; | 849 }; |
882 | 850 |
883 // Copy elements in the range 0..length from obj's prototype chain | 851 // Copy elements in the range 0..length from obj's prototype chain |
884 // to obj itself, if obj has holes. Return one more than the maximal index | 852 // to obj itself, if obj has holes. Return one more than the maximal index |
885 // of a prototype property. | 853 // of a prototype property. |
886 var CopyFromPrototype = function CopyFromPrototype(obj, length) { | 854 var CopyFromPrototype = function CopyFromPrototype(obj, length) { |
887 var max = 0; | 855 var max = 0; |
888 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) { | 856 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) { |
889 var indices = %GetArrayKeys(proto, length); | 857 var indices = %GetArrayKeys(proto, length); |
890 if (indices.length > 0) { | 858 if (IS_NUMBER(indices)) { |
891 if (indices[0] == -1) { | 859 // It's an interval. |
892 // It's an interval. | 860 var proto_length = indices; |
893 var proto_length = indices[1]; | 861 for (var i = 0; i < proto_length; i++) { |
894 for (var i = 0; i < proto_length; i++) { | 862 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { |
895 if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) { | 863 obj[i] = proto[i]; |
896 obj[i] = proto[i]; | 864 if (i >= max) { max = i + 1; } |
897 if (i >= max) { max = i + 1; } | |
898 } | |
899 } | 865 } |
900 } else { | 866 } |
901 for (var i = 0; i < indices.length; i++) { | 867 } else { |
902 var index = indices[i]; | 868 for (var i = 0; i < indices.length; i++) { |
903 if (!IS_UNDEFINED(index) && | 869 var index = indices[i]; |
904 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { | 870 if (!IS_UNDEFINED(index) && |
905 obj[index] = proto[index]; | 871 !obj.hasOwnProperty(index) && proto.hasOwnProperty(index)) { |
906 if (index >= max) { max = index + 1; } | 872 obj[index] = proto[index]; |
907 } | 873 if (index >= max) { max = index + 1; } |
908 } | 874 } |
909 } | 875 } |
910 } | 876 } |
911 } | 877 } |
912 return max; | 878 return max; |
913 }; | 879 }; |
914 | 880 |
915 // Set a value of "undefined" on all indices in the range from..to | 881 // Set a value of "undefined" on all indices in the range from..to |
916 // where a prototype of obj has an element. I.e., shadow all prototype | 882 // where a prototype of obj has an element. I.e., shadow all prototype |
917 // elements in that range. | 883 // elements in that range. |
918 var ShadowPrototypeElements = function(obj, from, to) { | 884 var ShadowPrototypeElements = function(obj, from, to) { |
919 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) { | 885 for (var proto = %GetPrototype(obj); proto; proto = %GetPrototype(proto)) { |
920 var indices = %GetArrayKeys(proto, to); | 886 var indices = %GetArrayKeys(proto, to); |
921 if (indices.length > 0) { | 887 if (IS_NUMBER(indices)) { |
922 if (indices[0] == -1) { | 888 // It's an interval. |
923 // It's an interval. | 889 var proto_length = indices; |
924 var proto_length = indices[1]; | 890 for (var i = from; i < proto_length; i++) { |
925 for (var i = from; i < proto_length; i++) { | 891 if (proto.hasOwnProperty(i)) { |
926 if (proto.hasOwnProperty(i)) { | 892 obj[i] = void 0; |
927 obj[i] = void 0; | |
928 } | |
929 } | 893 } |
930 } else { | 894 } |
931 for (var i = 0; i < indices.length; i++) { | 895 } else { |
932 var index = indices[i]; | 896 for (var i = 0; i < indices.length; i++) { |
933 if (!IS_UNDEFINED(index) && from <= index && | 897 var index = indices[i]; |
934 proto.hasOwnProperty(index)) { | 898 if (!IS_UNDEFINED(index) && from <= index && |
935 obj[index] = void 0; | 899 proto.hasOwnProperty(index)) { |
936 } | 900 obj[index] = void 0; |
937 } | 901 } |
938 } | 902 } |
939 } | 903 } |
940 } | 904 } |
941 }; | 905 }; |
942 | 906 |
943 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) { | 907 var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) { |
944 // Copy defined elements from the end to fill in all holes and undefineds | 908 // Copy defined elements from the end to fill in all holes and undefineds |
945 // in the beginning of the array. Write undefineds and holes at the end | 909 // in the beginning of the array. Write undefineds and holes at the end |
946 // after loop is finished. | 910 // after loop is finished. |
(...skipping 330 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1277 // If index is negative, index from the end of the array. | 1241 // If index is negative, index from the end of the array. |
1278 if (index < 0) { | 1242 if (index < 0) { |
1279 index = length + index; | 1243 index = length + index; |
1280 // If index is still negative, search the entire array. | 1244 // If index is still negative, search the entire array. |
1281 if (index < 0) index = 0; | 1245 if (index < 0) index = 0; |
1282 } | 1246 } |
1283 } | 1247 } |
1284 var min = index; | 1248 var min = index; |
1285 var max = length; | 1249 var max = length; |
1286 if (UseSparseVariant(this, length, IS_ARRAY(this))) { | 1250 if (UseSparseVariant(this, length, IS_ARRAY(this))) { |
1287 var intervals = %GetArrayKeys(this, length); | 1251 var indices = %GetArrayKeys(this, length); |
1288 if (intervals.length == 2 && intervals[0] < 0) { | 1252 if (IS_NUMBER(indices)) { |
1289 // A single interval. | 1253 // It's an interval. |
1290 var intervalMin = -(intervals[0] + 1); | 1254 max = indices; // Capped by length already. |
1291 var intervalMax = intervalMin + intervals[1]; | |
1292 if (min < intervalMin) min = intervalMin; | |
1293 max = intervalMax; // Capped by length already. | |
1294 // Fall through to loop below. | 1255 // Fall through to loop below. |
1295 } else { | 1256 } else { |
1296 if (intervals.length == 0) return -1; | 1257 if (indices.length == 0) return -1; |
1297 // Get all the keys in sorted order. | 1258 // Get all the keys in sorted order. |
1298 var sortedKeys = GetSortedArrayKeys(this, intervals); | 1259 var sortedKeys = GetSortedArrayKeys(this, indices); |
1299 var n = sortedKeys.length; | 1260 var n = sortedKeys.length; |
1300 var i = 0; | 1261 var i = 0; |
1301 while (i < n && sortedKeys[i] < index) i++; | 1262 while (i < n && sortedKeys[i] < index) i++; |
1302 while (i < n) { | 1263 while (i < n) { |
1303 var key = sortedKeys[i]; | 1264 var key = sortedKeys[i]; |
1304 if (!IS_UNDEFINED(key) && this[key] === element) return key; | 1265 if (!IS_UNDEFINED(key) && this[key] === element) return key; |
1305 i++; | 1266 i++; |
1306 } | 1267 } |
1307 return -1; | 1268 return -1; |
1308 } | 1269 } |
(...skipping 29 matching lines...) Expand all Loading... |
1338 index = TO_INTEGER(index); | 1299 index = TO_INTEGER(index); |
1339 // If index is negative, index from end of the array. | 1300 // If index is negative, index from end of the array. |
1340 if (index < 0) index += length; | 1301 if (index < 0) index += length; |
1341 // If index is still negative, do not search the array. | 1302 // If index is still negative, do not search the array. |
1342 if (index < 0) return -1; | 1303 if (index < 0) return -1; |
1343 else if (index >= length) index = length - 1; | 1304 else if (index >= length) index = length - 1; |
1344 } | 1305 } |
1345 var min = 0; | 1306 var min = 0; |
1346 var max = index; | 1307 var max = index; |
1347 if (UseSparseVariant(this, length, IS_ARRAY(this))) { | 1308 if (UseSparseVariant(this, length, IS_ARRAY(this))) { |
1348 var intervals = %GetArrayKeys(this, index + 1); | 1309 var indices = %GetArrayKeys(this, index + 1); |
1349 if (intervals.length == 2 && intervals[0] < 0) { | 1310 if (IS_NUMBER(indices)) { |
1350 // A single interval. | 1311 // It's an interval. |
1351 var intervalMin = -(intervals[0] + 1); | 1312 max = indices; // Capped by index already. |
1352 var intervalMax = intervalMin + intervals[1]; | |
1353 if (min < intervalMin) min = intervalMin; | |
1354 max = intervalMax; // Capped by index already. | |
1355 // Fall through to loop below. | 1313 // Fall through to loop below. |
1356 } else { | 1314 } else { |
1357 if (intervals.length == 0) return -1; | 1315 if (indices.length == 0) return -1; |
1358 // Get all the keys in sorted order. | 1316 // Get all the keys in sorted order. |
1359 var sortedKeys = GetSortedArrayKeys(this, intervals); | 1317 var sortedKeys = GetSortedArrayKeys(this, indices); |
1360 var i = sortedKeys.length - 1; | 1318 var i = sortedKeys.length - 1; |
1361 while (i >= 0) { | 1319 while (i >= 0) { |
1362 var key = sortedKeys[i]; | 1320 var key = sortedKeys[i]; |
1363 if (!IS_UNDEFINED(key) && this[key] === element) return key; | 1321 if (!IS_UNDEFINED(key) && this[key] === element) return key; |
1364 i--; | 1322 i--; |
1365 } | 1323 } |
1366 return -1; | 1324 return -1; |
1367 } | 1325 } |
1368 } | 1326 } |
1369 // Lookup through the array. | 1327 // Lookup through the array. |
(...skipping 192 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1562 )); | 1520 )); |
1563 | 1521 |
1564 SetUpLockedPrototype(InternalPackedArray, $Array(), $Array( | 1522 SetUpLockedPrototype(InternalPackedArray, $Array(), $Array( |
1565 "join", getFunction("join", ArrayJoin), | 1523 "join", getFunction("join", ArrayJoin), |
1566 "pop", getFunction("pop", ArrayPop), | 1524 "pop", getFunction("pop", ArrayPop), |
1567 "push", getFunction("push", ArrayPush) | 1525 "push", getFunction("push", ArrayPush) |
1568 )); | 1526 )); |
1569 } | 1527 } |
1570 | 1528 |
1571 SetUpArray(); | 1529 SetUpArray(); |
OLD | NEW |