1 // Copyright 2010 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 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. 27 28 // Flags: --allow-natives-syntax 29 30 // Test array sort. 31 32 // Test counter-intuitive default number sorting. 33 function TestNumberSort() { 34 var a = [ 200, 45, 7 ]; 35 36 // Default sort converts each element to string and orders 37 // lexicographically. 38 a.sort(); 39 assertArrayEquals([ 200, 45, 7 ], a); 40 // Sort numbers by value using a compare functions. 41 a.sort(function(x, y) { return x - y; }); 42 assertArrayEquals([ 7, 45, 200 ], a); 43 44 // Default sort on negative numbers. 45 a = [-12345,-123,-1234,-123456]; 46 a.sort(); 47 assertArrayEquals([-123,-1234,-12345,-123456], a); 48 49 // Default sort on negative and non-negative numbers. 50 a = [123456,0,-12345,-123,123,1234,-1234,0,12345,-123456]; 51 a.sort(); 52 assertArrayEquals([-123,-1234,-12345,-123456,0,0,123,1234,12345,123456], a); 53 54 // Tricky case avoiding integer overflow in Runtime_SmiLexicographicCompare. 55 a = [9, 1000000000].sort(); 56 assertArrayEquals([1000000000, 9], a); 57 a = [1000000000, 1].sort(); 58 assertArrayEquals([1, 1000000000], a); 59 a = [1000000000, 0].sort(); 60 assertArrayEquals([0, 1000000000], a); 61 62 // One string is a prefix of the other. 63 a = [1230, 123].sort(); 64 assertArrayEquals([123, 1230], a); 65 a = [1231, 123].sort(); 66 assertArrayEquals([123, 1231], a); 67 68 // Default sort on Smis and non-Smis. 69 a = [1000000000, 10000000000, 1000000001, -1000000000, -10000000000, -1000000001]; 70 a.sort(); 71 assertArrayEquals([-1000000000, -10000000000, -1000000001, 1000000000, 10000000000, 1000000001], a); 72 73 // Other cases are tested implicitly in TestSmiLexicographicCompare. 74 } 75 76 TestNumberSort(); 77 78 function TestSmiLexicographicCompare() { 79 80 assertFalse(%_IsSmi(2147483648), 'Update test for >32 bit Smi'); 81 82 // Collect a list of interesting Smis. 83 var seen = {}; 84 var smis = []; 85 function add(x) { 86 if (x | 0 == x) { 87 x = x | 0; // Canonicalizes to Smi if 32-bit signed and fits in Smi. 88 } 89 if (%_IsSmi(x) && !seen[x]) { 90 seen[x] = 1; 91 smis.push(x); 92 } 93 } 94 function addSigned(x) { 95 add(x); 96 add(-x); 97 } 98 99 var BIGGER_THAN_ANY_SMI = 10 * 1000 * 1000 * 1000; 100 for (var xb = 1; xb <= BIGGER_THAN_ANY_SMI; xb *= 10) { 101 for (var xf = 0; xf <= 9; xf++) { 102 for (var xo = -1; xo <= 1; xo++) { 103 addSigned(xb * xf + xo); 104 } 105 } 106 } 107 108 for (var yb = 1; yb <= BIGGER_THAN_ANY_SMI; yb *= 2) { 109 for (var yo = -2; yo <= 2; yo++) { 110 addSigned(yb + yo); 111 } 112 } 113 114 for (var i = 0; i < smis.length; i++) { 115 for (var j = 0; j < smis.length; j++) { 116 var x = smis[i]; 117 var y = smis[j]; 118 var lex = %SmiLexicographicCompare(x, y); 119 var expected = (x == y) ? 0 : ((x + "") < (y + "") ? -1 : 1); 120 assertEquals(lex, expected, x + " < " + y); 121 } 122 } 123 } 124 125 TestSmiLexicographicCompare(); 126 127 128 // Test lexicographical string sorting. 129 function TestStringSort() { 130 var a = [ "cc", "c", "aa", "a", "bb", "b", "ab", "ac" ]; 131 a.sort(); 132 assertArrayEquals([ "a", "aa", "ab", "ac", "b", "bb", "c", "cc" ], a); 133 } 134 135 TestStringSort(); 136 137 138 // Test object sorting. Calls toString on each element and sorts 139 // lexicographically. 140 function TestObjectSort() { 141 var obj0 = { toString: function() { return "a"; } }; 142 var obj1 = { toString: function() { return "b"; } }; 143 var obj2 = { toString: function() { return "c"; } }; 144 var a = [ obj2, obj0, obj1 ]; 145 a.sort(); 146 assertArrayEquals([ obj0, obj1, obj2 ], a); 147 } 148 149 TestObjectSort(); 150 151 // Test array sorting with holes in the array. 152 function TestArraySortingWithHoles() { 153 var a = []; 154 a[4] = "18"; 155 a[10] = "12"; 156 a.sort(); 157 assertEquals(11, a.length); 158 assertEquals("12", a[0]); 159 assertEquals("18", a[1]); 160 } 161 162 TestArraySortingWithHoles(); 163 164 // Test array sorting with undefined elemeents in the array. 165 function TestArraySortingWithUndefined() { 166 var a = [ 3, void 0, 2 ]; 167 a.sort(); 168 assertArrayEquals([ 2, 3, void 0 ], a); 169 } 170 171 TestArraySortingWithUndefined(); 172 173 // Test that sorting using an unsound comparison function still gives a 174 // sane result, i.e. it terminates without error and retains the elements 175 // in the array. 176 function TestArraySortingWithUnsoundComparisonFunction() { 177 var a = [ 3, void 0, 2 ]; 178 a.sort(function(x, y) { return 1; }); 179 a.sort(); 180 assertArrayEquals([ 2, 3, void 0 ], a); 181 } 182 183 TestArraySortingWithUnsoundComparisonFunction(); 184 185 186 function TestSparseNonArraySorting(length) { 187 assertTrue(length > 101); 188 var obj = {length: length}; 189 obj[0] = 42; 190 obj[10] = 37; 191 obj[100] = undefined; 192 obj[length - 1] = null; 193 Array.prototype.sort.call(obj); 194 assertEquals(length, obj.length, "objsort length unaffected"); 195 assertEquals(37, obj[0], "objsort smallest number"); 196 assertEquals(42, obj[1], "objsort largest number"); 197 assertEquals(null, obj[2], "objsort null"); 198 assertEquals(undefined, obj[3], "objsort undefined"); 199 assertTrue(3 in obj, "objsort undefined retained"); 200 assertFalse(4 in obj, "objsort non-existing retained"); 201 } 202 203 TestSparseNonArraySorting(5000); 204 TestSparseNonArraySorting(500000); 205 TestSparseNonArraySorting(Math.pow(2, 31) + 1); 206 207 208 function TestArrayLongerLength(length) { 209 var x = new Array(4); 210 x[0] = 42; 211 x[2] = 37; 212 x.length = length; 213 Array.prototype.sort.call(x); 214 assertEquals(length, x.length, "longlength length"); 215 assertEquals(37, x[0], "longlength first"); 216 assertEquals(42, x[1], "longlength second"); 217 assertFalse(2 in x,"longlength third"); 218 } 219 220 TestArrayLongerLength(4); 221 TestArrayLongerLength(10); 222 TestArrayLongerLength(1000); 223 TestArrayLongerLength(500000); 224 TestArrayLongerLength(Math.pow(2,32) - 1); 225 226 227 function TestNonArrayLongerLength(length) { 228 var x = {}; 229 x[0] = 42; 230 x[2] = 37; 231 x.length = length; 232 Array.prototype.sort.call(x); 233 assertEquals(length, x.length, "longlength length"); 234 assertEquals(37, x[0], "longlength first"); 235 assertEquals(42, x[1], "longlength second"); 236 assertFalse(2 in x,"longlength third"); 237 } 238 239 TestNonArrayLongerLength(4); 240 TestNonArrayLongerLength(10); 241 TestNonArrayLongerLength(1000); 242 TestNonArrayLongerLength(500000); 243 TestNonArrayLongerLength(Math.pow(2,32) - 1); 244 245 246 function TestNonArrayWithAccessors() { 247 // Regression test for issue 346, more info at URL 248 // http://code.google.com/p/v8/issues/detail?id=346 249 // Reported by nth10sd, test based on this report. 250 var x = {}; 251 x[0] = 42; 252 x.__defineGetter__("1", function(){return this.foo;}); 253 x.__defineSetter__("1", function(val){this.foo = val;}); 254 x[1] = 49 255 x[3] = 37; 256 x.length = 4; 257 Array.prototype.sort.call(x); 258 // Behavior of sort with accessors is undefined. This accessor is 259 // well-behaved (acts like a normal property), so it should work. 260 assertEquals(4, x.length, "sortaccessors length"); 261 assertEquals(37, x[0], "sortaccessors first"); 262 assertEquals(42, x[1], "sortaccessors second"); 263 assertEquals(49, x[2], "sortaccessors third") 264 assertFalse(3 in x, "sortaccessors fourth"); 265 } 266 267 TestNonArrayWithAccessors(); 268 269 270 function TestInheritedElementSort(depth) { 271 var length = depth * 2 + 3; 272 var obj = {length: length}; 273 obj[depth * 2 + 1] = 0; 274 for (var i = 0; i < depth; i++) { 275 var newObj = {}; 276 newObj.__proto__ = obj; 277 obj[i] = undefined; 278 obj[i + depth + 1] = depth - i; 279 obj = newObj; 280 } 281 // expected (inherited) object: [undef1,...undefdepth,hole,1,...,depth,0,hole] 282 283 Array.prototype.sort.call(obj, function(a,b) { return (b < a) - (a < b); }); 284 // expected result: [0,1,...,depth,undef1,...,undefdepth,undef,hole] 285 var name = "SortInherit("+depth+")-"; 286 287 assertEquals(length, obj.length, name+"length"); 288 for (var i = 0; i <= depth; i++) { 289 assertTrue(obj.hasOwnProperty(i), name + "hasvalue" + i); 290 assertEquals(i, obj[i], name + "value" + i); 291 } 292 for (var i = depth + 1; i <= depth * 2 + 1; i++) { 293 assertEquals(undefined, obj[i], name + "undefined" + i); 294 assertTrue(obj.hasOwnProperty(i), name + "hasundefined" + i); 295 } 296 assertTrue(!obj.hasOwnProperty(depth * 2 + 2), name + "hashole"); 297 } 298 299 TestInheritedElementSort(5); 300 TestInheritedElementSort(15); 301 302 function TestSparseInheritedElementSort(scale) { 303 var length = scale * 10; 304 var x = {length: length}; 305 var y = {}; 306 y.__proto__ = x; 307 308 for (var i = 0; i < 5; i++) { 309 x[i * 2 * scale] = 2 * (4 - i); 310 y[(i * 2 + 1) * scale] = 2 * (4 - i) + 1; 311 } 312 313 var name = "SparseSortInherit(" + scale + ")-"; 314 315 Array.prototype.sort.call(y); 316 317 assertEquals(length, y.length, name +"length"); 318 319 for (var i = 0; i < 10; i++) { 320 assertTrue(y.hasOwnProperty(i), name + "hasvalue" + i); 321 assertEquals(i, y[i], name + "value" + i); 322 } 323 for (var i = 10; i < length; i++) { 324 assertEquals(x.hasOwnProperty(i), y.hasOwnProperty(i), 325 name + "hasundef" + i); 326 assertEquals(undefined, y[i], name+"undefined"+i); 327 if (x.hasOwnProperty(i)) { 328 assertTrue(0 == i % (2 * scale), name + "new_x" + i); 329 } 330 } 331 } 332 333 TestSparseInheritedElementSort(10); 334 TestSparseInheritedElementSort(100); 335 TestSparseInheritedElementSort(1000); 336 337 function TestSpecialCasesInheritedElementSort() { 338 339 var x = { 340 1:"d1", 341 2:"c1", 342 3:"b1", 343 4: undefined, 344 __proto__: { 345 length: 10000, 346 1: "e2", 347 10: "a2", 348 100: "b2", 349 1000: "c2", 350 2000: undefined, 351 8000: "d2", 352 12000: "XX", 353 __proto__: { 354 0: "e3", 355 1: "d3", 356 2: "c3", 357 3: "b3", 358 4: "f3", 359 5: "a3", 360 6: undefined, 361 } 362 } 363 }; 364 Array.prototype.sort.call(x); 365 366 var name = "SpecialInherit-"; 367 368 assertEquals(10000, x.length, name + "length"); 369 var sorted = ["a2", "a3", "b1", "b2", "c1", "c2", "d1", "d2", "e3", 370 undefined, undefined, undefined]; 371 for (var i = 0; i < sorted.length; i++) { 372 assertTrue(x.hasOwnProperty(i), name + "has" + i) 373 assertEquals(sorted[i], x[i], name + i); 374 } 375 assertFalse(x.hasOwnProperty(sorted.length), name + "haspost"); 376 assertFalse(sorted.length in x, name + "haspost2"); 377 assertTrue(x.hasOwnProperty(10), name + "hasundefined10"); 378 assertEquals(undefined, x[10], name + "undefined10"); 379 assertTrue(x.hasOwnProperty(100), name + "hasundefined100"); 380 assertEquals(undefined, x[100], name + "undefined100"); 381 assertTrue(x.hasOwnProperty(1000), name + "hasundefined1000"); 382 assertEquals(undefined, x[1000], name + "undefined1000"); 383 assertTrue(x.hasOwnProperty(2000), name + "hasundefined2000"); 384 assertEquals(undefined, x[2000], name + "undefined2000"); 385 assertTrue(x.hasOwnProperty(8000), name + "hasundefined8000"); 386 assertEquals(undefined, x[8000], name + "undefined8000"); 387 assertFalse(x.hasOwnProperty(12000), name + "has12000"); 388 assertEquals("XX", x[12000], name + "XX12000"); 389 } 390 391 TestSpecialCasesInheritedElementSort(); 392 393 // Test that sort calls compare function with global object as receiver, 394 // and with only elements of the array as arguments. 395 function o(v) { 396 return {__proto__: o.prototype, val: v}; 397 } 398 var arr = [o(1), o(2), o(4), o(8), o(16), o(32), o(64), o(128), o(256), o(-0)]; 399 var global = this; 400 function cmpTest(a, b) { 401 assertEquals(global, this); 402 assertTrue(a instanceof o); 403 assertTrue(b instanceof o); 404 return a.val - b.val; 405 } 406 arr.sort(cmpTest); 407 408 function TestSortDoesNotDependOnObjectPrototypeHasOwnProperty() { 409 Array.prototype.sort.call({ 410 __proto__: { hasOwnProperty: null, 0: 1 }, 411 length: 5 412 }); 413 414 var arr = new Array(2); 415 Object.defineProperty(arr, 0, { get: function() {}, set: function() {} }); 416 arr.hasOwnProperty = null; 417 arr.sort(); 418 } 419 420 TestSortDoesNotDependOnObjectPrototypeHasOwnProperty(); 421 422 function TestSortDoesNotDependOnArrayPrototypePush() { 423 // InsertionSort is used for arrays which length <= 22 424 var arr = []; 425 for (var i = 0; i < 22; i++) arr[i] = {}; 426 Array.prototype.push = function() { 427 fail('Should not call push'); 428 }; 429 arr.sort(); 430 431 // Quicksort is used for arrays which length > 22 432 // Arrays which length > 1000 guarantee GetThirdIndex is executed 433 arr = []; 434 for (var i = 0; i < 2000; ++i) arr[i] = {}; 435 arr.sort(); 436 } 437 438 TestSortDoesNotDependOnArrayPrototypePush(); 439 440 function TestSortDoesNotDependOnArrayPrototypeSort() { 441 var arr = []; 442 for (var i = 0; i < 2000; i++) arr[i] = {}; 443 var sortfn = Array.prototype.sort; 444 Array.prototype.sort = function() { 445 fail('Should not call sort'); 446 }; 447 sortfn.call(arr); 448 } 449 450 TestSortDoesNotDependOnArrayPrototypeSort(); 451