Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1 | // Copyright 2012 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. |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 27 | |
| 28 | // Check that we can traverse very deep stacks of ConsStrings using |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 29 | // StringCharacterStram. Check that Get(int) works on very deep stacks |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 30 | // of ConsStrings. These operations may not be very fast, but they |
| 31 | // should be possible without getting errors due to too deep recursion. |
| 32 | |
| 33 | #include <stdlib.h> |
| 34 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 35 | #include "src/v8.h" |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 36 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 37 | #include "src/api.h" |
| 38 | #include "src/factory.h" |
| 39 | #include "src/objects.h" |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 40 | #include "src/unicode-decoder.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 41 | #include "test/cctest/cctest.h" |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 42 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 43 | // Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry |
| 44 | class MyRandomNumberGenerator { |
| 45 | public: |
| 46 | MyRandomNumberGenerator() { |
| 47 | init(); |
| 48 | } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 49 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 50 | void init(uint32_t seed = 0x5688c73e) { |
| 51 | static const uint32_t phi = 0x9e3779b9; |
| 52 | c = 362436; |
| 53 | i = kQSize-1; |
| 54 | Q[0] = seed; |
| 55 | Q[1] = seed + phi; |
| 56 | Q[2] = seed + phi + phi; |
| 57 | for (unsigned j = 3; j < kQSize; j++) { |
| 58 | Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j; |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | uint32_t next() { |
| 63 | uint64_t a = 18782; |
| 64 | uint32_t r = 0xfffffffe; |
| 65 | i = (i + 1) & (kQSize-1); |
| 66 | uint64_t t = a * Q[i] + c; |
| 67 | c = (t >> 32); |
| 68 | uint32_t x = static_cast<uint32_t>(t + c); |
| 69 | if (x < c) { |
| 70 | x++; |
| 71 | c++; |
| 72 | } |
| 73 | return (Q[i] = r - x); |
| 74 | } |
| 75 | |
| 76 | uint32_t next(int max) { |
| 77 | return next() % max; |
| 78 | } |
| 79 | |
| 80 | bool next(double threshold) { |
| 81 | DCHECK(threshold >= 0.0 && threshold <= 1.0); |
| 82 | if (threshold == 1.0) return true; |
| 83 | if (threshold == 0.0) return false; |
| 84 | uint32_t value = next() % 100000; |
| 85 | return threshold > static_cast<double>(value)/100000.0; |
| 86 | } |
| 87 | |
| 88 | private: |
| 89 | static const uint32_t kQSize = 4096; |
| 90 | uint32_t Q[kQSize]; |
| 91 | uint32_t c; |
| 92 | uint32_t i; |
| 93 | }; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 94 | |
| 95 | |
| 96 | using namespace v8::internal; |
| 97 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 98 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 99 | static const int DEEP_DEPTH = 8 * 1024; |
| 100 | static const int SUPER_DEEP_DEPTH = 80 * 1024; |
| 101 | |
| 102 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 103 | class Resource: public v8::String::ExternalStringResource { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 104 | public: |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 105 | Resource(const uc16* data, size_t length): data_(data), length_(length) {} |
| 106 | ~Resource() { i::DeleteArray(data_); } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 107 | virtual const uint16_t* data() const { return data_; } |
| 108 | virtual size_t length() const { return length_; } |
| 109 | |
| 110 | private: |
| 111 | const uc16* data_; |
| 112 | size_t length_; |
| 113 | }; |
| 114 | |
| 115 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 116 | class OneByteResource : public v8::String::ExternalOneByteStringResource { |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 117 | public: |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 118 | OneByteResource(const char* data, size_t length) |
| 119 | : data_(data), length_(length) {} |
| 120 | ~OneByteResource() { i::DeleteArray(data_); } |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 121 | virtual const char* data() const { return data_; } |
| 122 | virtual size_t length() const { return length_; } |
| 123 | |
| 124 | private: |
| 125 | const char* data_; |
| 126 | size_t length_; |
| 127 | }; |
| 128 | |
| 129 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 130 | static void InitializeBuildingBlocks(Handle<String>* building_blocks, |
| 131 | int bb_length, |
| 132 | bool long_blocks, |
| 133 | MyRandomNumberGenerator* rng) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 134 | // A list of pointers that we don't have any interest in cleaning up. |
| 135 | // If they are reachable from a root then leak detection won't complain. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 136 | Isolate* isolate = CcTest::i_isolate(); |
| 137 | Factory* factory = isolate->factory(); |
| 138 | for (int i = 0; i < bb_length; i++) { |
| 139 | int len = rng->next(16); |
| 140 | int slice_head_chars = 0; |
| 141 | int slice_tail_chars = 0; |
| 142 | int slice_depth = 0; |
| 143 | for (int j = 0; j < 3; j++) { |
| 144 | if (rng->next(0.35)) slice_depth++; |
| 145 | } |
| 146 | // Must truncate something for a slice string. Loop until |
| 147 | // at least one end will be sliced. |
| 148 | while (slice_head_chars == 0 && slice_tail_chars == 0) { |
| 149 | slice_head_chars = rng->next(15); |
| 150 | slice_tail_chars = rng->next(12); |
| 151 | } |
| 152 | if (long_blocks) { |
| 153 | // Generate building blocks which will never be merged |
| 154 | len += ConsString::kMinLength + 1; |
| 155 | } else if (len > 14) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 156 | len += 1234; |
| 157 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 158 | // Don't slice 0 length strings. |
| 159 | if (len == 0) slice_depth = 0; |
| 160 | int slice_length = slice_depth*(slice_head_chars + slice_tail_chars); |
| 161 | len += slice_length; |
| 162 | switch (rng->next(4)) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 163 | case 0: { |
| 164 | uc16 buf[2000]; |
| 165 | for (int j = 0; j < len; j++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 166 | buf[j] = rng->next(0x10000); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 167 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 168 | building_blocks[i] = factory->NewStringFromTwoByte( |
| 169 | Vector<const uc16>(buf, len)).ToHandleChecked(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 170 | for (int j = 0; j < len; j++) { |
| 171 | CHECK_EQ(buf[j], building_blocks[i]->Get(j)); |
| 172 | } |
| 173 | break; |
| 174 | } |
| 175 | case 1: { |
| 176 | char buf[2000]; |
| 177 | for (int j = 0; j < len; j++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 178 | buf[j] = rng->next(0x80); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 179 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 180 | building_blocks[i] = factory->NewStringFromAscii( |
| 181 | Vector<const char>(buf, len)).ToHandleChecked(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 182 | for (int j = 0; j < len; j++) { |
| 183 | CHECK_EQ(buf[j], building_blocks[i]->Get(j)); |
| 184 | } |
| 185 | break; |
| 186 | } |
| 187 | case 2: { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 188 | uc16* buf = NewArray<uc16>(len); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 189 | for (int j = 0; j < len; j++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 190 | buf[j] = rng->next(0x10000); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 191 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 192 | Resource* resource = new Resource(buf, len); |
| 193 | building_blocks[i] = |
| 194 | v8::Utils::OpenHandle( |
| 195 | *v8::String::NewExternal(CcTest::isolate(), resource)); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 196 | for (int j = 0; j < len; j++) { |
| 197 | CHECK_EQ(buf[j], building_blocks[i]->Get(j)); |
| 198 | } |
| 199 | break; |
| 200 | } |
| 201 | case 3: { |
| 202 | char* buf = NewArray<char>(len); |
| 203 | for (int j = 0; j < len; j++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 204 | buf[j] = rng->next(0x80); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 205 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 206 | OneByteResource* resource = new OneByteResource(buf, len); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 207 | building_blocks[i] = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 208 | v8::Utils::OpenHandle( |
| 209 | *v8::String::NewExternal(CcTest::isolate(), resource)); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 210 | for (int j = 0; j < len; j++) { |
| 211 | CHECK_EQ(buf[j], building_blocks[i]->Get(j)); |
| 212 | } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 213 | break; |
| 214 | } |
| 215 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 216 | for (int j = slice_depth; j > 0; j--) { |
| 217 | building_blocks[i] = factory->NewSubString( |
| 218 | building_blocks[i], |
| 219 | slice_head_chars, |
| 220 | building_blocks[i]->length() - slice_tail_chars); |
| 221 | } |
| 222 | CHECK(len == building_blocks[i]->length() + slice_length); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 223 | } |
| 224 | } |
| 225 | |
| 226 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 227 | class ConsStringStats { |
| 228 | public: |
| 229 | ConsStringStats() { |
| 230 | Reset(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 231 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 232 | void Reset(); |
| 233 | void VerifyEqual(const ConsStringStats& that) const; |
| 234 | int leaves_; |
| 235 | int empty_leaves_; |
| 236 | int chars_; |
| 237 | int left_traversals_; |
| 238 | int right_traversals_; |
| 239 | private: |
| 240 | DISALLOW_COPY_AND_ASSIGN(ConsStringStats); |
| 241 | }; |
| 242 | |
| 243 | |
| 244 | void ConsStringStats::Reset() { |
| 245 | leaves_ = 0; |
| 246 | empty_leaves_ = 0; |
| 247 | chars_ = 0; |
| 248 | left_traversals_ = 0; |
| 249 | right_traversals_ = 0; |
| 250 | } |
| 251 | |
| 252 | |
| 253 | void ConsStringStats::VerifyEqual(const ConsStringStats& that) const { |
| 254 | CHECK_EQ(this->leaves_, that.leaves_); |
| 255 | CHECK_EQ(this->empty_leaves_, that.empty_leaves_); |
| 256 | CHECK_EQ(this->chars_, that.chars_); |
| 257 | CHECK_EQ(this->left_traversals_, that.left_traversals_); |
| 258 | CHECK_EQ(this->right_traversals_, that.right_traversals_); |
| 259 | } |
| 260 | |
| 261 | |
| 262 | class ConsStringGenerationData { |
| 263 | public: |
| 264 | static const int kNumberOfBuildingBlocks = 256; |
| 265 | explicit ConsStringGenerationData(bool long_blocks); |
| 266 | void Reset(); |
| 267 | inline Handle<String> block(int offset); |
| 268 | inline Handle<String> block(uint32_t offset); |
| 269 | // Input variables. |
| 270 | double early_termination_threshold_; |
| 271 | double leftness_; |
| 272 | double rightness_; |
| 273 | double empty_leaf_threshold_; |
| 274 | int max_leaves_; |
| 275 | // Cached data. |
| 276 | Handle<String> building_blocks_[kNumberOfBuildingBlocks]; |
| 277 | String* empty_string_; |
| 278 | MyRandomNumberGenerator rng_; |
| 279 | // Stats. |
| 280 | ConsStringStats stats_; |
| 281 | int early_terminations_; |
| 282 | private: |
| 283 | DISALLOW_COPY_AND_ASSIGN(ConsStringGenerationData); |
| 284 | }; |
| 285 | |
| 286 | |
| 287 | ConsStringGenerationData::ConsStringGenerationData(bool long_blocks) { |
| 288 | rng_.init(); |
| 289 | InitializeBuildingBlocks( |
| 290 | building_blocks_, kNumberOfBuildingBlocks, long_blocks, &rng_); |
| 291 | empty_string_ = CcTest::heap()->empty_string(); |
| 292 | Reset(); |
| 293 | } |
| 294 | |
| 295 | |
| 296 | Handle<String> ConsStringGenerationData::block(uint32_t offset) { |
| 297 | return building_blocks_[offset % kNumberOfBuildingBlocks ]; |
| 298 | } |
| 299 | |
| 300 | |
| 301 | Handle<String> ConsStringGenerationData::block(int offset) { |
| 302 | CHECK_GE(offset, 0); |
| 303 | return building_blocks_[offset % kNumberOfBuildingBlocks]; |
| 304 | } |
| 305 | |
| 306 | |
| 307 | void ConsStringGenerationData::Reset() { |
| 308 | early_termination_threshold_ = 0.01; |
| 309 | leftness_ = 0.75; |
| 310 | rightness_ = 0.75; |
| 311 | empty_leaf_threshold_ = 0.02; |
| 312 | max_leaves_ = 1000; |
| 313 | stats_.Reset(); |
| 314 | early_terminations_ = 0; |
| 315 | rng_.init(); |
| 316 | } |
| 317 | |
| 318 | |
| 319 | void AccumulateStats(ConsString* cons_string, ConsStringStats* stats) { |
| 320 | int left_length = cons_string->first()->length(); |
| 321 | int right_length = cons_string->second()->length(); |
| 322 | CHECK(cons_string->length() == left_length + right_length); |
| 323 | // Check left side. |
| 324 | bool left_is_cons = cons_string->first()->IsConsString(); |
| 325 | if (left_is_cons) { |
| 326 | stats->left_traversals_++; |
| 327 | AccumulateStats(ConsString::cast(cons_string->first()), stats); |
| 328 | } else { |
| 329 | CHECK_NE(left_length, 0); |
| 330 | stats->leaves_++; |
| 331 | stats->chars_ += left_length; |
| 332 | } |
| 333 | // Check right side. |
| 334 | if (cons_string->second()->IsConsString()) { |
| 335 | stats->right_traversals_++; |
| 336 | AccumulateStats(ConsString::cast(cons_string->second()), stats); |
| 337 | } else { |
| 338 | if (right_length == 0) { |
| 339 | stats->empty_leaves_++; |
| 340 | CHECK(!left_is_cons); |
| 341 | } |
| 342 | stats->leaves_++; |
| 343 | stats->chars_ += right_length; |
| 344 | } |
| 345 | } |
| 346 | |
| 347 | |
| 348 | void AccumulateStats(Handle<String> cons_string, ConsStringStats* stats) { |
| 349 | DisallowHeapAllocation no_allocation; |
| 350 | if (cons_string->IsConsString()) { |
| 351 | return AccumulateStats(ConsString::cast(*cons_string), stats); |
| 352 | } |
| 353 | // This string got flattened by gc. |
| 354 | stats->chars_ += cons_string->length(); |
| 355 | } |
| 356 | |
| 357 | |
| 358 | void AccumulateStatsWithOperator( |
| 359 | ConsString* cons_string, ConsStringStats* stats) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 360 | ConsStringIterator iter(cons_string); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 361 | String* string; |
| 362 | int offset; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 363 | while (NULL != (string = iter.Next(&offset))) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 364 | // Accumulate stats. |
| 365 | CHECK_EQ(0, offset); |
| 366 | stats->leaves_++; |
| 367 | stats->chars_ += string->length(); |
| 368 | } |
| 369 | } |
| 370 | |
| 371 | |
| 372 | void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) { |
| 373 | // Verify basic data. |
| 374 | CHECK(root->IsConsString()); |
| 375 | CHECK_EQ(root->length(), data->stats_.chars_); |
| 376 | // Recursive verify. |
| 377 | ConsStringStats stats; |
| 378 | AccumulateStats(ConsString::cast(*root), &stats); |
| 379 | stats.VerifyEqual(data->stats_); |
| 380 | // Iteratively verify. |
| 381 | stats.Reset(); |
| 382 | AccumulateStatsWithOperator(ConsString::cast(*root), &stats); |
| 383 | // Don't see these. Must copy over. |
| 384 | stats.empty_leaves_ = data->stats_.empty_leaves_; |
| 385 | stats.left_traversals_ = data->stats_.left_traversals_; |
| 386 | stats.right_traversals_ = data->stats_.right_traversals_; |
| 387 | // Adjust total leaves to compensate. |
| 388 | stats.leaves_ += stats.empty_leaves_; |
| 389 | stats.VerifyEqual(data->stats_); |
| 390 | } |
| 391 | |
| 392 | |
| 393 | static Handle<String> ConstructRandomString(ConsStringGenerationData* data, |
| 394 | unsigned max_recursion) { |
| 395 | Factory* factory = CcTest::i_isolate()->factory(); |
| 396 | // Compute termination characteristics. |
| 397 | bool terminate = false; |
| 398 | bool flat = data->rng_.next(data->empty_leaf_threshold_); |
| 399 | bool terminate_early = data->rng_.next(data->early_termination_threshold_); |
| 400 | if (terminate_early) data->early_terminations_++; |
| 401 | // The obvious condition. |
| 402 | terminate |= max_recursion == 0; |
| 403 | // Flat cons string terminate by definition. |
| 404 | terminate |= flat; |
| 405 | // Cap for max leaves. |
| 406 | terminate |= data->stats_.leaves_ >= data->max_leaves_; |
| 407 | // Roll the dice. |
| 408 | terminate |= terminate_early; |
| 409 | // Compute termination characteristics for each side. |
| 410 | bool terminate_left = terminate || !data->rng_.next(data->leftness_); |
| 411 | bool terminate_right = terminate || !data->rng_.next(data->rightness_); |
| 412 | // Generate left string. |
| 413 | Handle<String> left; |
| 414 | if (terminate_left) { |
| 415 | left = data->block(data->rng_.next()); |
| 416 | data->stats_.leaves_++; |
| 417 | data->stats_.chars_ += left->length(); |
| 418 | } else { |
| 419 | data->stats_.left_traversals_++; |
| 420 | } |
| 421 | // Generate right string. |
| 422 | Handle<String> right; |
| 423 | if (terminate_right) { |
| 424 | right = data->block(data->rng_.next()); |
| 425 | data->stats_.leaves_++; |
| 426 | data->stats_.chars_ += right->length(); |
| 427 | } else { |
| 428 | data->stats_.right_traversals_++; |
| 429 | } |
| 430 | // Generate the necessary sub-nodes recursively. |
| 431 | if (!terminate_right) { |
| 432 | // Need to balance generation fairly. |
| 433 | if (!terminate_left && data->rng_.next(0.5)) { |
| 434 | left = ConstructRandomString(data, max_recursion - 1); |
| 435 | } |
| 436 | right = ConstructRandomString(data, max_recursion - 1); |
| 437 | } |
| 438 | if (!terminate_left && left.is_null()) { |
| 439 | left = ConstructRandomString(data, max_recursion - 1); |
| 440 | } |
| 441 | // Build the cons string. |
| 442 | Handle<String> root = factory->NewConsString(left, right).ToHandleChecked(); |
| 443 | CHECK(root->IsConsString() && !root->IsFlat()); |
| 444 | // Special work needed for flat string. |
| 445 | if (flat) { |
| 446 | data->stats_.empty_leaves_++; |
| 447 | String::Flatten(root); |
| 448 | CHECK(root->IsConsString() && root->IsFlat()); |
| 449 | } |
| 450 | return root; |
| 451 | } |
| 452 | |
| 453 | |
| 454 | static Handle<String> ConstructLeft( |
| 455 | ConsStringGenerationData* data, |
| 456 | int depth) { |
| 457 | Factory* factory = CcTest::i_isolate()->factory(); |
| 458 | Handle<String> answer = factory->NewStringFromStaticChars(""); |
| 459 | data->stats_.leaves_++; |
| 460 | for (int i = 0; i < depth; i++) { |
| 461 | Handle<String> block = data->block(i); |
| 462 | Handle<String> next = |
| 463 | factory->NewConsString(answer, block).ToHandleChecked(); |
| 464 | if (next->IsConsString()) data->stats_.leaves_++; |
| 465 | data->stats_.chars_ += block->length(); |
| 466 | answer = next; |
| 467 | } |
| 468 | data->stats_.left_traversals_ = data->stats_.leaves_ - 2; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 469 | return answer; |
| 470 | } |
| 471 | |
| 472 | |
| 473 | static Handle<String> ConstructRight( |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 474 | ConsStringGenerationData* data, |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 475 | int depth) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 476 | Factory* factory = CcTest::i_isolate()->factory(); |
| 477 | Handle<String> answer = factory->NewStringFromStaticChars(""); |
| 478 | data->stats_.leaves_++; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 479 | for (int i = depth - 1; i >= 0; i--) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 480 | Handle<String> block = data->block(i); |
| 481 | Handle<String> next = |
| 482 | factory->NewConsString(block, answer).ToHandleChecked(); |
| 483 | if (next->IsConsString()) data->stats_.leaves_++; |
| 484 | data->stats_.chars_ += block->length(); |
| 485 | answer = next; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 486 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 487 | data->stats_.right_traversals_ = data->stats_.leaves_ - 2; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 488 | return answer; |
| 489 | } |
| 490 | |
| 491 | |
| 492 | static Handle<String> ConstructBalancedHelper( |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 493 | ConsStringGenerationData* data, |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 494 | int from, |
| 495 | int to) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 496 | Factory* factory = CcTest::i_isolate()->factory(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 497 | CHECK(to > from); |
| 498 | if (to - from == 1) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 499 | data->stats_.chars_ += data->block(from)->length(); |
| 500 | return data->block(from); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 501 | } |
| 502 | if (to - from == 2) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 503 | data->stats_.chars_ += data->block(from)->length(); |
| 504 | data->stats_.chars_ += data->block(from+1)->length(); |
| 505 | return factory->NewConsString(data->block(from), data->block(from+1)) |
| 506 | .ToHandleChecked(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 507 | } |
| 508 | Handle<String> part1 = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 509 | ConstructBalancedHelper(data, from, from + ((to - from) / 2)); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 510 | Handle<String> part2 = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 511 | ConstructBalancedHelper(data, from + ((to - from) / 2), to); |
| 512 | if (part1->IsConsString()) data->stats_.left_traversals_++; |
| 513 | if (part2->IsConsString()) data->stats_.right_traversals_++; |
| 514 | return factory->NewConsString(part1, part2).ToHandleChecked(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 515 | } |
| 516 | |
| 517 | |
| 518 | static Handle<String> ConstructBalanced( |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 519 | ConsStringGenerationData* data, int depth = DEEP_DEPTH) { |
| 520 | Handle<String> string = ConstructBalancedHelper(data, 0, depth); |
| 521 | data->stats_.leaves_ = |
| 522 | data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2; |
| 523 | return string; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 524 | } |
| 525 | |
| 526 | |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 527 | static void Traverse(Handle<String> s1, Handle<String> s2) { |
| 528 | int i = 0; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 529 | StringCharacterStream character_stream_1(*s1); |
| 530 | StringCharacterStream character_stream_2(*s2); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 531 | while (character_stream_1.HasMore()) { |
| 532 | CHECK(character_stream_2.HasMore()); |
| 533 | uint16_t c = character_stream_1.GetNext(); |
| 534 | CHECK_EQ(c, character_stream_2.GetNext()); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 535 | i++; |
| 536 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 537 | CHECK(!character_stream_1.HasMore()); |
| 538 | CHECK(!character_stream_2.HasMore()); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 539 | CHECK_EQ(s1->length(), i); |
| 540 | CHECK_EQ(s2->length(), i); |
| 541 | } |
| 542 | |
| 543 | |
| 544 | static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) { |
| 545 | int i = 0; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 546 | StringCharacterStream character_stream_1(*s1); |
| 547 | StringCharacterStream character_stream_2(*s2); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 548 | while (character_stream_1.HasMore() && i < chars) { |
| 549 | CHECK(character_stream_2.HasMore()); |
| 550 | uint16_t c = character_stream_1.GetNext(); |
| 551 | CHECK_EQ(c, character_stream_2.GetNext()); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 552 | i++; |
| 553 | } |
| 554 | s1->Get(s1->length() - 1); |
| 555 | s2->Get(s2->length() - 1); |
| 556 | } |
| 557 | |
| 558 | |
| 559 | TEST(Traverse) { |
| 560 | printf("TestTraverse\n"); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 561 | CcTest::InitializeVM(); |
| 562 | v8::HandleScope scope(CcTest::isolate()); |
| 563 | ConsStringGenerationData data(false); |
| 564 | Handle<String> flat = ConstructBalanced(&data); |
| 565 | String::Flatten(flat); |
| 566 | Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH); |
| 567 | Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH); |
| 568 | Handle<String> symmetric = ConstructBalanced(&data); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 569 | printf("1\n"); |
| 570 | Traverse(flat, symmetric); |
| 571 | printf("2\n"); |
| 572 | Traverse(flat, left_asymmetric); |
| 573 | printf("3\n"); |
| 574 | Traverse(flat, right_asymmetric); |
| 575 | printf("4\n"); |
| 576 | Handle<String> left_deep_asymmetric = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 577 | ConstructLeft(&data, SUPER_DEEP_DEPTH); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 578 | Handle<String> right_deep_asymmetric = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 579 | ConstructRight(&data, SUPER_DEEP_DEPTH); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 580 | printf("5\n"); |
| 581 | TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050); |
| 582 | printf("6\n"); |
| 583 | TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536); |
| 584 | printf("7\n"); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 585 | String::Flatten(left_asymmetric); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 586 | printf("10\n"); |
| 587 | Traverse(flat, left_asymmetric); |
| 588 | printf("11\n"); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 589 | String::Flatten(right_asymmetric); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 590 | printf("12\n"); |
| 591 | Traverse(flat, right_asymmetric); |
| 592 | printf("14\n"); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 593 | String::Flatten(symmetric); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 594 | printf("15\n"); |
| 595 | Traverse(flat, symmetric); |
| 596 | printf("16\n"); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 597 | String::Flatten(left_deep_asymmetric); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 598 | printf("18\n"); |
| 599 | } |
| 600 | |
| 601 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 602 | static void VerifyCharacterStream( |
| 603 | String* flat_string, String* cons_string) { |
| 604 | // Do not want to test ConString traversal on flat string. |
| 605 | CHECK(flat_string->IsFlat() && !flat_string->IsConsString()); |
| 606 | CHECK(cons_string->IsConsString()); |
| 607 | // TODO(dcarney) Test stream reset as well. |
| 608 | int length = flat_string->length(); |
| 609 | // Iterate start search in multiple places in the string. |
| 610 | int outer_iterations = length > 20 ? 20 : length; |
| 611 | for (int j = 0; j <= outer_iterations; j++) { |
| 612 | int offset = length * j / outer_iterations; |
| 613 | if (offset < 0) offset = 0; |
| 614 | // Want to test the offset == length case. |
| 615 | if (offset > length) offset = length; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 616 | StringCharacterStream flat_stream(flat_string, offset); |
| 617 | StringCharacterStream cons_stream(cons_string, offset); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 618 | for (int i = offset; i < length; i++) { |
| 619 | uint16_t c = flat_string->Get(i); |
| 620 | CHECK(flat_stream.HasMore()); |
| 621 | CHECK(cons_stream.HasMore()); |
| 622 | CHECK_EQ(c, flat_stream.GetNext()); |
| 623 | CHECK_EQ(c, cons_stream.GetNext()); |
| 624 | } |
| 625 | CHECK(!flat_stream.HasMore()); |
| 626 | CHECK(!cons_stream.HasMore()); |
| 627 | } |
| 628 | } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 629 | |
| 630 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 631 | static inline void PrintStats(const ConsStringGenerationData& data) { |
| 632 | #ifdef DEBUG |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 633 | printf("%s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u]\n", |
| 634 | "leaves", data.stats_.leaves_, "empty", data.stats_.empty_leaves_, |
| 635 | "chars", data.stats_.chars_, "lefts", data.stats_.left_traversals_, |
| 636 | "rights", data.stats_.right_traversals_, "early_terminations", |
| 637 | data.early_terminations_); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 638 | #endif |
| 639 | } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 640 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 641 | |
| 642 | template<typename BuildString> |
| 643 | void TestStringCharacterStream(BuildString build, int test_cases) { |
| 644 | CcTest::InitializeVM(); |
| 645 | Isolate* isolate = CcTest::i_isolate(); |
| 646 | HandleScope outer_scope(isolate); |
| 647 | ConsStringGenerationData data(true); |
| 648 | for (int i = 0; i < test_cases; i++) { |
| 649 | printf("%d\n", i); |
| 650 | HandleScope inner_scope(isolate); |
| 651 | AlwaysAllocateScope always_allocate(isolate); |
| 652 | // Build flat version of cons string. |
| 653 | Handle<String> flat_string = build(i, &data); |
| 654 | ConsStringStats flat_string_stats; |
| 655 | AccumulateStats(flat_string, &flat_string_stats); |
| 656 | // Flatten string. |
| 657 | String::Flatten(flat_string); |
| 658 | // Build unflattened version of cons string to test. |
| 659 | Handle<String> cons_string = build(i, &data); |
| 660 | ConsStringStats cons_string_stats; |
| 661 | AccumulateStats(cons_string, &cons_string_stats); |
| 662 | DisallowHeapAllocation no_allocation; |
| 663 | PrintStats(data); |
| 664 | // Full verify of cons string. |
| 665 | cons_string_stats.VerifyEqual(flat_string_stats); |
| 666 | cons_string_stats.VerifyEqual(data.stats_); |
| 667 | VerifyConsString(cons_string, &data); |
| 668 | String* flat_string_ptr = |
| 669 | flat_string->IsConsString() ? |
| 670 | ConsString::cast(*flat_string)->first() : |
| 671 | *flat_string; |
| 672 | VerifyCharacterStream(flat_string_ptr, *cons_string); |
| 673 | } |
| 674 | } |
| 675 | |
| 676 | |
| 677 | static const int kCharacterStreamNonRandomCases = 8; |
| 678 | |
| 679 | |
| 680 | static Handle<String> BuildEdgeCaseConsString( |
| 681 | int test_case, ConsStringGenerationData* data) { |
| 682 | Factory* factory = CcTest::i_isolate()->factory(); |
| 683 | data->Reset(); |
| 684 | switch (test_case) { |
| 685 | case 0: |
| 686 | return ConstructBalanced(data, 71); |
| 687 | case 1: |
| 688 | return ConstructLeft(data, 71); |
| 689 | case 2: |
| 690 | return ConstructRight(data, 71); |
| 691 | case 3: |
| 692 | return ConstructLeft(data, 10); |
| 693 | case 4: |
| 694 | return ConstructRight(data, 10); |
| 695 | case 5: |
| 696 | // 2 element balanced tree. |
| 697 | data->stats_.chars_ += data->block(0)->length(); |
| 698 | data->stats_.chars_ += data->block(1)->length(); |
| 699 | data->stats_.leaves_ += 2; |
| 700 | return factory->NewConsString(data->block(0), data->block(1)) |
| 701 | .ToHandleChecked(); |
| 702 | case 6: |
| 703 | // Simple flattened tree. |
| 704 | data->stats_.chars_ += data->block(0)->length(); |
| 705 | data->stats_.chars_ += data->block(1)->length(); |
| 706 | data->stats_.leaves_ += 2; |
| 707 | data->stats_.empty_leaves_ += 1; |
| 708 | { |
| 709 | Handle<String> string = |
| 710 | factory->NewConsString(data->block(0), data->block(1)) |
| 711 | .ToHandleChecked(); |
| 712 | String::Flatten(string); |
| 713 | return string; |
| 714 | } |
| 715 | case 7: |
| 716 | // Left node flattened. |
| 717 | data->stats_.chars_ += data->block(0)->length(); |
| 718 | data->stats_.chars_ += data->block(1)->length(); |
| 719 | data->stats_.chars_ += data->block(2)->length(); |
| 720 | data->stats_.leaves_ += 3; |
| 721 | data->stats_.empty_leaves_ += 1; |
| 722 | data->stats_.left_traversals_ += 1; |
| 723 | { |
| 724 | Handle<String> left = |
| 725 | factory->NewConsString(data->block(0), data->block(1)) |
| 726 | .ToHandleChecked(); |
| 727 | String::Flatten(left); |
| 728 | return factory->NewConsString(left, data->block(2)).ToHandleChecked(); |
| 729 | } |
| 730 | case 8: |
| 731 | // Left node and right node flattened. |
| 732 | data->stats_.chars_ += data->block(0)->length(); |
| 733 | data->stats_.chars_ += data->block(1)->length(); |
| 734 | data->stats_.chars_ += data->block(2)->length(); |
| 735 | data->stats_.chars_ += data->block(3)->length(); |
| 736 | data->stats_.leaves_ += 4; |
| 737 | data->stats_.empty_leaves_ += 2; |
| 738 | data->stats_.left_traversals_ += 1; |
| 739 | data->stats_.right_traversals_ += 1; |
| 740 | { |
| 741 | Handle<String> left = |
| 742 | factory->NewConsString(data->block(0), data->block(1)) |
| 743 | .ToHandleChecked(); |
| 744 | String::Flatten(left); |
| 745 | Handle<String> right = |
| 746 | factory->NewConsString(data->block(2), data->block(2)) |
| 747 | .ToHandleChecked(); |
| 748 | String::Flatten(right); |
| 749 | return factory->NewConsString(left, right).ToHandleChecked(); |
| 750 | } |
| 751 | } |
| 752 | UNREACHABLE(); |
| 753 | return Handle<String>(); |
| 754 | } |
| 755 | |
| 756 | |
| 757 | TEST(StringCharacterStreamEdgeCases) { |
| 758 | printf("TestStringCharacterStreamEdgeCases\n"); |
| 759 | TestStringCharacterStream( |
| 760 | BuildEdgeCaseConsString, kCharacterStreamNonRandomCases); |
| 761 | } |
| 762 | |
| 763 | |
| 764 | static const int kBalances = 3; |
| 765 | static const int kTreeLengths = 4; |
| 766 | static const int kEmptyLeaves = 4; |
| 767 | static const int kUniqueRandomParameters = |
| 768 | kBalances*kTreeLengths*kEmptyLeaves; |
| 769 | |
| 770 | |
| 771 | static void InitializeGenerationData( |
| 772 | int test_case, ConsStringGenerationData* data) { |
| 773 | // Clear the settings and reinit the rng. |
| 774 | data->Reset(); |
| 775 | // Spin up the rng to a known location that is unique per test. |
| 776 | static const int kPerTestJump = 501; |
| 777 | for (int j = 0; j < test_case*kPerTestJump; j++) { |
| 778 | data->rng_.next(); |
| 779 | } |
| 780 | // Choose balanced, left or right heavy trees. |
| 781 | switch (test_case % kBalances) { |
| 782 | case 0: |
| 783 | // Nothing to do. Already balanced. |
| 784 | break; |
| 785 | case 1: |
| 786 | // Left balanced. |
| 787 | data->leftness_ = 0.90; |
| 788 | data->rightness_ = 0.15; |
| 789 | break; |
| 790 | case 2: |
| 791 | // Right balanced. |
| 792 | data->leftness_ = 0.15; |
| 793 | data->rightness_ = 0.90; |
| 794 | break; |
| 795 | default: |
| 796 | UNREACHABLE(); |
| 797 | break; |
| 798 | } |
| 799 | // Must remove the influence of the above decision. |
| 800 | test_case /= kBalances; |
| 801 | // Choose tree length. |
| 802 | switch (test_case % kTreeLengths) { |
| 803 | case 0: |
| 804 | data->max_leaves_ = 16; |
| 805 | data->early_termination_threshold_ = 0.2; |
| 806 | break; |
| 807 | case 1: |
| 808 | data->max_leaves_ = 50; |
| 809 | data->early_termination_threshold_ = 0.05; |
| 810 | break; |
| 811 | case 2: |
| 812 | data->max_leaves_ = 500; |
| 813 | data->early_termination_threshold_ = 0.03; |
| 814 | break; |
| 815 | case 3: |
| 816 | data->max_leaves_ = 5000; |
| 817 | data->early_termination_threshold_ = 0.001; |
| 818 | break; |
| 819 | default: |
| 820 | UNREACHABLE(); |
| 821 | break; |
| 822 | } |
| 823 | // Must remove the influence of the above decision. |
| 824 | test_case /= kTreeLengths; |
| 825 | // Choose how much we allow empty nodes, including not at all. |
| 826 | data->empty_leaf_threshold_ = |
| 827 | 0.03 * static_cast<double>(test_case % kEmptyLeaves); |
| 828 | } |
| 829 | |
| 830 | |
| 831 | static Handle<String> BuildRandomConsString( |
| 832 | int test_case, ConsStringGenerationData* data) { |
| 833 | InitializeGenerationData(test_case, data); |
| 834 | return ConstructRandomString(data, 200); |
| 835 | } |
| 836 | |
| 837 | |
| 838 | TEST(StringCharacterStreamRandom) { |
| 839 | printf("StringCharacterStreamRandom\n"); |
| 840 | TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7); |
| 841 | } |
| 842 | |
| 843 | |
| 844 | static const int kDeepOneByteDepth = 100000; |
| 845 | |
| 846 | |
| 847 | TEST(DeepOneByte) { |
| 848 | CcTest::InitializeVM(); |
| 849 | Factory* factory = CcTest::i_isolate()->factory(); |
| 850 | v8::HandleScope scope(CcTest::isolate()); |
| 851 | |
| 852 | char* foo = NewArray<char>(kDeepOneByteDepth); |
| 853 | for (int i = 0; i < kDeepOneByteDepth; i++) { |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 854 | foo[i] = "foo "[i % 4]; |
| 855 | } |
| 856 | Handle<String> string = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 857 | factory->NewStringFromOneByte(OneByteVector(foo, kDeepOneByteDepth)) |
| 858 | .ToHandleChecked(); |
| 859 | Handle<String> foo_string = factory->NewStringFromStaticChars("foo"); |
| 860 | for (int i = 0; i < kDeepOneByteDepth; i += 10) { |
| 861 | string = factory->NewConsString(string, foo_string).ToHandleChecked(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 862 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 863 | Handle<String> flat_string = |
| 864 | factory->NewConsString(string, foo_string).ToHandleChecked(); |
| 865 | String::Flatten(flat_string); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 866 | |
| 867 | for (int i = 0; i < 500; i++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 868 | TraverseFirst(flat_string, string, kDeepOneByteDepth); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 869 | } |
| 870 | DeleteArray<char>(foo); |
| 871 | } |
| 872 | |
| 873 | |
| 874 | TEST(Utf8Conversion) { |
| 875 | // Smoke test for converting strings to utf-8. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 876 | CcTest::InitializeVM(); |
| 877 | v8::HandleScope handle_scope(CcTest::isolate()); |
| 878 | // A simple one-byte string |
| 879 | const char* one_byte_string = "abcdef12345"; |
| 880 | int len = v8::String::NewFromUtf8(CcTest::isolate(), one_byte_string, |
| 881 | v8::String::kNormalString, |
| 882 | StrLength(one_byte_string))->Utf8Length(); |
| 883 | CHECK_EQ(StrLength(one_byte_string), len); |
| 884 | // A mixed one-byte and two-byte string |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 885 | // U+02E4 -> CB A4 |
| 886 | // U+0064 -> 64 |
| 887 | // U+12E4 -> E1 8B A4 |
| 888 | // U+0030 -> 30 |
| 889 | // U+3045 -> E3 81 85 |
| 890 | const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045}; |
| 891 | // The characters we expect to be output |
| 892 | const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30, |
| 893 | 0xE3, 0x81, 0x85, 0x00}; |
| 894 | // The number of bytes expected to be written for each length |
| 895 | const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11}; |
Steve Block | 6ded16b | 2010-05-10 14:33:55 +0100 | [diff] [blame] | 896 | const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5}; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 897 | v8::Handle<v8::String> mixed = v8::String::NewFromTwoByte( |
| 898 | CcTest::isolate(), mixed_string, v8::String::kNormalString, 5); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 899 | CHECK_EQ(10, mixed->Utf8Length()); |
| 900 | // Try encoding the string with all capacities |
| 901 | char buffer[11]; |
| 902 | const char kNoChar = static_cast<char>(-1); |
| 903 | for (int i = 0; i <= 11; i++) { |
| 904 | // Clear the buffer before reusing it |
| 905 | for (int j = 0; j < 11; j++) |
| 906 | buffer[j] = kNoChar; |
Steve Block | 6ded16b | 2010-05-10 14:33:55 +0100 | [diff] [blame] | 907 | int chars_written; |
| 908 | int written = mixed->WriteUtf8(buffer, i, &chars_written); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 909 | CHECK_EQ(lengths[i], written); |
Steve Block | 6ded16b | 2010-05-10 14:33:55 +0100 | [diff] [blame] | 910 | CHECK_EQ(char_lengths[i], chars_written); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 911 | // Check that the contents are correct |
| 912 | for (int j = 0; j < lengths[i]; j++) |
| 913 | CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j])); |
| 914 | // Check that the rest of the buffer hasn't been touched |
| 915 | for (int j = lengths[i]; j < 11; j++) |
| 916 | CHECK_EQ(kNoChar, buffer[j]); |
| 917 | } |
| 918 | } |
| 919 | |
| 920 | |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 921 | TEST(ExternalShortStringAdd) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 922 | LocalContext context; |
| 923 | v8::HandleScope handle_scope(CcTest::isolate()); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 924 | |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 925 | // Make sure we cover all always-flat lengths and at least one above. |
| 926 | static const int kMaxLength = 20; |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 927 | CHECK_GT(kMaxLength, i::ConsString::kMinLength); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 928 | |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 929 | // Allocate two JavaScript arrays for holding short strings. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 930 | v8::Handle<v8::Array> one_byte_external_strings = |
| 931 | v8::Array::New(CcTest::isolate(), kMaxLength + 1); |
| 932 | v8::Handle<v8::Array> non_one_byte_external_strings = |
| 933 | v8::Array::New(CcTest::isolate(), kMaxLength + 1); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 934 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 935 | // Generate short one-byte and two-byte external strings. |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 936 | for (int i = 0; i <= kMaxLength; i++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 937 | char* one_byte = NewArray<char>(i + 1); |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 938 | for (int j = 0; j < i; j++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 939 | one_byte[j] = 'a'; |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 940 | } |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 941 | // Terminating '\0' is left out on purpose. It is not required for external |
| 942 | // string data. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 943 | OneByteResource* one_byte_resource = new OneByteResource(one_byte, i); |
| 944 | v8::Local<v8::String> one_byte_external_string = |
| 945 | v8::String::NewExternal(CcTest::isolate(), one_byte_resource); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 946 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 947 | one_byte_external_strings->Set(v8::Integer::New(CcTest::isolate(), i), |
| 948 | one_byte_external_string); |
| 949 | uc16* non_one_byte = NewArray<uc16>(i + 1); |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 950 | for (int j = 0; j < i; j++) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 951 | non_one_byte[j] = 0x1234; |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 952 | } |
| 953 | // Terminating '\0' is left out on purpose. It is not required for external |
| 954 | // string data. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 955 | Resource* resource = new Resource(non_one_byte, i); |
| 956 | v8::Local<v8::String> non_one_byte_external_string = |
| 957 | v8::String::NewExternal(CcTest::isolate(), resource); |
| 958 | non_one_byte_external_strings->Set(v8::Integer::New(CcTest::isolate(), i), |
| 959 | non_one_byte_external_string); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 960 | } |
| 961 | |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 962 | // Add the arrays with the short external strings in the global object. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 963 | v8::Handle<v8::Object> global = context->Global(); |
| 964 | global->Set(v8_str("external_one_byte"), one_byte_external_strings); |
| 965 | global->Set(v8_str("external_non_one_byte"), non_one_byte_external_strings); |
| 966 | global->Set(v8_str("max_length"), |
| 967 | v8::Integer::New(CcTest::isolate(), kMaxLength)); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 968 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 969 | // Add short external one-byte and two-byte strings checking the result. |
Steve Block | d0582a6 | 2009-12-15 09:54:21 +0000 | [diff] [blame] | 970 | static const char* source = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 971 | "function test() {" |
| 972 | " var one_byte_chars = 'aaaaaaaaaaaaaaaaaaaa';" |
| 973 | " var non_one_byte_chars = " |
| 974 | "'\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1" |
| 975 | "234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\" |
| 976 | "u1234';" // NOLINT |
| 977 | " if (one_byte_chars.length != max_length) return 1;" |
| 978 | " if (non_one_byte_chars.length != max_length) return 2;" |
| 979 | " var one_byte = Array(max_length + 1);" |
| 980 | " var non_one_byte = Array(max_length + 1);" |
| 981 | " for (var i = 0; i <= max_length; i++) {" |
| 982 | " one_byte[i] = one_byte_chars.substring(0, i);" |
| 983 | " non_one_byte[i] = non_one_byte_chars.substring(0, i);" |
| 984 | " };" |
| 985 | " for (var i = 0; i <= max_length; i++) {" |
| 986 | " if (one_byte[i] != external_one_byte[i]) return 3;" |
| 987 | " if (non_one_byte[i] != external_non_one_byte[i]) return 4;" |
| 988 | " for (var j = 0; j < i; j++) {" |
| 989 | " if (external_one_byte[i] !=" |
| 990 | " (external_one_byte[j] + external_one_byte[i - j])) return " |
| 991 | "5;" |
| 992 | " if (external_non_one_byte[i] !=" |
| 993 | " (external_non_one_byte[j] + external_non_one_byte[i - " |
| 994 | "j])) return 6;" |
| 995 | " if (non_one_byte[i] != (non_one_byte[j] + non_one_byte[i - " |
| 996 | "j])) return 7;" |
| 997 | " if (one_byte[i] != (one_byte[j] + one_byte[i - j])) return 8;" |
| 998 | " if (one_byte[i] != (external_one_byte[j] + one_byte[i - j])) " |
| 999 | "return 9;" |
| 1000 | " if (one_byte[i] != (one_byte[j] + external_one_byte[i - j])) " |
| 1001 | "return 10;" |
| 1002 | " if (non_one_byte[i] !=" |
| 1003 | " (external_non_one_byte[j] + non_one_byte[i - j])) return " |
| 1004 | "11;" |
| 1005 | " if (non_one_byte[i] !=" |
| 1006 | " (non_one_byte[j] + external_non_one_byte[i - j])) return " |
| 1007 | "12;" |
| 1008 | " }" |
| 1009 | " }" |
| 1010 | " return 0;" |
| 1011 | "};" |
| 1012 | "test()"; |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1013 | CHECK_EQ(0, CompileRun(source)->Int32Value()); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 1014 | } |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1015 | |
| 1016 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1017 | TEST(JSONStringifySliceMadeExternal) { |
| 1018 | CcTest::InitializeVM(); |
| 1019 | // Create a sliced string from a one-byte string. The latter is turned |
| 1020 | // into a two-byte external string. Check that JSON.stringify works. |
| 1021 | v8::HandleScope handle_scope(CcTest::isolate()); |
| 1022 | v8::Handle<v8::String> underlying = |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 1023 | CompileRun( |
| 1024 | "var underlying = 'abcdefghijklmnopqrstuvwxyz';" |
| 1025 | "underlying")->ToString(CcTest::isolate()); |
| 1026 | v8::Handle<v8::String> slice = CompileRun( |
| 1027 | "var slice = '';" |
| 1028 | "slice = underlying.slice(1);" |
| 1029 | "slice")->ToString(CcTest::isolate()); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1030 | CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString()); |
| 1031 | CHECK(v8::Utils::OpenHandle(*underlying)->IsSeqOneByteString()); |
| 1032 | |
| 1033 | int length = underlying->Length(); |
| 1034 | uc16* two_byte = NewArray<uc16>(length + 1); |
| 1035 | underlying->Write(two_byte); |
| 1036 | Resource* resource = new Resource(two_byte, length); |
| 1037 | CHECK(underlying->MakeExternal(resource)); |
| 1038 | CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString()); |
| 1039 | CHECK(v8::Utils::OpenHandle(*underlying)->IsExternalTwoByteString()); |
| 1040 | |
| 1041 | CHECK_EQ("\"bcdefghijklmnopqrstuvwxyz\"", |
| 1042 | *v8::String::Utf8Value(CompileRun("JSON.stringify(slice)"))); |
| 1043 | } |
| 1044 | |
| 1045 | |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1046 | TEST(CachedHashOverflow) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1047 | CcTest::InitializeVM(); |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1048 | // We incorrectly allowed strings to be tagged as array indices even if their |
| 1049 | // values didn't fit in the hash field. |
| 1050 | // See http://code.google.com/p/v8/issues/detail?id=728 |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1051 | Isolate* isolate = CcTest::i_isolate(); |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1052 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1053 | v8::HandleScope handle_scope(CcTest::isolate()); |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1054 | // Lines must be executed sequentially. Combining them into one script |
| 1055 | // makes the bug go away. |
| 1056 | const char* lines[] = { |
| 1057 | "var x = [];", |
| 1058 | "x[4] = 42;", |
| 1059 | "var s = \"1073741828\";", |
| 1060 | "x[s];", |
| 1061 | "x[s] = 37;", |
| 1062 | "x[4];", |
| 1063 | "x[s];", |
| 1064 | NULL |
| 1065 | }; |
| 1066 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1067 | Handle<Smi> fortytwo(Smi::FromInt(42), isolate); |
| 1068 | Handle<Smi> thirtyseven(Smi::FromInt(37), isolate); |
| 1069 | Handle<Object> results[] = { isolate->factory()->undefined_value(), |
| 1070 | fortytwo, |
| 1071 | isolate->factory()->undefined_value(), |
| 1072 | isolate->factory()->undefined_value(), |
| 1073 | thirtyseven, |
| 1074 | fortytwo, |
| 1075 | thirtyseven // Bug yielded 42 here. |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1076 | }; |
| 1077 | |
| 1078 | const char* line; |
| 1079 | for (int i = 0; (line = lines[i]); i++) { |
| 1080 | printf("%s\n", line); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1081 | v8::Local<v8::Value> result = v8::Script::Compile( |
| 1082 | v8::String::NewFromUtf8(CcTest::isolate(), line))->Run(); |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1083 | CHECK_EQ(results[i]->IsUndefined(), result->IsUndefined()); |
| 1084 | CHECK_EQ(results[i]->IsNumber(), result->IsNumber()); |
| 1085 | if (result->IsNumber()) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1086 | CHECK_EQ(Object::ToSmi(isolate, results[i]).ToHandleChecked()->value(), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 1087 | result->ToInt32(CcTest::isolate())->Value()); |
Ben Murdoch | 7f4d5bd | 2010-06-15 11:15:29 +0100 | [diff] [blame] | 1088 | } |
| 1089 | } |
| 1090 | } |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1091 | |
| 1092 | |
| 1093 | TEST(SliceFromCons) { |
| 1094 | FLAG_string_slices = true; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1095 | CcTest::InitializeVM(); |
| 1096 | Factory* factory = CcTest::i_isolate()->factory(); |
| 1097 | v8::HandleScope scope(CcTest::isolate()); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1098 | Handle<String> string = |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1099 | factory->NewStringFromStaticChars("parentparentparent"); |
| 1100 | Handle<String> parent = |
| 1101 | factory->NewConsString(string, string).ToHandleChecked(); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1102 | CHECK(parent->IsConsString()); |
| 1103 | CHECK(!parent->IsFlat()); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1104 | Handle<String> slice = factory->NewSubString(parent, 1, 25); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1105 | // After slicing, the original string becomes a flat cons. |
| 1106 | CHECK(parent->IsFlat()); |
| 1107 | CHECK(slice->IsSlicedString()); |
| 1108 | CHECK_EQ(SlicedString::cast(*slice)->parent(), |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1109 | // Parent could have been short-circuited. |
| 1110 | parent->IsConsString() ? ConsString::cast(*parent)->first() |
| 1111 | : *parent); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1112 | CHECK(SlicedString::cast(*slice)->parent()->IsSeqString()); |
| 1113 | CHECK(slice->IsFlat()); |
| 1114 | } |
| 1115 | |
| 1116 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1117 | class OneByteVectorResource : public v8::String::ExternalOneByteStringResource { |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1118 | public: |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1119 | explicit OneByteVectorResource(i::Vector<const char> vector) |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1120 | : data_(vector) {} |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1121 | virtual ~OneByteVectorResource() {} |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1122 | virtual size_t length() const { return data_.length(); } |
| 1123 | virtual const char* data() const { return data_.start(); } |
| 1124 | private: |
| 1125 | i::Vector<const char> data_; |
| 1126 | }; |
| 1127 | |
| 1128 | |
| 1129 | TEST(SliceFromExternal) { |
| 1130 | FLAG_string_slices = true; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1131 | CcTest::InitializeVM(); |
| 1132 | Factory* factory = CcTest::i_isolate()->factory(); |
| 1133 | v8::HandleScope scope(CcTest::isolate()); |
| 1134 | OneByteVectorResource resource( |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1135 | i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26)); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1136 | Handle<String> string = |
| 1137 | factory->NewExternalStringFromOneByte(&resource).ToHandleChecked(); |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1138 | CHECK(string->IsExternalString()); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1139 | Handle<String> slice = factory->NewSubString(string, 1, 25); |
Ben Murdoch | 3ef787d | 2012-04-12 10:51:47 +0100 | [diff] [blame] | 1140 | CHECK(slice->IsSlicedString()); |
| 1141 | CHECK(string->IsExternalString()); |
| 1142 | CHECK_EQ(SlicedString::cast(*slice)->parent(), *string); |
| 1143 | CHECK(SlicedString::cast(*slice)->parent()->IsExternalString()); |
| 1144 | CHECK(slice->IsFlat()); |
| 1145 | } |
| 1146 | |
| 1147 | |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1148 | TEST(TrivialSlice) { |
| 1149 | // This tests whether a slice that contains the entire parent string |
| 1150 | // actually creates a new string (it should not). |
| 1151 | FLAG_string_slices = true; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1152 | CcTest::InitializeVM(); |
| 1153 | Factory* factory = CcTest::i_isolate()->factory(); |
| 1154 | v8::HandleScope scope(CcTest::isolate()); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1155 | v8::Local<v8::Value> result; |
| 1156 | Handle<String> string; |
| 1157 | const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';"; |
| 1158 | const char* check = "str.slice(0,26)"; |
| 1159 | const char* crosscheck = "str.slice(1,25)"; |
| 1160 | |
| 1161 | CompileRun(init); |
| 1162 | |
| 1163 | result = CompileRun(check); |
| 1164 | CHECK(result->IsString()); |
| 1165 | string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1166 | CHECK(!string->IsSlicedString()); |
| 1167 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1168 | string = factory->NewSubString(string, 0, 26); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1169 | CHECK(!string->IsSlicedString()); |
| 1170 | result = CompileRun(crosscheck); |
| 1171 | CHECK(result->IsString()); |
| 1172 | string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1173 | CHECK(string->IsSlicedString()); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1174 | CHECK_EQ("bcdefghijklmnopqrstuvwxy", string->ToCString().get()); |
Ben Murdoch | 69a99ed | 2011-11-30 16:03:39 +0000 | [diff] [blame] | 1175 | } |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 1176 | |
| 1177 | |
| 1178 | TEST(SliceFromSlice) { |
| 1179 | // This tests whether a slice that contains the entire parent string |
| 1180 | // actually creates a new string (it should not). |
| 1181 | FLAG_string_slices = true; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1182 | CcTest::InitializeVM(); |
| 1183 | v8::HandleScope scope(CcTest::isolate()); |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 1184 | v8::Local<v8::Value> result; |
| 1185 | Handle<String> string; |
| 1186 | const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';"; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 1187 | const char* slice = "var slice = ''; slice = str.slice(1,-1); slice"; |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 1188 | const char* slice_from_slice = "slice.slice(1,-1);"; |
| 1189 | |
| 1190 | CompileRun(init); |
| 1191 | result = CompileRun(slice); |
| 1192 | CHECK(result->IsString()); |
| 1193 | string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1194 | CHECK(string->IsSlicedString()); |
| 1195 | CHECK(SlicedString::cast(*string)->parent()->IsSeqString()); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1196 | CHECK_EQ("bcdefghijklmnopqrstuvwxy", string->ToCString().get()); |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 1197 | |
| 1198 | result = CompileRun(slice_from_slice); |
| 1199 | CHECK(result->IsString()); |
| 1200 | string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1201 | CHECK(string->IsSlicedString()); |
| 1202 | CHECK(SlicedString::cast(*string)->parent()->IsSeqString()); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1203 | CHECK_EQ("cdefghijklmnopqrstuvwx", string->ToCString().get()); |
Ben Murdoch | 589d697 | 2011-11-30 16:04:58 +0000 | [diff] [blame] | 1204 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1205 | |
| 1206 | |
| 1207 | UNINITIALIZED_TEST(OneByteArrayJoin) { |
| 1208 | v8::Isolate::CreateParams create_params; |
| 1209 | // Set heap limits. |
| 1210 | create_params.constraints.set_max_semi_space_size(1); |
| 1211 | create_params.constraints.set_max_old_space_size(4); |
| 1212 | v8::Isolate* isolate = v8::Isolate::New(create_params); |
| 1213 | isolate->Enter(); |
| 1214 | |
| 1215 | { |
| 1216 | // String s is made of 2^17 = 131072 'c' characters and a is an array |
| 1217 | // starting with 'bad', followed by 2^14 times the string s. That means the |
| 1218 | // total length of the concatenated strings is 2^31 + 3. So on 32bit systems |
| 1219 | // summing the lengths of the strings (as Smis) overflows and wraps. |
| 1220 | LocalContext context(isolate); |
| 1221 | v8::HandleScope scope(isolate); |
| 1222 | v8::TryCatch try_catch; |
| 1223 | CHECK(CompileRun( |
| 1224 | "var two_14 = Math.pow(2, 14);" |
| 1225 | "var two_17 = Math.pow(2, 17);" |
| 1226 | "var s = Array(two_17 + 1).join('c');" |
| 1227 | "var a = ['bad'];" |
| 1228 | "for (var i = 1; i <= two_14; i++) a.push(s);" |
| 1229 | "a.join(" |
| 1230 | ");").IsEmpty()); |
| 1231 | CHECK(try_catch.HasCaught()); |
| 1232 | } |
| 1233 | isolate->Exit(); |
| 1234 | isolate->Dispose(); |
| 1235 | } |
| 1236 | |
| 1237 | |
| 1238 | static void CheckException(const char* source) { |
| 1239 | // An empty handle is returned upon exception. |
| 1240 | CHECK(CompileRun(source).IsEmpty()); |
| 1241 | } |
| 1242 | |
| 1243 | |
| 1244 | TEST(RobustSubStringStub) { |
| 1245 | // This tests whether the SubStringStub can handle unsafe arguments. |
| 1246 | // If not recognized, those unsafe arguments lead to out-of-bounds reads. |
| 1247 | FLAG_allow_natives_syntax = true; |
| 1248 | CcTest::InitializeVM(); |
| 1249 | v8::HandleScope scope(CcTest::isolate()); |
| 1250 | v8::Local<v8::Value> result; |
| 1251 | Handle<String> string; |
| 1252 | CompileRun("var short = 'abcdef';"); |
| 1253 | |
| 1254 | // Invalid indices. |
| 1255 | CheckException("%_SubString(short, 0, 10000);"); |
| 1256 | CheckException("%_SubString(short, -1234, 5);"); |
| 1257 | CheckException("%_SubString(short, 5, 2);"); |
| 1258 | // Special HeapNumbers. |
| 1259 | CheckException("%_SubString(short, 1, Infinity);"); |
| 1260 | CheckException("%_SubString(short, NaN, 5);"); |
| 1261 | // String arguments. |
| 1262 | CheckException("%_SubString(short, '2', '5');"); |
| 1263 | // Ordinary HeapNumbers can be handled (in runtime). |
| 1264 | result = CompileRun("%_SubString(short, Math.sqrt(4), 5.1);"); |
| 1265 | string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1266 | CHECK_EQ("cde", string->ToCString().get()); |
| 1267 | |
| 1268 | CompileRun("var long = 'abcdefghijklmnopqrstuvwxyz';"); |
| 1269 | // Invalid indices. |
| 1270 | CheckException("%_SubString(long, 0, 10000);"); |
| 1271 | CheckException("%_SubString(long, -1234, 17);"); |
| 1272 | CheckException("%_SubString(long, 17, 2);"); |
| 1273 | // Special HeapNumbers. |
| 1274 | CheckException("%_SubString(long, 1, Infinity);"); |
| 1275 | CheckException("%_SubString(long, NaN, 17);"); |
| 1276 | // String arguments. |
| 1277 | CheckException("%_SubString(long, '2', '17');"); |
| 1278 | // Ordinary HeapNumbers within bounds can be handled (in runtime). |
| 1279 | result = CompileRun("%_SubString(long, Math.sqrt(4), 17.1);"); |
| 1280 | string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1281 | CHECK_EQ("cdefghijklmnopq", string->ToCString().get()); |
| 1282 | |
| 1283 | // Test that out-of-bounds substring of a slice fails when the indices |
| 1284 | // would have been valid for the underlying string. |
| 1285 | CompileRun("var slice = long.slice(1, 15);"); |
| 1286 | CheckException("%_SubString(slice, 0, 17);"); |
| 1287 | } |
| 1288 | |
| 1289 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 1290 | namespace { |
| 1291 | |
| 1292 | int* global_use_counts = NULL; |
| 1293 | |
| 1294 | void MockUseCounterCallback(v8::Isolate* isolate, |
| 1295 | v8::Isolate::UseCounterFeature feature) { |
| 1296 | ++global_use_counts[feature]; |
| 1297 | } |
| 1298 | } |
| 1299 | |
| 1300 | |
| 1301 | TEST(CountBreakIterator) { |
| 1302 | CcTest::InitializeVM(); |
| 1303 | v8::HandleScope scope(CcTest::isolate()); |
| 1304 | LocalContext context; |
| 1305 | int use_counts[v8::Isolate::kUseCounterFeatureCount] = {}; |
| 1306 | global_use_counts = use_counts; |
| 1307 | CcTest::isolate()->SetUseCounterCallback(MockUseCounterCallback); |
| 1308 | CHECK_EQ(0, use_counts[v8::Isolate::kBreakIterator]); |
| 1309 | v8::Local<v8::Value> result = CompileRun( |
| 1310 | "(function() {" |
| 1311 | " if (!this.Intl) return 0;" |
| 1312 | " var iterator = Intl.v8BreakIterator(['en']);" |
| 1313 | " iterator.adoptText('Now is the time');" |
| 1314 | " iterator.next();" |
| 1315 | " return iterator.next();" |
| 1316 | "})();"); |
| 1317 | CHECK(result->IsNumber()); |
| 1318 | int uses = result->ToInt32(CcTest::isolate())->Value() == 0 ? 0 : 1; |
| 1319 | CHECK_EQ(uses, use_counts[v8::Isolate::kBreakIterator]); |
| 1320 | // Make sure GC cleans up the break iterator, so we don't get a memory leak |
| 1321 | // reported by ASAN. |
| 1322 | CcTest::isolate()->LowMemoryNotification(); |
| 1323 | } |
| 1324 | |
| 1325 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1326 | TEST(StringReplaceAtomTwoByteResult) { |
| 1327 | CcTest::InitializeVM(); |
| 1328 | v8::HandleScope scope(CcTest::isolate()); |
| 1329 | LocalContext context; |
| 1330 | v8::Local<v8::Value> result = CompileRun( |
| 1331 | "var subject = 'one_byte~only~string~'; " |
| 1332 | "var replace = '\x80'; " |
| 1333 | "subject.replace(/~/g, replace); "); |
| 1334 | CHECK(result->IsString()); |
| 1335 | Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result)); |
| 1336 | CHECK(string->IsSeqTwoByteString()); |
| 1337 | |
| 1338 | v8::Local<v8::String> expected = v8_str("one_byte\x80only\x80string\x80"); |
| 1339 | CHECK(expected->Equals(result)); |
| 1340 | } |
| 1341 | |
| 1342 | |
| 1343 | TEST(IsAscii) { |
| 1344 | CHECK(String::IsAscii(static_cast<char*>(NULL), 0)); |
| 1345 | CHECK(String::IsOneByte(static_cast<uc16*>(NULL), 0)); |
| 1346 | } |
| 1347 | |
| 1348 | |
| 1349 | |
| 1350 | template<typename Op, bool return_first> |
| 1351 | static uint16_t ConvertLatin1(uint16_t c) { |
| 1352 | uint32_t result[Op::kMaxWidth]; |
| 1353 | int chars; |
| 1354 | chars = Op::Convert(c, 0, result, NULL); |
| 1355 | if (chars == 0) return 0; |
| 1356 | CHECK_LE(chars, static_cast<int>(sizeof(result))); |
| 1357 | if (!return_first && chars > 1) { |
| 1358 | return 0; |
| 1359 | } |
| 1360 | return result[0]; |
| 1361 | } |
| 1362 | |
| 1363 | |
| 1364 | static void CheckCanonicalEquivalence(uint16_t c, uint16_t test) { |
| 1365 | uint16_t expect = ConvertLatin1<unibrow::Ecma262UnCanonicalize, true>(c); |
| 1366 | if (expect > unibrow::Latin1::kMaxChar) expect = 0; |
| 1367 | CHECK_EQ(expect, test); |
| 1368 | } |
| 1369 | |
| 1370 | |
| 1371 | TEST(Latin1IgnoreCase) { |
| 1372 | using namespace unibrow; |
| 1373 | for (uint16_t c = Latin1::kMaxChar + 1; c != 0; c++) { |
| 1374 | uint16_t lower = ConvertLatin1<ToLowercase, false>(c); |
| 1375 | uint16_t upper = ConvertLatin1<ToUppercase, false>(c); |
| 1376 | uint16_t test = Latin1::ConvertNonLatin1ToLatin1(c); |
| 1377 | // Filter out all character whose upper is not their lower or vice versa. |
| 1378 | if (lower == 0 && upper == 0) { |
| 1379 | CheckCanonicalEquivalence(c, test); |
| 1380 | continue; |
| 1381 | } |
| 1382 | if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) { |
| 1383 | CheckCanonicalEquivalence(c, test); |
| 1384 | continue; |
| 1385 | } |
| 1386 | if (lower == 0 && upper != 0) { |
| 1387 | lower = ConvertLatin1<ToLowercase, false>(upper); |
| 1388 | } |
| 1389 | if (upper == 0 && lower != c) { |
| 1390 | upper = ConvertLatin1<ToUppercase, false>(lower); |
| 1391 | } |
| 1392 | if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) { |
| 1393 | CheckCanonicalEquivalence(c, test); |
| 1394 | continue; |
| 1395 | } |
| 1396 | if (upper != c && lower != c) { |
| 1397 | CheckCanonicalEquivalence(c, test); |
| 1398 | continue; |
| 1399 | } |
| 1400 | CHECK_EQ(Min(upper, lower), test); |
| 1401 | } |
| 1402 | } |
| 1403 | |
| 1404 | |
| 1405 | class DummyResource: public v8::String::ExternalStringResource { |
| 1406 | public: |
| 1407 | virtual const uint16_t* data() const { return NULL; } |
| 1408 | virtual size_t length() const { return 1 << 30; } |
| 1409 | }; |
| 1410 | |
| 1411 | |
| 1412 | class DummyOneByteResource: public v8::String::ExternalOneByteStringResource { |
| 1413 | public: |
| 1414 | virtual const char* data() const { return NULL; } |
| 1415 | virtual size_t length() const { return 1 << 30; } |
| 1416 | }; |
| 1417 | |
| 1418 | |
| 1419 | TEST(InvalidExternalString) { |
| 1420 | CcTest::InitializeVM(); |
| 1421 | LocalContext context; |
| 1422 | Isolate* isolate = CcTest::i_isolate(); |
| 1423 | { HandleScope scope(isolate); |
| 1424 | DummyOneByteResource r; |
| 1425 | CHECK(isolate->factory()->NewExternalStringFromOneByte(&r).is_null()); |
| 1426 | CHECK(isolate->has_pending_exception()); |
| 1427 | isolate->clear_pending_exception(); |
| 1428 | } |
| 1429 | |
| 1430 | { HandleScope scope(isolate); |
| 1431 | DummyResource r; |
| 1432 | CHECK(isolate->factory()->NewExternalStringFromTwoByte(&r).is_null()); |
| 1433 | CHECK(isolate->has_pending_exception()); |
| 1434 | isolate->clear_pending_exception(); |
| 1435 | } |
| 1436 | } |
| 1437 | |
| 1438 | |
| 1439 | #define INVALID_STRING_TEST(FUN, TYPE) \ |
| 1440 | TEST(StringOOM##FUN) { \ |
| 1441 | CcTest::InitializeVM(); \ |
| 1442 | LocalContext context; \ |
| 1443 | Isolate* isolate = CcTest::i_isolate(); \ |
| 1444 | STATIC_ASSERT(String::kMaxLength < kMaxInt); \ |
| 1445 | static const int invalid = String::kMaxLength + 1; \ |
| 1446 | HandleScope scope(isolate); \ |
| 1447 | Vector<TYPE> dummy = Vector<TYPE>::New(invalid); \ |
| 1448 | CHECK(isolate->factory()->FUN(Vector<const TYPE>::cast(dummy)).is_null()); \ |
| 1449 | memset(dummy.start(), 0x20, dummy.length() * sizeof(TYPE)); \ |
| 1450 | CHECK(isolate->has_pending_exception()); \ |
| 1451 | isolate->clear_pending_exception(); \ |
| 1452 | dummy.Dispose(); \ |
| 1453 | } |
| 1454 | |
| 1455 | INVALID_STRING_TEST(NewStringFromAscii, char) |
| 1456 | INVALID_STRING_TEST(NewStringFromUtf8, char) |
| 1457 | INVALID_STRING_TEST(NewStringFromOneByte, uint8_t) |
| 1458 | |
| 1459 | #undef INVALID_STRING_TEST |