19258b6bc66e09368ada54001f619d53b4fc976d5ager@chromium.org// Copyright 2008 the V8 project authors. All rights reserved. 29a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// Redistribution and use in source and binary forms, with or without 39a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// modification, are permitted provided that the following conditions are 49a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// met: 59a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// 69a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// * Redistributions of source code must retain the above copyright 79a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// notice, this list of conditions and the following disclaimer. 89a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// * Redistributions in binary form must reproduce the above 99a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// copyright notice, this list of conditions and the following 109a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// disclaimer in the documentation and/or other materials provided 119a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// with the distribution. 129a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// * Neither the name of Google Inc. nor the names of its 139a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// contributors may be used to endorse or promote products derived 149a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// from this software without specific prior written permission. 159a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// 169a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 179a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 189a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 199a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 209a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 219a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 229a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 239a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 249a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 259a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 269a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 279a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 289a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com/** 299a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com * @fileoverview Test reverse on small * and large arrays. 309a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com */ 319a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 329a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comvar VERYLARGE = 4000000000; 339a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 349a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// Nicer for firefox 1.5. Unless you uncomment the following line, 359a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// smjs will appear to hang on this file. 369a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com//var VERYLARGE = 40000; 379a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 389a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 399a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// Simple test of reverse on sparse array. 409a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comvar a = []; 419a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma.length = 2000; 429a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma[15] = 'a'; 439a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma[30] = 'b'; 449a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comArray.prototype[30] = 'B'; // Should be hidden by a[30]. 459a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma[40] = 'c'; 469a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma[50] = 'deleted'; 479a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comdelete a[50]; // Should leave no trace once deleted. 489a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma[1959] = 'd'; // Swapped with a[40] when reversing. 499a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma[1999] = 'e'; 509a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comassertEquals("abcde", a.join('')); 519a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.coma.reverse(); 529a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comdelete Array.prototype[30]; 539a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comassertEquals("edcba", a.join('')); 549a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 559a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 569a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 579a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comvar seed = 43; 589a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 599a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// CONG pseudo random number generator. Used for fuzzing the sparse array 609a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// reverse code. 619a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comfunction DoOrDont() { 629a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com seed = (69069 * seed + 1234567) % 0x100000000; 639a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com return (seed & 0x100000) != 0; 649a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com} 659a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 669a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comvar sizes = [140, 40000, VERYLARGE]; 679a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comvar poses = [0, 10, 50, 69]; 689a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 699a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 709a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com// Fuzzing test of reverse on sparse array. 719a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.comfor (var iterations = 0; iterations < 20; iterations++) { 729a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com for (var size_pos = 0; size_pos < sizes.length; size_pos++) { 739a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var size = sizes[size_pos]; 749a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 759a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var to_delete = []; 769a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 777be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org var a; 787be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // Make sure we test both array-backed and hash-table backed 797be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // arrays. 807be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org if (size < 1000) { 817be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org a = new Array(size); 827be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } else { 837be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org a = new Array(); 847be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org a.length = size; 857be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } 869a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 879a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var expected = ''; 889a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var expected_reversed = ''; 899a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 909a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com for (var pos_pos = 0; pos_pos < poses.length; pos_pos++) { 919a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var pos = poses[pos_pos]; 929a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var letter = String.fromCharCode(97 + pos_pos); 939a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com if (DoOrDont()) { 949a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com a[pos] = letter; 959a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected += letter; 969a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected_reversed = letter + expected_reversed; 979a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } else if (DoOrDont()) { 989a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com Array.prototype[pos] = letter; 999a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected += letter; 1009a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected_reversed = letter + expected_reversed; 1019a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com to_delete.push(pos); 1029a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } 1039a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } 1049a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var expected2 = ''; 1059a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var expected_reversed2 = ''; 1069a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com for (var pos_pos = poses.length - 1; pos_pos >= 0; pos_pos--) { 1079a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var letter = String.fromCharCode(110 + pos_pos); 1089a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var pos = size - poses[pos_pos] - 1; 1099a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com if (DoOrDont()) { 1109a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com a[pos] = letter; 1119a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected2 += letter; 1129a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected_reversed2 = letter + expected_reversed2; 1139a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } else if (DoOrDont()) { 1149a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com Array.prototype[pos] = letter; 1159a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected2 += letter; 1169a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com expected_reversed2 = letter + expected_reversed2; 1179a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com to_delete.push(pos); 1189a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } 1199a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } 1209a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 1219a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com assertEquals(expected + expected2, a.join(''), 'join' + size); 1229a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com a.reverse(); 1239a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 1249a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com while (to_delete.length != 0) { 1259a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com var pos = to_delete.pop(); 1269a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com delete(Array.prototype[pos]); 1279a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } 1289a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com 1299a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com assertEquals(expected_reversed2 + expected_reversed, a.join(''), 'reverse then join' + size); 1309a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com } 1319a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com} 132