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 74 for (var xb = 1; xb <= 1000 * 1000 * 1000; xb *= 10) { 75 for (var xf = 0; xf <= 9; xf++) { 76 for (var xo = -1; xo <= 1; xo++) { 77 for (var yb = 1; yb <= 1000 * 1000 * 1000; yb *= 10) { 78 for (var yf = 0; yf <= 9; yf++) { 79 for (var yo = -1; yo <= 1; yo++) { 80 var x = xb * xf + xo; 81 var y = yb * yf + yo; 82 if (!%_IsSmi(x)) continue; 83 if (!%_IsSmi(y)) continue; 84 var lex = %SmiLexicographicCompare(x, y); 85 if (lex < 0) lex = -1; 86 if (lex > 0) lex = 1; 87 assertEquals(lex, (x == y) ? 0 : ((x + "") < (y + "") ? -1 : 1), x + " < " + y); 88 } 89 } 90 } 91 } 92 } 93 } 94 } 95 96 TestNumberSort(); 97 98 99 // Test lexicographical string sorting. 100 function TestStringSort() { 101 var a = [ "cc", "c", "aa", "a", "bb", "b", "ab", "ac" ]; 102 a.sort(); 103 assertArrayEquals([ "a", "aa", "ab", "ac", "b", "bb", "c", "cc" ], a); 104 } 105 106 TestStringSort(); 107 108 109 // Test object sorting. Calls toString on each element and sorts 110 // lexicographically. 111 function TestObjectSort() { 112 var obj0 = { toString: function() { return "a"; } }; 113 var obj1 = { toString: function() { return "b"; } }; 114 var obj2 = { toString: function() { return "c"; } }; 115 var a = [ obj2, obj0, obj1 ]; 116 a.sort(); 117 assertArrayEquals([ obj0, obj1, obj2 ], a); 118 } 119 120 TestObjectSort(); 121 122 // Test array sorting with holes in the array. 123 function TestArraySortingWithHoles() { 124 var a = []; 125 a[4] = "18"; 126 a[10] = "12"; 127 a.sort(); 128 assertEquals(11, a.length); 129 assertEquals("12", a[0]); 130 assertEquals("18", a[1]); 131 } 132 133 TestArraySortingWithHoles(); 134 135 // Test array sorting with undefined elemeents in the array. 136 function TestArraySortingWithUndefined() { 137 var a = [ 3, void 0, 2 ]; 138 a.sort(); 139 assertArrayEquals([ 2, 3, void 0 ], a); 140 } 141 142 TestArraySortingWithUndefined(); 143 144 // Test that sorting using an unsound comparison function still gives a 145 // sane result, i.e. it terminates without error and retains the elements 146 // in the array. 147 function TestArraySortingWithUnsoundComparisonFunction() { 148 var a = [ 3, void 0, 2 ]; 149 a.sort(function(x, y) { return 1; }); 150 a.sort(); 151 assertArrayEquals([ 2, 3, void 0 ], a); 152 } 153 154 TestArraySortingWithUnsoundComparisonFunction(); 155 156 157 function TestSparseNonArraySorting(length) { 158 assertTrue(length > 101); 159 var obj = {length: length}; 160 obj[0] = 42; 161 obj[10] = 37; 162 obj[100] = undefined; 163 obj[length - 1] = null; 164 Array.prototype.sort.call(obj); 165 assertEquals(length, obj.length, "objsort length unaffected"); 166 assertEquals(37, obj[0], "objsort smallest number"); 167 assertEquals(42, obj[1], "objsort largest number"); 168 assertEquals(null, obj[2], "objsort null"); 169 assertEquals(undefined, obj[3], "objsort undefined"); 170 assertTrue(3 in obj, "objsort undefined retained"); 171 assertFalse(4 in obj, "objsort non-existing retained"); 172 } 173 174 TestSparseNonArraySorting(5000); 175 TestSparseNonArraySorting(500000); 176 TestSparseNonArraySorting(Math.pow(2, 31) + 1); 177 178 179 function TestArrayLongerLength(length) { 180 var x = new Array(4); 181 x[0] = 42; 182 x[2] = 37; 183 x.length = length; 184 Array.prototype.sort.call(x); 185 assertEquals(length, x.length, "longlength length"); 186 assertEquals(37, x[0], "longlength first"); 187 assertEquals(42, x[1], "longlength second"); 188 assertFalse(2 in x,"longlength third"); 189 } 190 191 TestArrayLongerLength(4); 192 TestArrayLongerLength(10); 193 TestArrayLongerLength(1000); 194 TestArrayLongerLength(500000); 195 TestArrayLongerLength(Math.pow(2,32) - 1); 196 197 198 function TestNonArrayLongerLength(length) { 199 var x = {}; 200 x[0] = 42; 201 x[2] = 37; 202 x.length = length; 203 Array.prototype.sort.call(x); 204 assertEquals(length, x.length, "longlength length"); 205 assertEquals(37, x[0], "longlength first"); 206 assertEquals(42, x[1], "longlength second"); 207 assertFalse(2 in x,"longlength third"); 208 } 209 210 TestNonArrayLongerLength(4); 211 TestNonArrayLongerLength(10); 212 TestNonArrayLongerLength(1000); 213 TestNonArrayLongerLength(500000); 214 TestNonArrayLongerLength(Math.pow(2,32) - 1); 215 216 217 function TestNonArrayWithAccessors() { 218 // Regression test for issue 346, more info at URL 219 // http://code.google.com/p/v8/issues/detail?id=346 220 // Reported by nth10sd, test based on this report. 221 var x = {}; 222 x[0] = 42; 223 x.__defineGetter__("1", function(){return this.foo;}); 224 x.__defineSetter__("1", function(val){this.foo = val;}); 225 x[1] = 49 226 x[3] = 37; 227 x.length = 4; 228 Array.prototype.sort.call(x); 229 // Behavior of sort with accessors is undefined. This accessor is 230 // well-behaved (acts like a normal property), so it should work. 231 assertEquals(4, x.length, "sortaccessors length"); 232 assertEquals(37, x[0], "sortaccessors first"); 233 assertEquals(42, x[1], "sortaccessors second"); 234 assertEquals(49, x[2], "sortaccessors third") 235 assertFalse(3 in x, "sortaccessors fourth"); 236 } 237 238 TestNonArrayWithAccessors(); 239 240 241 function TestInheritedElementSort(depth) { 242 var length = depth * 2 + 3; 243 var obj = {length: length}; 244 obj[depth * 2 + 1] = 0; 245 for (var i = 0; i < depth; i++) { 246 var newObj = {}; 247 newObj.__proto__ = obj; 248 obj[i] = undefined; 249 obj[i + depth + 1] = depth - i; 250 obj = newObj; 251 } 252 // expected (inherited) object: [undef1,...undefdepth,hole,1,...,depth,0,hole] 253 254 Array.prototype.sort.call(obj, function(a,b) { return (b < a) - (a < b); }); 255 // expected result: [0,1,...,depth,undef1,...,undefdepth,undef,hole] 256 var name = "SortInherit("+depth+")-"; 257 258 assertEquals(length, obj.length, name+"length"); 259 for (var i = 0; i <= depth; i++) { 260 assertTrue(obj.hasOwnProperty(i), name + "hasvalue" + i); 261 assertEquals(i, obj[i], name + "value" + i); 262 } 263 for (var i = depth + 1; i <= depth * 2 + 1; i++) { 264 assertEquals(undefined, obj[i], name + "undefined" + i); 265 assertTrue(obj.hasOwnProperty(i), name + "hasundefined" + i); 266 } 267 assertTrue(!obj.hasOwnProperty(depth * 2 + 2), name + "hashole"); 268 } 269 270 TestInheritedElementSort(5); 271 TestInheritedElementSort(15); 272 273 function TestSparseInheritedElementSort(scale) { 274 var length = scale * 10; 275 var x = {length: length}; 276 var y = {}; 277 y.__proto__ = x; 278 279 for (var i = 0; i < 5; i++) { 280 x[i * 2 * scale] = 2 * (4 - i); 281 y[(i * 2 + 1) * scale] = 2 * (4 - i) + 1; 282 } 283 284 var name = "SparseSortInherit(" + scale + ")-"; 285 286 Array.prototype.sort.call(y); 287 288 assertEquals(length, y.length, name +"length"); 289 290 for (var i = 0; i < 10; i++) { 291 assertTrue(y.hasOwnProperty(i), name + "hasvalue" + i); 292 assertEquals(i, y[i], name + "value" + i); 293 } 294 for (var i = 10; i < length; i++) { 295 assertEquals(x.hasOwnProperty(i), y.hasOwnProperty(i), 296 name + "hasundef" + i); 297 assertEquals(undefined, y[i], name+"undefined"+i); 298 if (x.hasOwnProperty(i)) { 299 assertTrue(0 == i % (2 * scale), name + "new_x" + i); 300 } 301 } 302 } 303 304 TestSparseInheritedElementSort(10); 305 TestSparseInheritedElementSort(100); 306 TestSparseInheritedElementSort(1000); 307 308 function TestSpecialCasesInheritedElementSort() { 309 310 var x = { 311 1:"d1", 312 2:"c1", 313 3:"b1", 314 4: undefined, 315 __proto__: { 316 length: 10000, 317 1: "e2", 318 10: "a2", 319 100: "b2", 320 1000: "c2", 321 2000: undefined, 322 8000: "d2", 323 12000: "XX", 324 __proto__: { 325 0: "e3", 326 1: "d3", 327 2: "c3", 328 3: "b3", 329 4: "f3", 330 5: "a3", 331 6: undefined, 332 } 333 } 334 }; 335 Array.prototype.sort.call(x); 336 337 var name = "SpecialInherit-"; 338 339 assertEquals(10000, x.length, name + "length"); 340 var sorted = ["a2", "a3", "b1", "b2", "c1", "c2", "d1", "d2", "e3", 341 undefined, undefined, undefined]; 342 for (var i = 0; i < sorted.length; i++) { 343 assertTrue(x.hasOwnProperty(i), name + "has" + i) 344 assertEquals(sorted[i], x[i], name + i); 345 } 346 assertFalse(x.hasOwnProperty(sorted.length), name + "haspost"); 347 assertFalse(sorted.length in x, name + "haspost2"); 348 assertTrue(x.hasOwnProperty(10), name + "hasundefined10"); 349 assertEquals(undefined, x[10], name + "undefined10"); 350 assertTrue(x.hasOwnProperty(100), name + "hasundefined100"); 351 assertEquals(undefined, x[100], name + "undefined100"); 352 assertTrue(x.hasOwnProperty(1000), name + "hasundefined1000"); 353 assertEquals(undefined, x[1000], name + "undefined1000"); 354 assertTrue(x.hasOwnProperty(2000), name + "hasundefined2000"); 355 assertEquals(undefined, x[2000], name + "undefined2000"); 356 assertTrue(x.hasOwnProperty(8000), name + "hasundefined8000"); 357 assertEquals(undefined, x[8000], name + "undefined8000"); 358 assertFalse(x.hasOwnProperty(12000), name + "has12000"); 359 assertEquals("XX", x[12000], name + "XX12000"); 360 } 361 362 TestSpecialCasesInheritedElementSort(); 363 364 // Test that sort calls compare function with global object as receiver, 365 // and with only elements of the array as arguments. 366 function o(v) { 367 return {__proto__: o.prototype, val: v}; 368 } 369 var arr = [o(1), o(2), o(4), o(8), o(16), o(32), o(64), o(128), o(256), o(-0)]; 370 var global = this; 371 function cmpTest(a, b) { 372 assertEquals(global, this); 373 assertTrue(a instanceof o); 374 assertTrue(b instanceof o); 375 return a.val - b.val; 376 } 377 arr.sort(cmpTest);