| OLD | NEW |
| 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 896 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 907 visitor->Visit##Type(this); \ | 907 visitor->Visit##Type(this); \ |
| 908 } | 908 } |
| 909 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT) | 909 FOR_EACH_NODE_TYPE(DEFINE_ACCEPT) |
| 910 #undef DEFINE_ACCEPT | 910 #undef DEFINE_ACCEPT |
| 911 | 911 |
| 912 | 912 |
| 913 // ------------------------------------------------------------------- | 913 // ------------------------------------------------------------------- |
| 914 // Dot/dotty output | 914 // Dot/dotty output |
| 915 | 915 |
| 916 | 916 |
| 917 #ifdef DEBUG |
| 918 |
| 919 |
| 917 class DotPrinter: public NodeVisitor { | 920 class DotPrinter: public NodeVisitor { |
| 918 public: | 921 public: |
| 919 DotPrinter() : stream_(&alloc_) { } | 922 DotPrinter() : stream_(&alloc_) { } |
| 920 void PrintNode(const char* label, RegExpNode* node); | 923 void PrintNode(const char* label, RegExpNode* node); |
| 921 void Visit(RegExpNode* node); | 924 void Visit(RegExpNode* node); |
| 922 void PrintOnFailure(RegExpNode* from, RegExpNode* on_failure); | 925 void PrintOnFailure(RegExpNode* from, RegExpNode* on_failure); |
| 923 StringStream* stream() { return &stream_; } | 926 StringStream* stream() { return &stream_; } |
| 924 #define DECLARE_VISIT(Type) \ | 927 #define DECLARE_VISIT(Type) \ |
| 925 virtual void Visit##Type(Type##Node* that); | 928 virtual void Visit##Type(Type##Node* that); |
| 926 FOR_EACH_NODE_TYPE(DECLARE_VISIT) | 929 FOR_EACH_NODE_TYPE(DECLARE_VISIT) |
| (...skipping 28 matching lines...) Expand all Loading... |
| 955 | 958 |
| 956 | 959 |
| 957 void DotPrinter::Visit(RegExpNode* node) { | 960 void DotPrinter::Visit(RegExpNode* node) { |
| 958 if (seen_.find(node) != seen_.end()) | 961 if (seen_.find(node) != seen_.end()) |
| 959 return; | 962 return; |
| 960 seen_.insert(node); | 963 seen_.insert(node); |
| 961 node->Accept(this); | 964 node->Accept(this); |
| 962 } | 965 } |
| 963 | 966 |
| 964 | 967 |
| 965 #ifdef DEBUG | |
| 966 | |
| 967 | |
| 968 void DotPrinter::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) { | 968 void DotPrinter::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) { |
| 969 if (on_failure == EndNode::GetBacktrack()) return; | 969 if (on_failure == EndNode::GetBacktrack()) return; |
| 970 stream()->Add(" n%p -> n%p [style=dotted];\n", from, on_failure); | 970 stream()->Add(" n%p -> n%p [style=dotted];\n", from, on_failure); |
| 971 Visit(on_failure); | 971 Visit(on_failure); |
| 972 } | 972 } |
| 973 | 973 |
| 974 | 974 |
| 975 void DotPrinter::VisitChoice(ChoiceNode* that) { | 975 void DotPrinter::VisitChoice(ChoiceNode* that) { |
| 976 stream()->Add(" n%p [label=\"? (%p)\"];\n", that, that); | 976 stream()->Add(" n%p [label=\"? (%p)\"];\n", that, that); |
| 977 PrintOnFailure(that, that->on_failure()); | 977 PrintOnFailure(that, that->on_failure()); |
| (...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1068 case ActionNode::END_SUBMATCH: | 1068 case ActionNode::END_SUBMATCH: |
| 1069 stream()->Add("label=\"end\", shape=septagon"); | 1069 stream()->Add("label=\"end\", shape=septagon"); |
| 1070 break; | 1070 break; |
| 1071 } | 1071 } |
| 1072 stream()->Add("];\n"); | 1072 stream()->Add("];\n"); |
| 1073 stream()->Add(" n%p -> n%p;\n", that, that->on_success()); | 1073 stream()->Add(" n%p -> n%p;\n", that, that->on_success()); |
| 1074 Visit(that->on_success()); | 1074 Visit(that->on_success()); |
| 1075 } | 1075 } |
| 1076 | 1076 |
| 1077 | 1077 |
| 1078 class DispatchTableDumper { |
| 1079 public: |
| 1080 DispatchTableDumper(StringStream* stream) : stream_(stream) { } |
| 1081 void Call(uc16 key, DispatchTable::Entry entry); |
| 1082 StringStream* stream() { return stream_; } |
| 1083 private: |
| 1084 StringStream* stream_; |
| 1085 }; |
| 1086 |
| 1087 |
| 1088 void DispatchTableDumper::Call(uc16 key, DispatchTable::Entry entry) { |
| 1089 stream()->Add("[%k-%k]: {", key, entry.to()); |
| 1090 OutSet set = entry.out_set(); |
| 1091 bool first = true; |
| 1092 for (unsigned i = 0; i < OutSet::kFirstLimit; i++) { |
| 1093 if (set.Get(i)) { |
| 1094 if (first) first = false; |
| 1095 else stream()->Add(", "); |
| 1096 stream()->Add("%i", i); |
| 1097 } |
| 1098 } |
| 1099 stream()->Add("}\n"); |
| 1100 } |
| 1101 |
| 1102 |
| 1103 void DispatchTable::Dump() { |
| 1104 HeapStringAllocator alloc; |
| 1105 StringStream stream(&alloc); |
| 1106 tree()->ForEach(DispatchTableDumper(&stream)); |
| 1107 OS::PrintError("%s", *stream.ToCString()); |
| 1108 } |
| 1109 |
| 1110 |
| 1111 void RegExpEngine::DotPrint(const char* label, RegExpNode* node) { |
| 1112 DotPrinter printer; |
| 1113 printer.PrintNode(label, node); |
| 1114 } |
| 1115 |
| 1116 |
| 1078 #endif // DEBUG | 1117 #endif // DEBUG |
| 1079 | 1118 |
| 1080 | 1119 |
| 1081 // ------------------------------------------------------------------- | 1120 // ------------------------------------------------------------------- |
| 1082 // Tree to graph conversion | 1121 // Tree to graph conversion |
| 1083 | 1122 |
| 1084 | 1123 |
| 1085 RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler, | 1124 RegExpNode* RegExpAtom::ToNode(RegExpCompiler* compiler, |
| 1086 RegExpNode* on_success, | 1125 RegExpNode* on_success, |
| 1087 RegExpNode* on_failure) { | 1126 RegExpNode* on_failure) { |
| (...skipping 356 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1444 // There is no overlap so we can just add the range | 1483 // There is no overlap so we can just add the range |
| 1445 ZoneSplayTree<Config>::Locator ins; | 1484 ZoneSplayTree<Config>::Locator ins; |
| 1446 ASSERT_RESULT(tree()->Insert(current.from(), &ins)); | 1485 ASSERT_RESULT(tree()->Insert(current.from(), &ins)); |
| 1447 ins.set_value(Entry(current.from(), current.to(), value)); | 1486 ins.set_value(Entry(current.from(), current.to(), value)); |
| 1448 break; | 1487 break; |
| 1449 } | 1488 } |
| 1450 } | 1489 } |
| 1451 } | 1490 } |
| 1452 | 1491 |
| 1453 | 1492 |
| 1454 #ifdef DEBUG | |
| 1455 | |
| 1456 | |
| 1457 class DispatchTableDumper { | |
| 1458 public: | |
| 1459 DispatchTableDumper(StringStream* stream) : stream_(stream) { } | |
| 1460 void Call(uc16 key, DispatchTable::Entry entry); | |
| 1461 StringStream* stream() { return stream_; } | |
| 1462 private: | |
| 1463 StringStream* stream_; | |
| 1464 }; | |
| 1465 | |
| 1466 | |
| 1467 void DispatchTableDumper::Call(uc16 key, DispatchTable::Entry entry) { | |
| 1468 stream()->Add("[%k-%k]: {", key, entry.to()); | |
| 1469 OutSet set = entry.out_set(); | |
| 1470 bool first = true; | |
| 1471 for (unsigned i = 0; i < OutSet::kFirstLimit; i++) { | |
| 1472 if (set.Get(i)) { | |
| 1473 if (first) first = false; | |
| 1474 else stream()->Add(", "); | |
| 1475 stream()->Add("%i", i); | |
| 1476 } | |
| 1477 } | |
| 1478 stream()->Add("}\n"); | |
| 1479 } | |
| 1480 | |
| 1481 | |
| 1482 void DispatchTable::Dump() { | |
| 1483 HeapStringAllocator alloc; | |
| 1484 StringStream stream(&alloc); | |
| 1485 tree()->ForEach(DispatchTableDumper(&stream)); | |
| 1486 OS::PrintError("%s", *stream.ToCString()); | |
| 1487 } | |
| 1488 | |
| 1489 | |
| 1490 #endif | |
| 1491 | |
| 1492 | |
| 1493 OutSet DispatchTable::Get(uc16 value) { | 1493 OutSet DispatchTable::Get(uc16 value) { |
| 1494 ZoneSplayTree<Config>::Locator loc; | 1494 ZoneSplayTree<Config>::Locator loc; |
| 1495 if (!tree()->FindGreatestLessThan(value, &loc)) | 1495 if (!tree()->FindGreatestLessThan(value, &loc)) |
| 1496 return OutSet::empty(); | 1496 return OutSet::empty(); |
| 1497 Entry* entry = &loc.value(); | 1497 Entry* entry = &loc.value(); |
| 1498 if (value <= entry->to()) | 1498 if (value <= entry->to()) |
| 1499 return entry->out_set(); | 1499 return entry->out_set(); |
| 1500 else | 1500 else |
| 1501 return OutSet::empty(); | 1501 return OutSet::empty(); |
| 1502 } | 1502 } |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1598 RegExpNode* RegExpCompiler::Compile(RegExpTree* tree, | 1598 RegExpNode* RegExpCompiler::Compile(RegExpTree* tree, |
| 1599 RegExpNode* on_success, | 1599 RegExpNode* on_success, |
| 1600 RegExpNode* on_failure) { | 1600 RegExpNode* on_failure) { |
| 1601 RegExpNode* node = tree->ToNode(this, on_success, on_failure); | 1601 RegExpNode* node = tree->ToNode(this, on_success, on_failure); |
| 1602 Analysis analysis(this); | 1602 Analysis analysis(this); |
| 1603 analysis.Analyze(node); | 1603 analysis.Analyze(node); |
| 1604 return node; | 1604 return node; |
| 1605 } | 1605 } |
| 1606 | 1606 |
| 1607 | 1607 |
| 1608 void RegExpEngine::DotPrint(const char* label, RegExpNode* node) { | |
| 1609 DotPrinter printer; | |
| 1610 printer.PrintNode(label, node); | |
| 1611 } | |
| 1612 | |
| 1613 | |
| 1614 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) { | 1608 RegExpNode* RegExpEngine::Compile(RegExpParseResult* input) { |
| 1615 RegExpCompiler compiler(input->capture_count); | 1609 RegExpCompiler compiler(input->capture_count); |
| 1616 RegExpNode* node = compiler.Compile(input->tree, | 1610 RegExpNode* node = compiler.Compile(input->tree, |
| 1617 EndNode::GetAccept(), | 1611 EndNode::GetAccept(), |
| 1618 EndNode::GetBacktrack()); | 1612 EndNode::GetBacktrack()); |
| 1619 return node; | 1613 return node; |
| 1620 } | 1614 } |
| 1621 | 1615 |
| 1622 | 1616 |
| 1623 }} // namespace v8::internal | 1617 }} // namespace v8::internal |
| OLD | NEW |