Revision: 13217
Author: [email protected]
Date: Thu Dec 13 07:39:01 2012
Log: Cleanup tests for StringCharacterStream
Edge case tests now cover all branches.
[email protected]
BUG=
Review URL: https://chromiumcodereview.appspot.com/11548023
Patch from Dan Carney <[email protected]>.
http://code.google.com/p/v8/source/detail?r=13217
Modified:
/branches/bleeding_edge/test/cctest/test-strings.cc
=======================================
--- /branches/bleeding_edge/test/cctest/test-strings.cc Tue Dec 11 02:42:10
2012
+++ /branches/bleeding_edge/test/cctest/test-strings.cc Thu Dec 13 07:39:01
2012
@@ -85,7 +85,6 @@
}
-static const int NUMBER_OF_BUILDING_BLOCKS = 256;
static const int DEEP_DEPTH = 8 * 1024;
static const int SUPER_DEEP_DEPTH = 80 * 1024;
@@ -191,7 +190,7 @@
case 3: {
char* buf = zone->NewArray<char>(len);
for (int j = 0; j < len; j++) {
- buf[j] = rng->next(128);
+ buf[j] = rng->next(0x80);
}
AsciiResource* resource =
new(zone) AsciiResource(Vector<const char>(buf, len));
@@ -211,155 +210,6 @@
CHECK(len == building_blocks[i]->length() + slice_length);
}
}
-
-
-static Handle<String> ConstructLeft(
- Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
- int depth) {
- Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
- for (int i = 0; i < depth; i++) {
- answer = FACTORY->NewConsString(
- answer,
- building_blocks[i % NUMBER_OF_BUILDING_BLOCKS]);
- }
- return answer;
-}
-
-
-static Handle<String> ConstructRight(
- Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
- int depth) {
- Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
- for (int i = depth - 1; i >= 0; i--) {
- answer = FACTORY->NewConsString(
- building_blocks[i % NUMBER_OF_BUILDING_BLOCKS],
- answer);
- }
- return answer;
-}
-
-
-static Handle<String> ConstructBalancedHelper(
- Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
- int from,
- int to) {
- CHECK(to > from);
- if (to - from == 1) {
- return building_blocks[from % NUMBER_OF_BUILDING_BLOCKS];
- }
- if (to - from == 2) {
- return FACTORY->NewConsString(
- building_blocks[from % NUMBER_OF_BUILDING_BLOCKS],
- building_blocks[(from+1) % NUMBER_OF_BUILDING_BLOCKS]);
- }
- Handle<String> part1 =
- ConstructBalancedHelper(building_blocks, from, from + ((to - from) /
2));
- Handle<String> part2 =
- ConstructBalancedHelper(building_blocks, from + ((to - from) / 2), to);
- return FACTORY->NewConsString(part1, part2);
-}
-
-
-static Handle<String> ConstructBalanced(
- Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS]) {
- return ConstructBalancedHelper(building_blocks, 0, DEEP_DEPTH);
-}
-
-
-static StringInputBuffer buffer;
-static ConsStringIteratorOp cons_string_iterator_op_1;
-static ConsStringIteratorOp cons_string_iterator_op_2;
-
-static void Traverse(Handle<String> s1, Handle<String> s2) {
- int i = 0;
- buffer.Reset(*s1);
- StringCharacterStream character_stream_1(*s1, 0,
&cons_string_iterator_op_1);
- StringCharacterStream character_stream_2(*s2, 0,
&cons_string_iterator_op_2);
- StringInputBuffer buffer2(*s2);
- while (buffer.has_more()) {
- CHECK(buffer2.has_more());
- CHECK(character_stream_1.HasMore());
- CHECK(character_stream_2.HasMore());
- uint16_t c = buffer.GetNext();
- CHECK_EQ(c, buffer2.GetNext());
- CHECK_EQ(c, character_stream_1.GetNext());
- CHECK_EQ(c, character_stream_2.GetNext());
- i++;
- }
- CHECK(!character_stream_1.HasMore());
- CHECK(!character_stream_2.HasMore());
- CHECK_EQ(s1->length(), i);
- CHECK_EQ(s2->length(), i);
-}
-
-
-static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars)
{
- int i = 0;
- buffer.Reset(*s1);
- StringInputBuffer buffer2(*s2);
- StringCharacterStream character_stream_1(*s1, 0,
&cons_string_iterator_op_1);
- StringCharacterStream character_stream_2(*s2, 0,
&cons_string_iterator_op_2);
- while (buffer.has_more() && i < chars) {
- CHECK(buffer2.has_more());
- CHECK(character_stream_1.HasMore());
- CHECK(character_stream_2.HasMore());
- uint16_t c = buffer.GetNext();
- CHECK_EQ(c, buffer2.GetNext());
- CHECK_EQ(c, character_stream_1.GetNext());
- CHECK_EQ(c, character_stream_2.GetNext());
- i++;
- }
- s1->Get(s1->length() - 1);
- s2->Get(s2->length() - 1);
-}
-
-
-TEST(Traverse) {
- printf("TestTraverse\n");
- InitializeVM();
- v8::HandleScope scope;
- Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS];
- ZoneScope zone(Isolate::Current()->runtime_zone(), DELETE_ON_EXIT);
- RandomNumberGenerator rng;
- rng.init();
- InitializeBuildingBlocks(
- building_blocks, NUMBER_OF_BUILDING_BLOCKS, false, &rng);
- Handle<String> flat = ConstructBalanced(building_blocks);
- FlattenString(flat);
- Handle<String> left_asymmetric = ConstructLeft(building_blocks,
DEEP_DEPTH);
- Handle<String> right_asymmetric = ConstructRight(building_blocks,
DEEP_DEPTH);
- Handle<String> symmetric = ConstructBalanced(building_blocks);
- printf("1\n");
- Traverse(flat, symmetric);
- printf("2\n");
- Traverse(flat, left_asymmetric);
- printf("3\n");
- Traverse(flat, right_asymmetric);
- printf("4\n");
- Handle<String> left_deep_asymmetric =
- ConstructLeft(building_blocks, SUPER_DEEP_DEPTH);
- Handle<String> right_deep_asymmetric =
- ConstructRight(building_blocks, SUPER_DEEP_DEPTH);
- printf("5\n");
- TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
- printf("6\n");
- TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
- printf("7\n");
- FlattenString(left_asymmetric);
- printf("10\n");
- Traverse(flat, left_asymmetric);
- printf("11\n");
- FlattenString(right_asymmetric);
- printf("12\n");
- Traverse(flat, right_asymmetric);
- printf("14\n");
- FlattenString(symmetric);
- printf("15\n");
- Traverse(flat, symmetric);
- printf("16\n");
- FlattenString(left_deep_asymmetric);
- printf("18\n");
-}
class ConsStringStats {
@@ -399,8 +249,11 @@
class ConsStringGenerationData {
public:
- ConsStringGenerationData();
+ static const int kNumberOfBuildingBlocks = 256;
+ explicit ConsStringGenerationData(bool long_blocks);
void Reset();
+ inline Handle<String> block(int offset);
+ inline Handle<String> block(uint32_t offset);
// Input variables.
double early_termination_threshold_;
double leftness_;
@@ -408,7 +261,7 @@
double empty_leaf_threshold_;
unsigned max_leaves_;
// Cached data.
- Handle<String> building_blocks_[NUMBER_OF_BUILDING_BLOCKS];
+ Handle<String> building_blocks_[kNumberOfBuildingBlocks];
String* empty_string_;
RandomNumberGenerator rng_;
// Stats.
@@ -419,13 +272,24 @@
};
-ConsStringGenerationData::ConsStringGenerationData() {
+ConsStringGenerationData::ConsStringGenerationData(bool long_blocks) {
rng_.init();
InitializeBuildingBlocks(
- building_blocks_, NUMBER_OF_BUILDING_BLOCKS, true, &rng_);
+ building_blocks_, kNumberOfBuildingBlocks, long_blocks, &rng_);
empty_string_ = Isolate::Current()->heap()->empty_string();
Reset();
}
+
+
+Handle<String> ConsStringGenerationData::block(uint32_t offset) {
+ return building_blocks_[offset % kNumberOfBuildingBlocks ];
+}
+
+
+Handle<String> ConsStringGenerationData::block(int offset) {
+ CHECK_GE(offset, 0);
+ return building_blocks_[offset % kNumberOfBuildingBlocks];
+}
void ConsStringGenerationData::Reset() {
@@ -436,17 +300,19 @@
max_leaves_ = 1000;
stats_.Reset();
early_terminations_ = 0;
+ rng_.init();
}
-void VerifyConsString(ConsString* cons_string, ConsStringStats* stats) {
+void AccumulateStats(ConsString* cons_string, ConsStringStats* stats) {
int left_length = cons_string->first()->length();
int right_length = cons_string->second()->length();
CHECK(cons_string->length() == left_length + right_length);
// Check left side.
- if (cons_string->first()->IsConsString()) {
+ bool left_is_cons = cons_string->first()->IsConsString();
+ if (left_is_cons) {
stats->left_traversals_++;
- VerifyConsString(ConsString::cast(cons_string->first()), stats);
+ AccumulateStats(ConsString::cast(cons_string->first()), stats);
} else {
CHECK_NE(left_length, 0);
stats->leaves_++;
@@ -455,16 +321,29 @@
// Check right side.
if (cons_string->second()->IsConsString()) {
stats->right_traversals_++;
- VerifyConsString(ConsString::cast(cons_string->second()), stats);
+ AccumulateStats(ConsString::cast(cons_string->second()), stats);
} else {
- if (right_length == 0) stats->empty_leaves_++;
+ if (right_length == 0) {
+ stats->empty_leaves_++;
+ CHECK(!left_is_cons);
+ }
stats->leaves_++;
stats->chars_ += right_length;
}
}
-void VerifyConsStringWithOperator(
+void AccumulateStats(Handle<String> cons_string, ConsStringStats* stats) {
+ AssertNoAllocation no_alloc;
+ if (cons_string->IsConsString()) {
+ return AccumulateStats(ConsString::cast(*cons_string), stats);
+ }
+ // This string got flattened by gc.
+ stats->chars_ += cons_string->length();
+}
+
+
+void AccumulateStatsWithOperator(
ConsString* cons_string, ConsStringStats* stats) {
// Init op.
ConsStringIteratorOp op;
@@ -506,11 +385,11 @@
CHECK((unsigned)root->length() == data->stats_.chars_);
// Recursive verify.
ConsStringStats stats;
- VerifyConsString(ConsString::cast(*root), &stats);
+ AccumulateStats(ConsString::cast(*root), &stats);
stats.VerifyEqual(data->stats_);
// Iteratively verify.
stats.Reset();
- VerifyConsStringWithOperator(ConsString::cast(*root), &stats);
+ AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
// Don't see these. Must copy over.
stats.empty_leaves_ = data->stats_.empty_leaves_;
stats.left_traversals_ = data->stats_.left_traversals_;
@@ -542,23 +421,32 @@
// Generate left string.
Handle<String> left;
if (terminate_left) {
- left =
data->building_blocks_[data->rng_.next(NUMBER_OF_BUILDING_BLOCKS)];
+ left = data->block(data->rng_.next());
data->stats_.leaves_++;
data->stats_.chars_ += left->length();
} else {
- left = ConstructRandomString(data, max_recursion - 1);
data->stats_.left_traversals_++;
}
// Generate right string.
Handle<String> right;
if (terminate_right) {
- right =
data->building_blocks_[data->rng_.next(NUMBER_OF_BUILDING_BLOCKS)];
+ right = data->block(data->rng_.next());
data->stats_.leaves_++;
data->stats_.chars_ += right->length();
} else {
- right = ConstructRandomString(data, max_recursion - 1);
data->stats_.right_traversals_++;
}
+ // Generate the necessary sub-nodes recursively.
+ if (!terminate_right) {
+ // Need to balance generation fairly.
+ if (!terminate_left && data->rng_.next(0.5)) {
+ left = ConstructRandomString(data, max_recursion - 1);
+ }
+ right = ConstructRandomString(data, max_recursion - 1);
+ }
+ if (!terminate_left && left.is_null()) {
+ left = ConstructRandomString(data, max_recursion - 1);
+ }
// Build the cons string.
Handle<String> root = FACTORY->NewConsString(left, right);
CHECK(root->IsConsString() && !root->IsFlat());
@@ -572,63 +460,169 @@
}
-static const int kCharacterStreamRandomCases = 150;
-static const int kCharacterStreamEdgeCases =
- kCharacterStreamRandomCases + 5;
+static Handle<String> ConstructLeft(
+ ConsStringGenerationData* data,
+ int depth) {
+ Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
+ data->stats_.leaves_++;
+ for (int i = 0; i < depth; i++) {
+ Handle<String> block = data->block(i);
+ Handle<String> next = FACTORY->NewConsString(answer, block);
+ if (next->IsConsString()) data->stats_.leaves_++;
+ data->stats_.chars_ += block->length();
+ answer = next;
+ }
+ data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
+ return answer;
+}
-static Handle<String> BuildConsStrings(int testCase,
- ConsStringGenerationData* data) {
- // For random constructions, need to reset the generator.
- data->rng_.init();
- for (int j = 0; j < testCase * 50; j++) {
- data->rng_.next();
+static Handle<String> ConstructRight(
+ ConsStringGenerationData* data,
+ int depth) {
+ Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
+ data->stats_.leaves_++;
+ for (int i = depth - 1; i >= 0; i--) {
+ Handle<String> block = data->block(i);
+ Handle<String> next = FACTORY->NewConsString(block, answer);
+ if (next->IsConsString()) data->stats_.leaves_++;
+ data->stats_.chars_ += block->length();
+ answer = next;
}
- Handle<String> string;
- switch (testCase) {
- case 0:
- return ConstructBalanced(data->building_blocks_);
- case 1:
- return ConstructLeft(data->building_blocks_, DEEP_DEPTH);
- case 2:
- return ConstructRight(data->building_blocks_, DEEP_DEPTH);
- case 3:
- return ConstructLeft(data->building_blocks_, 10);
- case 4:
- return ConstructRight(data->building_blocks_, 10);
- case 5:
- return FACTORY->NewConsString(
- data->building_blocks_[0], data->building_blocks_[1]);
- default:
- if (testCase >= kCharacterStreamEdgeCases) {
- CHECK(false);
- return string;
- }
- // Random test case.
- data->Reset();
- string = ConstructRandomString(data, 200);
- AssertNoAllocation no_alloc;
- VerifyConsString(string, data);
-#ifdef DEBUG
- printf(
- "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\n",
- "leaves", data->stats_.leaves_,
- "empty", data->stats_.empty_leaves_,
- "chars", data->stats_.chars_,
- "lefts", data->stats_.left_traversals_,
- "rights", data->stats_.right_traversals_,
- "early_terminations", data->early_terminations_);
-#endif
- return string;
- }
+ data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
+ return answer;
+}
+
+
+static Handle<String> ConstructBalancedHelper(
+ ConsStringGenerationData* data,
+ int from,
+ int to) {
+ CHECK(to > from);
+ if (to - from == 1) {
+ data->stats_.chars_ += data->block(from)->length();
+ return data->block(from);
+ }
+ if (to - from == 2) {
+ data->stats_.chars_ += data->block(from)->length();
+ data->stats_.chars_ += data->block(from+1)->length();
+ return FACTORY->NewConsString(data->block(from), data->block(from+1));
+ }
+ Handle<String> part1 =
+ ConstructBalancedHelper(data, from, from + ((to - from) / 2));
+ Handle<String> part2 =
+ ConstructBalancedHelper(data, from + ((to - from) / 2), to);
+ if (part1->IsConsString()) data->stats_.left_traversals_++;
+ if (part2->IsConsString()) data->stats_.right_traversals_++;
+ return FACTORY->NewConsString(part1, part2);
+}
+
+
+static Handle<String> ConstructBalanced(
+ ConsStringGenerationData* data, int depth = DEEP_DEPTH) {
+ Handle<String> string = ConstructBalancedHelper(data, 0, depth);
+ data->stats_.leaves_ =
+ data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2;
+ return string;
+}
+
+
+static StringInputBuffer buffer;
+static ConsStringIteratorOp cons_string_iterator_op_1;
+static ConsStringIteratorOp cons_string_iterator_op_2;
+
+static void Traverse(Handle<String> s1, Handle<String> s2) {
+ int i = 0;
+ buffer.Reset(*s1);
+ StringCharacterStream character_stream_1(*s1, 0,
&cons_string_iterator_op_1);
+ StringCharacterStream character_stream_2(*s2, 0,
&cons_string_iterator_op_2);
+ StringInputBuffer buffer2(*s2);
+ while (buffer.has_more()) {
+ CHECK(buffer2.has_more());
+ CHECK(character_stream_1.HasMore());
+ CHECK(character_stream_2.HasMore());
+ uint16_t c = buffer.GetNext();
+ CHECK_EQ(c, buffer2.GetNext());
+ CHECK_EQ(c, character_stream_1.GetNext());
+ CHECK_EQ(c, character_stream_2.GetNext());
+ i++;
+ }
+ CHECK(!character_stream_1.HasMore());
+ CHECK(!character_stream_2.HasMore());
+ CHECK_EQ(s1->length(), i);
+ CHECK_EQ(s2->length(), i);
+}
+
+
+static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars)
{
+ int i = 0;
+ buffer.Reset(*s1);
+ StringInputBuffer buffer2(*s2);
+ StringCharacterStream character_stream_1(*s1, 0,
&cons_string_iterator_op_1);
+ StringCharacterStream character_stream_2(*s2, 0,
&cons_string_iterator_op_2);
+ while (buffer.has_more() && i < chars) {
+ CHECK(buffer2.has_more());
+ CHECK(character_stream_1.HasMore());
+ CHECK(character_stream_2.HasMore());
+ uint16_t c = buffer.GetNext();
+ CHECK_EQ(c, buffer2.GetNext());
+ CHECK_EQ(c, character_stream_1.GetNext());
+ CHECK_EQ(c, character_stream_2.GetNext());
+ i++;
+ }
+ s1->Get(s1->length() - 1);
+ s2->Get(s2->length() - 1);
+}
+
+
+TEST(Traverse) {
+ printf("TestTraverse\n");
+ InitializeVM();
+ v8::HandleScope scope;
+ ZoneScope zone(Isolate::Current()->runtime_zone(), DELETE_ON_EXIT);
+ ConsStringGenerationData data(false);
+ Handle<String> flat = ConstructBalanced(&data);
+ FlattenString(flat);
+ Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH);
+ Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH);
+ Handle<String> symmetric = ConstructBalanced(&data);
+ printf("1\n");
+ Traverse(flat, symmetric);
+ printf("2\n");
+ Traverse(flat, left_asymmetric);
+ printf("3\n");
+ Traverse(flat, right_asymmetric);
+ printf("4\n");
+ Handle<String> left_deep_asymmetric =
+ ConstructLeft(&data, SUPER_DEEP_DEPTH);
+ Handle<String> right_deep_asymmetric =
+ ConstructRight(&data, SUPER_DEEP_DEPTH);
+ printf("5\n");
+ TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
+ printf("6\n");
+ TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
+ printf("7\n");
+ FlattenString(left_asymmetric);
+ printf("10\n");
+ Traverse(flat, left_asymmetric);
+ printf("11\n");
+ FlattenString(right_asymmetric);
+ printf("12\n");
+ Traverse(flat, right_asymmetric);
+ printf("14\n");
+ FlattenString(symmetric);
+ printf("15\n");
+ Traverse(flat, symmetric);
+ printf("16\n");
+ FlattenString(left_deep_asymmetric);
+ printf("18\n");
}
static void VerifyCharacterStream(
String* flat_string, String* cons_string) {
// Do not want to test ConString traversal on flat string.
- CHECK(flat_string->IsFlat());
- CHECK(!flat_string->IsConsString());
+ CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
CHECK(cons_string->IsConsString());
// TODO(dcarney) Test stream reset as well.
int length = flat_string->length();
@@ -656,28 +650,231 @@
}
-TEST(StringCharacterStreamEdgeCases) {
- printf("TestStringCharacterStreamEdgeCases\n");
+static inline void PrintStats(const ConsStringGenerationData& data) {
+#ifdef DEBUG
+printf(
+ "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\n",
+ "leaves", data.stats_.leaves_,
+ "empty", data.stats_.empty_leaves_,
+ "chars", data.stats_.chars_,
+ "lefts", data.stats_.left_traversals_,
+ "rights", data.stats_.right_traversals_,
+ "early_terminations", data.early_terminations_);
+#endif
+}
+
+
+template<typename BuildString>
+void TestStringCharacterStream(BuildString build, int test_cases) {
InitializeVM();
Isolate* isolate = Isolate::Current();
HandleScope outer_scope(isolate);
ZoneScope zone(Isolate::Current()->runtime_zone(), DELETE_ON_EXIT);
- ConsStringGenerationData data;
- for (int i = 0; i < kCharacterStreamEdgeCases; i++) {
+ ConsStringGenerationData data(true);
+ bool last_test_did_gc = false;
+ for (int i = 0; i < test_cases; i++) {
printf("%d\n", i);
- isolate->heap()->CollectAllGarbage(
- Heap::kNoGCFlags, "must not allocate in loop");
- AlwaysAllocateScope always_allocate;
HandleScope inner_scope(isolate);
- Handle<String> cons_string = BuildConsStrings(i, &data);
- Handle<String> flat_string = BuildConsStrings(i, &data);
+ // Build flat version of cons string.
+ Handle<String> flat_string = build(i, &data);
+ ConsStringStats flat_string_stats;
+ AccumulateStats(flat_string, &flat_string_stats);
+ // Flatten string.
FlattenString(flat_string);
+ // Build unflattened version of cons string to test.
+ Handle<String> cons_string = build(i, &data);
+ ConsStringStats cons_string_stats;
+ AccumulateStats(cons_string, &cons_string_stats);
+ // Check if gc changed our data structure.
+ bool broken_by_gc =
+ cons_string_stats.leaves_ != data.stats_.leaves_ ||
+ cons_string_stats.leaves_ != flat_string_stats.leaves_;
+ // If gc altered the data structure, do a full collection and retry
test.
+ if (broken_by_gc) {
+ // Bail if test runs twice.
+ if (last_test_did_gc) CHECK(false);
+ printf("forcing gc\n");
+ isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags, "retry test");
+ // Retry test.
+ last_test_did_gc = true;
+ i--;
+ continue;
+ }
+ last_test_did_gc = false;
AssertNoAllocation no_alloc;
- CHECK(flat_string->IsConsString() && flat_string->IsFlat());
- VerifyCharacterStream(ConsString::cast(*flat_string)->first(),
- *cons_string);
+ PrintStats(data);
+ // Full verify of cons string.
+ cons_string_stats.VerifyEqual(flat_string_stats);
+ cons_string_stats.VerifyEqual(data.stats_);
+ VerifyConsString(cons_string, &data);
+ String* flat_string_ptr =
+ flat_string->IsConsString() ?
+ ConsString::cast(*flat_string)->first() :
+ *flat_string;
+ VerifyCharacterStream(flat_string_ptr, *cons_string);
}
}
+
+
+static const int kCharacterStreamNonRandomCases = 8;
+
+
+static Handle<String> BuildEdgeCaseConsString(
+ int test_case, ConsStringGenerationData* data) {
+ data->Reset();
+ switch (test_case) {
+ case 0:
+ return ConstructBalanced(data, 71);
+ case 1:
+ return ConstructLeft(data, 71);
+ case 2:
+ return ConstructRight(data, 71);
+ case 3:
+ return ConstructLeft(data, 10);
+ case 4:
+ return ConstructRight(data, 10);
+ case 5:
+ // 2 element balanced tree.
+ data->stats_.chars_ += data->block(0)->length();
+ data->stats_.chars_ += data->block(1)->length();
+ data->stats_.leaves_ += 2;
+ return FACTORY->NewConsString(data->block(0), data->block(1));
+ case 6:
+ // Simple flattened tree.
+ data->stats_.chars_ += data->block(0)->length();
+ data->stats_.chars_ += data->block(1)->length();
+ data->stats_.leaves_ += 2;
+ data->stats_.empty_leaves_ += 1;
+ {
+ Handle<String> string =
+ FACTORY->NewConsString(data->block(0), data->block(1));
+ FlattenString(string);
+ return string;
+ }
+ case 7:
+ // Left node flattened.
+ data->stats_.chars_ += data->block(0)->length();
+ data->stats_.chars_ += data->block(1)->length();
+ data->stats_.chars_ += data->block(2)->length();
+ data->stats_.leaves_ += 3;
+ data->stats_.empty_leaves_ += 1;
+ data->stats_.left_traversals_ += 1;
+ {
+ Handle<String> left =
+ FACTORY->NewConsString(data->block(0), data->block(1));
+ FlattenString(left);
+ return FACTORY->NewConsString(left, data->block(2));
+ }
+ case 8:
+ // Left node and right node flattened.
+ data->stats_.chars_ += data->block(0)->length();
+ data->stats_.chars_ += data->block(1)->length();
+ data->stats_.chars_ += data->block(2)->length();
+ data->stats_.chars_ += data->block(3)->length();
+ data->stats_.leaves_ += 4;
+ data->stats_.empty_leaves_ += 2;
+ data->stats_.left_traversals_ += 1;
+ data->stats_.right_traversals_ += 1;
+ {
+ Handle<String> left =
+ FACTORY->NewConsString(data->block(0), data->block(1));
+ FlattenString(left);
+ Handle<String> right =
+ FACTORY->NewConsString(data->block(2), data->block(2));
+ FlattenString(right);
+ return FACTORY->NewConsString(left, right);
+ }
+ }
+ UNREACHABLE();
+ return Handle<String>();
+}
+
+
+TEST(StringCharacterStreamEdgeCases) {
+ printf("TestStringCharacterStreamEdgeCases\n");
+ TestStringCharacterStream(
+ BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
+}
+
+
+static const int kBalances = 3;
+static const int kTreeLengths = 4;
+static const int kEmptyLeaves = 4;
+static const int kUniqueRandomParameters =
+ kBalances*kTreeLengths*kEmptyLeaves;
+
+
+static void InitializeGenerationData(
+ int test_case, ConsStringGenerationData* data) {
+ // Clear the settings and reinit the rng.
+ data->Reset();
+ // Spin up the rng to a known location that is unique per test.
+ static const int kPerTestJump = 501;
+ for (int j = 0; j < test_case*kPerTestJump; j++) {
+ data->rng_.next();
+ }
+ // Choose balanced, left or right heavy trees.
+ switch (test_case % kBalances) {
+ case 0:
+ // Nothing to do. Already balanced.
+ break;
+ case 1:
+ // Left balanced.
+ data->leftness_ = 0.90;
+ data->rightness_ = 0.15;
+ break;
+ case 2:
+ // Right balanced.
+ data->leftness_ = 0.15;
+ data->rightness_ = 0.90;
+ break;
+ default:
+ UNREACHABLE();
+ break;
+ }
+ // Must remove the influence of the above decision.
+ test_case /= kBalances;
+ // Choose tree length.
+ switch (test_case % kTreeLengths) {
+ case 0:
+ data->max_leaves_ = 16;
+ data->early_termination_threshold_ = 0.2;
+ break;
+ case 1:
+ data->max_leaves_ = 50;
+ data->early_termination_threshold_ = 0.05;
+ break;
+ case 2:
+ data->max_leaves_ = 500;
+ data->early_termination_threshold_ = 0.03;
+ break;
+ case 3:
+ data->max_leaves_ = 5000;
+ data->early_termination_threshold_ = 0.001;
+ break;
+ default:
+ UNREACHABLE();
+ break;
+ }
+ // Must remove the influence of the above decision.
+ test_case /= kTreeLengths;
+ // Choose how much we allow empty nodes, including not at all.
+ data->empty_leaf_threshold_ =
+ 0.03 * static_cast<double>(test_case % kEmptyLeaves);
+}
+
+
+static Handle<String> BuildRandomConsString(
+ int test_case, ConsStringGenerationData* data) {
+ InitializeGenerationData(test_case, data);
+ return ConstructRandomString(data, 200);
+}
+
+
+TEST(StringCharacterStreamRandom) {
+ printf("StringCharacterStreamRandom\n");
+ TestStringCharacterStream(BuildRandomConsString,
kUniqueRandomParameters*7);
+}
static const int DEEP_ASCII_DEPTH = 100000;
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
