• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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