ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 1 | // Copyright 2008 the V8 project authors. All rights reserved. |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 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 | |
kasperl@chromium.org | b912362 | 2008-09-17 14:05:56 +0000 | [diff] [blame] | 28 | // Flags: --allow-natives-syntax |
| 29 | |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 30 | // Test array sort. |
| 31 | |
| 32 | // Test counter-intuitive default number sorting. |
| 33 | function TestNumberSort() { |
| 34 | var a = [ 200, 45, 7 ]; |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 35 | |
| 36 | // Default sort converts each element to string and orders |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 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); |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 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 | |
kasperl@chromium.org | b912362 | 2008-09-17 14:05:56 +0000 | [diff] [blame] | 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 | |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 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); |
kasperl@chromium.org | b912362 | 2008-09-17 14:05:56 +0000 | [diff] [blame] | 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 | } |
mads.s.ager@gmail.com | 9a4089a | 2008-09-01 08:55:01 +0000 | [diff] [blame] | 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(); |
kasperl@chromium.org | 41044eb | 2008-10-06 08:24:46 +0000 | [diff] [blame] | 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() { |
ager@chromium.org | 7c537e2 | 2008-10-16 08:43:32 +0000 | [diff] [blame] | 137 | var a = [ 3, void 0, 2 ]; |
kasperl@chromium.org | 41044eb | 2008-10-06 08:24:46 +0000 | [diff] [blame] | 138 | a.sort(); |
ager@chromium.org | 7c537e2 | 2008-10-16 08:43:32 +0000 | [diff] [blame] | 139 | assertArrayEquals([ 2, 3, void 0 ], a); |
kasperl@chromium.org | 41044eb | 2008-10-06 08:24:46 +0000 | [diff] [blame] | 140 | } |
| 141 | |
| 142 | TestArraySortingWithUndefined(); |
ager@chromium.org | 7c537e2 | 2008-10-16 08:43:32 +0000 | [diff] [blame] | 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(); |
ager@chromium.org | 5ec4892 | 2009-05-05 07:25:34 +0000 | [diff] [blame^] | 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 TestInheritedElementSort(depth) { |
| 218 | var length = depth * 2 + 3; |
| 219 | var obj = {length: length}; |
| 220 | obj[depth * 2 + 1] = 0; |
| 221 | for (var i = 0; i < depth; i++) { |
| 222 | var newObj = {}; |
| 223 | newObj.__proto__ = obj; |
| 224 | obj[i] = undefined; |
| 225 | obj[i + depth + 1] = depth - i; |
| 226 | obj = newObj; |
| 227 | } |
| 228 | // expected (inherited) object: [undef1,...undefdepth,hole,1,...,depth,0,hole] |
| 229 | |
| 230 | Array.prototype.sort.call(obj, function(a,b) { return (b < a) - (a < b); }); |
| 231 | // expected result: [0,1,...,depth,undef1,...,undefdepth,undef,hole] |
| 232 | var name = "SortInherit("+depth+")-"; |
| 233 | |
| 234 | assertEquals(length, obj.length, name+"length"); |
| 235 | for (var i = 0; i <= depth; i++) { |
| 236 | assertTrue(obj.hasOwnProperty(i), name + "hasvalue" + i); |
| 237 | assertEquals(i, obj[i], name + "value" + i); |
| 238 | } |
| 239 | for (var i = depth + 1; i <= depth * 2 + 1; i++) { |
| 240 | assertEquals(undefined, obj[i], name + "undefined" + i); |
| 241 | assertTrue(obj.hasOwnProperty(i), name + "hasundefined" + i); |
| 242 | } |
| 243 | assertTrue(!obj.hasOwnProperty(depth * 2 + 2), name + "hashole"); |
| 244 | } |
| 245 | |
| 246 | TestInheritedElementSort(5); |
| 247 | TestInheritedElementSort(15); |
| 248 | |
| 249 | function TestSparseInheritedElementSort(scale) { |
| 250 | var length = scale * 10; |
| 251 | var x = {length: length}; |
| 252 | var y = {}; |
| 253 | y.__proto__ = x; |
| 254 | |
| 255 | for (var i = 0; i < 5; i++) { |
| 256 | x[i * 2 * scale] = 2 * (4 - i); |
| 257 | y[(i * 2 + 1) * scale] = 2 * (4 - i) + 1; |
| 258 | } |
| 259 | |
| 260 | var name = "SparseSortInherit(" + scale + ")-"; |
| 261 | |
| 262 | Array.prototype.sort.call(y); |
| 263 | |
| 264 | assertEquals(length, y.length, name +"length"); |
| 265 | |
| 266 | for (var i = 0; i < 10; i++) { |
| 267 | assertTrue(y.hasOwnProperty(i), name + "hasvalue" + i); |
| 268 | assertEquals(i, y[i], name + "value" + i); |
| 269 | } |
| 270 | for (var i = 10; i < length; i++) { |
| 271 | assertEquals(x.hasOwnProperty(i), y.hasOwnProperty(i), |
| 272 | name + "hasundef" + i); |
| 273 | assertEquals(undefined, y[i], name+"undefined"+i); |
| 274 | if (x.hasOwnProperty(i)) { |
| 275 | assertTrue(0 == i % (2 * scale), name + "new_x" + i); |
| 276 | } |
| 277 | } |
| 278 | } |
| 279 | |
| 280 | TestSparseInheritedElementSort(10); |
| 281 | TestSparseInheritedElementSort(100); |
| 282 | TestSparseInheritedElementSort(1000); |
| 283 | |
| 284 | function TestSpecialCasesInheritedElementSort() { |
| 285 | |
| 286 | var x = { |
| 287 | 1:"d1", |
| 288 | 2:"c1", |
| 289 | 3:"b1", |
| 290 | 4: undefined, |
| 291 | __proto__: { |
| 292 | length: 10000, |
| 293 | 1: "e2", |
| 294 | 10: "a2", |
| 295 | 100: "b2", |
| 296 | 1000: "c2", |
| 297 | 2000: undefined, |
| 298 | 8000: "d2", |
| 299 | 12000: "XX", |
| 300 | __proto__: { |
| 301 | 0: "e3", |
| 302 | 1: "d3", |
| 303 | 2: "c3", |
| 304 | 3: "b3", |
| 305 | 4: "f3", |
| 306 | 5: "a3", |
| 307 | 6: undefined, |
| 308 | } |
| 309 | } |
| 310 | }; |
| 311 | Array.prototype.sort.call(x); |
| 312 | |
| 313 | var name = "SpecialInherit-"; |
| 314 | |
| 315 | assertEquals(10000, x.length, name + "length"); |
| 316 | var sorted = ["a2", "a3", "b1", "b2", "c1", "c2", "d1", "d2", "e3", |
| 317 | undefined, undefined, undefined]; |
| 318 | for (var i = 0; i < sorted.length; i++) { |
| 319 | assertTrue(x.hasOwnProperty(i), name + "has" + i) |
| 320 | assertEquals(sorted[i], x[i], name + i); |
| 321 | } |
| 322 | assertFalse(x.hasOwnProperty(sorted.length), name + "haspost"); |
| 323 | assertFalse(sorted.length in x, name + "haspost2"); |
| 324 | |
| 325 | assertTrue(x.hasOwnProperty(10), name + "hasundefined10"); |
| 326 | assertEquals(undefined, x[10], name + "undefined10"); |
| 327 | assertTrue(x.hasOwnProperty(100), name + "hasundefined100"); |
| 328 | assertEquals(undefined, x[100], name + "undefined100"); |
| 329 | assertTrue(x.hasOwnProperty(1000), name + "hasundefined1000"); |
| 330 | assertEquals(undefined, x[1000], name + "undefined1000"); |
| 331 | assertTrue(x.hasOwnProperty(2000), name + "hasundefined2000"); |
| 332 | assertEquals(undefined, x[2000], name + "undefined2000"); |
| 333 | assertTrue(x.hasOwnProperty(8000), name + "hasundefined8000"); |
| 334 | assertEquals(undefined, x[8000], name + "undefined8000"); |
| 335 | |
| 336 | assertFalse(x.hasOwnProperty(12000), name + "has12000"); |
| 337 | assertEquals("XX", x[12000], name + "XX12000"); |
| 338 | |
| 339 | } |
| 340 | |
| 341 | TestSpecialCasesInheritedElementSort(); |
| 342 | |