1 // Copyright 2006-2008 the V8 project authors. All rights reserved.
2
3 // Check that we can traverse very deep stacks of ConsStrings using
4 // StringInputBuffer. Check that Get(int) works on very deep stacks
5 // of ConsStrings. These operations may not be very fast, but they
6 // should be possible without getting errors due to too deep recursion.
7
8 #include <stdlib.h>
9
10 #include "v8.h"
11
12 #include "api.h"
13 #include "factory.h"
14 #include "cctest.h"
15 #include "zone-inl.h"
16
17 unsigned int seed = 123;
18
gen()19 static uint32_t gen() {
20 uint64_t z;
21 z = seed;
22 z *= 279470273;
23 z %= 4294967291U;
24 seed = static_cast<unsigned int>(z);
25 return static_cast<uint32_t>(seed >> 16);
26 }
27
28
29 using namespace v8::internal;
30
31 static v8::Persistent<v8::Context> env;
32
33
InitializeVM()34 static void InitializeVM() {
35 if (env.IsEmpty()) {
36 v8::HandleScope scope;
37 const char* extensions[] = { "v8/print" };
38 v8::ExtensionConfiguration config(1, extensions);
39 env = v8::Context::New(&config);
40 }
41 v8::HandleScope scope;
42 env->Enter();
43 }
44
45
46 static const int NUMBER_OF_BUILDING_BLOCKS = 128;
47 static const int DEEP_DEPTH = 8 * 1024;
48 static const int SUPER_DEEP_DEPTH = 80 * 1024;
49
50
51 class Resource: public v8::String::ExternalStringResource,
52 public ZoneObject {
53 public:
Resource(Vector<const uc16> string)54 explicit Resource(Vector<const uc16> string): data_(string.start()) {
55 length_ = string.length();
56 }
data() const57 virtual const uint16_t* data() const { return data_; }
length() const58 virtual size_t length() const { return length_; }
59
60 private:
61 const uc16* data_;
62 size_t length_;
63 };
64
65
66 class AsciiResource: public v8::String::ExternalAsciiStringResource,
67 public ZoneObject {
68 public:
AsciiResource(Vector<const char> string)69 explicit AsciiResource(Vector<const char> string): data_(string.start()) {
70 length_ = string.length();
71 }
data() const72 virtual const char* data() const { return data_; }
length() const73 virtual size_t length() const { return length_; }
74
75 private:
76 const char* data_;
77 size_t length_;
78 };
79
80
InitializeBuildingBlocks(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS])81 static void InitializeBuildingBlocks(
82 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS]) {
83 // A list of pointers that we don't have any interest in cleaning up.
84 // If they are reachable from a root then leak detection won't complain.
85 for (int i = 0; i < NUMBER_OF_BUILDING_BLOCKS; i++) {
86 int len = gen() % 16;
87 if (len > 14) {
88 len += 1234;
89 }
90 switch (gen() % 4) {
91 case 0: {
92 uc16 buf[2000];
93 for (int j = 0; j < len; j++) {
94 buf[j] = gen() % 65536;
95 }
96 building_blocks[i] =
97 Factory::NewStringFromTwoByte(Vector<const uc16>(buf, len));
98 for (int j = 0; j < len; j++) {
99 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
100 }
101 break;
102 }
103 case 1: {
104 char buf[2000];
105 for (int j = 0; j < len; j++) {
106 buf[j] = gen() % 128;
107 }
108 building_blocks[i] =
109 Factory::NewStringFromAscii(Vector<const char>(buf, len));
110 for (int j = 0; j < len; j++) {
111 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
112 }
113 break;
114 }
115 case 2: {
116 uc16* buf = Zone::NewArray<uc16>(len);
117 for (int j = 0; j < len; j++) {
118 buf[j] = gen() % 65536;
119 }
120 Resource* resource = new Resource(Vector<const uc16>(buf, len));
121 building_blocks[i] = Factory::NewExternalStringFromTwoByte(resource);
122 for (int j = 0; j < len; j++) {
123 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
124 }
125 break;
126 }
127 case 3: {
128 char* buf = NewArray<char>(len);
129 for (int j = 0; j < len; j++) {
130 buf[j] = gen() % 128;
131 }
132 building_blocks[i] =
133 Factory::NewStringFromAscii(Vector<const char>(buf, len));
134 for (int j = 0; j < len; j++) {
135 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
136 }
137 DeleteArray<char>(buf);
138 break;
139 }
140 }
141 }
142 }
143
144
ConstructLeft(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],int depth)145 static Handle<String> ConstructLeft(
146 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
147 int depth) {
148 Handle<String> answer = Factory::NewStringFromAscii(CStrVector(""));
149 for (int i = 0; i < depth; i++) {
150 answer = Factory::NewConsString(
151 answer,
152 building_blocks[i % NUMBER_OF_BUILDING_BLOCKS]);
153 }
154 return answer;
155 }
156
157
ConstructRight(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],int depth)158 static Handle<String> ConstructRight(
159 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
160 int depth) {
161 Handle<String> answer = Factory::NewStringFromAscii(CStrVector(""));
162 for (int i = depth - 1; i >= 0; i--) {
163 answer = Factory::NewConsString(
164 building_blocks[i % NUMBER_OF_BUILDING_BLOCKS],
165 answer);
166 }
167 return answer;
168 }
169
170
ConstructBalancedHelper(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],int from,int to)171 static Handle<String> ConstructBalancedHelper(
172 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
173 int from,
174 int to) {
175 CHECK(to > from);
176 if (to - from == 1) {
177 return building_blocks[from % NUMBER_OF_BUILDING_BLOCKS];
178 }
179 if (to - from == 2) {
180 return Factory::NewConsString(
181 building_blocks[from % NUMBER_OF_BUILDING_BLOCKS],
182 building_blocks[(from+1) % NUMBER_OF_BUILDING_BLOCKS]);
183 }
184 Handle<String> part1 =
185 ConstructBalancedHelper(building_blocks, from, from + ((to - from) / 2));
186 Handle<String> part2 =
187 ConstructBalancedHelper(building_blocks, from + ((to - from) / 2), to);
188 return Factory::NewConsString(part1, part2);
189 }
190
191
ConstructBalanced(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS])192 static Handle<String> ConstructBalanced(
193 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS]) {
194 return ConstructBalancedHelper(building_blocks, 0, DEEP_DEPTH);
195 }
196
197
198 static StringInputBuffer buffer;
199
200
Traverse(Handle<String> s1,Handle<String> s2)201 static void Traverse(Handle<String> s1, Handle<String> s2) {
202 int i = 0;
203 buffer.Reset(*s1);
204 StringInputBuffer buffer2(*s2);
205 while (buffer.has_more()) {
206 CHECK(buffer2.has_more());
207 uint16_t c = buffer.GetNext();
208 CHECK_EQ(c, buffer2.GetNext());
209 i++;
210 }
211 CHECK_EQ(s1->length(), i);
212 CHECK_EQ(s2->length(), i);
213 }
214
215
TraverseFirst(Handle<String> s1,Handle<String> s2,int chars)216 static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
217 int i = 0;
218 buffer.Reset(*s1);
219 StringInputBuffer buffer2(*s2);
220 while (buffer.has_more() && i < chars) {
221 CHECK(buffer2.has_more());
222 uint16_t c = buffer.GetNext();
223 CHECK_EQ(c, buffer2.GetNext());
224 i++;
225 }
226 s1->Get(s1->length() - 1);
227 s2->Get(s2->length() - 1);
228 }
229
230
TEST(Traverse)231 TEST(Traverse) {
232 printf("TestTraverse\n");
233 InitializeVM();
234 v8::HandleScope scope;
235 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS];
236 ZoneScope zone(DELETE_ON_EXIT);
237 InitializeBuildingBlocks(building_blocks);
238 Handle<String> flat = ConstructBalanced(building_blocks);
239 FlattenString(flat);
240 Handle<String> left_asymmetric = ConstructLeft(building_blocks, DEEP_DEPTH);
241 Handle<String> right_asymmetric = ConstructRight(building_blocks, DEEP_DEPTH);
242 Handle<String> symmetric = ConstructBalanced(building_blocks);
243 printf("1\n");
244 Traverse(flat, symmetric);
245 printf("2\n");
246 Traverse(flat, left_asymmetric);
247 printf("3\n");
248 Traverse(flat, right_asymmetric);
249 printf("4\n");
250 Handle<String> left_deep_asymmetric =
251 ConstructLeft(building_blocks, SUPER_DEEP_DEPTH);
252 Handle<String> right_deep_asymmetric =
253 ConstructRight(building_blocks, SUPER_DEEP_DEPTH);
254 printf("5\n");
255 TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
256 printf("6\n");
257 TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
258 printf("7\n");
259 FlattenString(left_asymmetric);
260 printf("10\n");
261 Traverse(flat, left_asymmetric);
262 printf("11\n");
263 FlattenString(right_asymmetric);
264 printf("12\n");
265 Traverse(flat, right_asymmetric);
266 printf("14\n");
267 FlattenString(symmetric);
268 printf("15\n");
269 Traverse(flat, symmetric);
270 printf("16\n");
271 FlattenString(left_deep_asymmetric);
272 printf("18\n");
273 }
274
275
276 static const int DEEP_ASCII_DEPTH = 100000;
277
278
TEST(DeepAscii)279 TEST(DeepAscii) {
280 printf("TestDeepAscii\n");
281 InitializeVM();
282 v8::HandleScope scope;
283
284 char* foo = NewArray<char>(DEEP_ASCII_DEPTH);
285 for (int i = 0; i < DEEP_ASCII_DEPTH; i++) {
286 foo[i] = "foo "[i % 4];
287 }
288 Handle<String> string =
289 Factory::NewStringFromAscii(Vector<const char>(foo, DEEP_ASCII_DEPTH));
290 Handle<String> foo_string = Factory::NewStringFromAscii(CStrVector("foo"));
291 for (int i = 0; i < DEEP_ASCII_DEPTH; i += 10) {
292 string = Factory::NewConsString(string, foo_string);
293 }
294 Handle<String> flat_string = Factory::NewConsString(string, foo_string);
295 FlattenString(flat_string);
296
297 for (int i = 0; i < 500; i++) {
298 TraverseFirst(flat_string, string, DEEP_ASCII_DEPTH);
299 }
300 DeleteArray<char>(foo);
301 }
302
303
TEST(Utf8Conversion)304 TEST(Utf8Conversion) {
305 // Smoke test for converting strings to utf-8.
306 InitializeVM();
307 v8::HandleScope handle_scope;
308 // A simple ascii string
309 const char* ascii_string = "abcdef12345";
310 int len =
311 v8::String::New(ascii_string,
312 StrLength(ascii_string))->Utf8Length();
313 CHECK_EQ(StrLength(ascii_string), len);
314 // A mixed ascii and non-ascii string
315 // U+02E4 -> CB A4
316 // U+0064 -> 64
317 // U+12E4 -> E1 8B A4
318 // U+0030 -> 30
319 // U+3045 -> E3 81 85
320 const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045};
321 // The characters we expect to be output
322 const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
323 0xE3, 0x81, 0x85, 0x00};
324 // The number of bytes expected to be written for each length
325 const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11};
326 v8::Handle<v8::String> mixed = v8::String::New(mixed_string, 5);
327 CHECK_EQ(10, mixed->Utf8Length());
328 // Try encoding the string with all capacities
329 char buffer[11];
330 const char kNoChar = static_cast<char>(-1);
331 for (int i = 0; i <= 11; i++) {
332 // Clear the buffer before reusing it
333 for (int j = 0; j < 11; j++)
334 buffer[j] = kNoChar;
335 int written = mixed->WriteUtf8(buffer, i);
336 CHECK_EQ(lengths[i], written);
337 // Check that the contents are correct
338 for (int j = 0; j < lengths[i]; j++)
339 CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
340 // Check that the rest of the buffer hasn't been touched
341 for (int j = lengths[i]; j < 11; j++)
342 CHECK_EQ(kNoChar, buffer[j]);
343 }
344 }
345
346
TEST(ExternalShortStringAdd)347 TEST(ExternalShortStringAdd) {
348 ZoneScope zone(DELETE_ON_EXIT);
349
350 InitializeVM();
351 v8::HandleScope handle_scope;
352
353 // Make sure we cover all always-flat lengths and at least one above.
354 static const int kMaxLength = 20;
355 CHECK_GT(kMaxLength, i::String::kMinNonFlatLength);
356
357 // Allocate two JavaScript arrays for holding short strings.
358 v8::Handle<v8::Array> ascii_external_strings =
359 v8::Array::New(kMaxLength + 1);
360 v8::Handle<v8::Array> non_ascii_external_strings =
361 v8::Array::New(kMaxLength + 1);
362
363 // Generate short ascii and non-ascii external strings.
364 for (int i = 0; i <= kMaxLength; i++) {
365 char* ascii = Zone::NewArray<char>(i + 1);
366 for (int j = 0; j < i; j++) {
367 ascii[j] = 'a';
368 }
369 // Terminating '\0' is left out on purpose. It is not required for external
370 // string data.
371 AsciiResource* ascii_resource =
372 new AsciiResource(Vector<const char>(ascii, i));
373 v8::Local<v8::String> ascii_external_string =
374 v8::String::NewExternal(ascii_resource);
375
376 ascii_external_strings->Set(v8::Integer::New(i), ascii_external_string);
377 uc16* non_ascii = Zone::NewArray<uc16>(i + 1);
378 for (int j = 0; j < i; j++) {
379 non_ascii[j] = 0x1234;
380 }
381 // Terminating '\0' is left out on purpose. It is not required for external
382 // string data.
383 Resource* resource = new Resource(Vector<const uc16>(non_ascii, i));
384 v8::Local<v8::String> non_ascii_external_string =
385 v8::String::NewExternal(resource);
386 non_ascii_external_strings->Set(v8::Integer::New(i),
387 non_ascii_external_string);
388 }
389
390 // Add the arrays with the short external strings in the global object.
391 v8::Handle<v8::Object> global = env->Global();
392 global->Set(v8_str("external_ascii"), ascii_external_strings);
393 global->Set(v8_str("external_non_ascii"), non_ascii_external_strings);
394 global->Set(v8_str("max_length"), v8::Integer::New(kMaxLength));
395
396 // Add short external ascii and non-ascii strings checking the result.
397 static const char* source =
398 "function test() {"
399 " var ascii_chars = 'aaaaaaaaaaaaaaaaaaaa';"
400 " var non_ascii_chars = '\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234';" //NOLINT
401 " if (ascii_chars.length != max_length) return 1;"
402 " if (non_ascii_chars.length != max_length) return 2;"
403 " var ascii = Array(max_length + 1);"
404 " var non_ascii = Array(max_length + 1);"
405 " for (var i = 0; i <= max_length; i++) {"
406 " ascii[i] = ascii_chars.substring(0, i);"
407 " non_ascii[i] = non_ascii_chars.substring(0, i);"
408 " };"
409 " for (var i = 0; i <= max_length; i++) {"
410 " if (ascii[i] != external_ascii[i]) return 3;"
411 " if (non_ascii[i] != external_non_ascii[i]) return 4;"
412 " for (var j = 0; j < i; j++) {"
413 " if (external_ascii[i] !="
414 " (external_ascii[j] + external_ascii[i - j])) return 5;"
415 " if (external_non_ascii[i] !="
416 " (external_non_ascii[j] + external_non_ascii[i - j])) return 6;"
417 " if (non_ascii[i] != (non_ascii[j] + non_ascii[i - j])) return 7;"
418 " if (ascii[i] != (ascii[j] + ascii[i - j])) return 8;"
419 " if (ascii[i] != (external_ascii[j] + ascii[i - j])) return 9;"
420 " if (ascii[i] != (ascii[j] + external_ascii[i - j])) return 10;"
421 " if (non_ascii[i] !="
422 " (external_non_ascii[j] + non_ascii[i - j])) return 11;"
423 " if (non_ascii[i] !="
424 " (non_ascii[j] + external_non_ascii[i - j])) return 12;"
425 " }"
426 " }"
427 " return 0;"
428 "};"
429 "test()";
430 CHECK_EQ(0,
431 v8::Script::Compile(v8::String::New(source))->Run()->Int32Value());
432 }
433