1// Copyright 2008 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/**
29 * @fileoverview Test reverse on small * and large arrays.
30 */
31
32var VERYLARGE = 4000000000;
33
34// Nicer for firefox 1.5.  Unless you uncomment the following line,
35// smjs will appear to hang on this file.
36//var VERYLARGE = 40000;
37
38
39// Simple test of reverse on sparse array.
40var a = [];
41a.length = 2000;
42a[15] = 'a';
43a[30] = 'b';
44Array.prototype[30] = 'B';  // Should be hidden by a[30].
45a[40] = 'c';
46a[50] = 'deleted';
47delete a[50]; // Should leave no trace once deleted.
48a[1959] = 'd'; // Swapped with a[40] when reversing.
49a[1999] = 'e';
50assertEquals("abcde", a.join(''));
51a.reverse();
52delete Array.prototype[30];
53assertEquals("edcba", a.join(''));
54
55
56
57var seed = 43;
58
59// CONG pseudo random number generator.  Used for fuzzing the sparse array
60// reverse code.
61function DoOrDont() {
62  seed = (69069 * seed + 1234567) % 0x100000000;
63  return (seed & 0x100000) != 0;
64}
65
66var sizes = [140, 40000, VERYLARGE];
67var poses = [0, 10, 50, 69];
68
69
70// Fuzzing test of reverse on sparse array.
71for (var iterations = 0; iterations < 20; iterations++) {
72  for (var size_pos = 0; size_pos < sizes.length; size_pos++) {
73    var size = sizes[size_pos];
74
75    var to_delete = [];
76
77    var a;
78    // Make sure we test both array-backed and hash-table backed
79    // arrays.
80    if (size < 1000) {
81      a = new Array(size);
82    } else {
83      a = new Array();
84      a.length = size;
85    }
86
87    var expected = '';
88    var expected_reversed = '';
89
90    for (var pos_pos = 0; pos_pos < poses.length; pos_pos++) {
91      var pos = poses[pos_pos];
92      var letter = String.fromCharCode(97 + pos_pos);
93      if (DoOrDont()) {
94        a[pos] = letter;
95        expected += letter;
96        expected_reversed = letter + expected_reversed;
97      } else if (DoOrDont()) {
98        Array.prototype[pos] = letter;
99        expected += letter;
100        expected_reversed = letter + expected_reversed;
101        to_delete.push(pos);
102      }
103    }
104    var expected2 = '';
105    var expected_reversed2 = '';
106    for (var pos_pos = poses.length - 1; pos_pos >= 0; pos_pos--) {
107      var letter = String.fromCharCode(110 + pos_pos);
108      var pos = size - poses[pos_pos] - 1;
109      if (DoOrDont()) {
110        a[pos] = letter;
111        expected2 += letter;
112        expected_reversed2 = letter + expected_reversed2;
113      } else if (DoOrDont()) {
114        Array.prototype[pos] = letter;
115        expected2 += letter;
116        expected_reversed2 = letter + expected_reversed2;
117        to_delete.push(pos);
118      }
119    }
120
121    assertEquals(expected + expected2, a.join(''), 'join' + size);
122    a.reverse();
123
124    while (to_delete.length != 0) {
125      var pos = to_delete.pop();
126      delete(Array.prototype[pos]);
127    }
128
129    assertEquals(expected_reversed2 + expected_reversed, a.join(''), 'reverse then join' + size);
130  }
131}
132