1 // Copyright 2019 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/regexp/regexp-dotprinter.h"
6
7 #include "src/regexp/regexp-compiler.h"
8 #include "src/utils/ostreams.h"
9
10 namespace v8 {
11 namespace internal {
12
13 // -------------------------------------------------------------------
14 // Dot/dotty output
15
16 #ifdef DEBUG
17
18 class DotPrinterImpl : public NodeVisitor {
19 public:
DotPrinterImpl(std::ostream & os)20 explicit DotPrinterImpl(std::ostream& os) : os_(os) {}
21 void PrintNode(const char* label, RegExpNode* node);
22 void Visit(RegExpNode* node);
23 void PrintAttributes(RegExpNode* from);
24 void PrintOnFailure(RegExpNode* from, RegExpNode* to);
25 #define DECLARE_VISIT(Type) virtual void Visit##Type(Type##Node* that);
26 FOR_EACH_NODE_TYPE(DECLARE_VISIT)
27 #undef DECLARE_VISIT
28 private:
29 std::ostream& os_;
30 };
31
PrintNode(const char * label,RegExpNode * node)32 void DotPrinterImpl::PrintNode(const char* label, RegExpNode* node) {
33 os_ << "digraph G {\n graph [label=\"";
34 for (int i = 0; label[i]; i++) {
35 switch (label[i]) {
36 case '\\':
37 os_ << "\\\\";
38 break;
39 case '"':
40 os_ << "\"";
41 break;
42 default:
43 os_ << label[i];
44 break;
45 }
46 }
47 os_ << "\"];\n";
48 Visit(node);
49 os_ << "}" << std::endl;
50 }
51
Visit(RegExpNode * node)52 void DotPrinterImpl::Visit(RegExpNode* node) {
53 if (node->info()->visited) return;
54 node->info()->visited = true;
55 node->Accept(this);
56 }
57
PrintOnFailure(RegExpNode * from,RegExpNode * on_failure)58 void DotPrinterImpl::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) {
59 os_ << " n" << from << " -> n" << on_failure << " [style=dotted];\n";
60 Visit(on_failure);
61 }
62
63 class AttributePrinter {
64 public:
AttributePrinter(std::ostream & os)65 explicit AttributePrinter(std::ostream& os) // NOLINT
66 : os_(os), first_(true) {}
PrintSeparator()67 void PrintSeparator() {
68 if (first_) {
69 first_ = false;
70 } else {
71 os_ << "|";
72 }
73 }
PrintBit(const char * name,bool value)74 void PrintBit(const char* name, bool value) {
75 if (!value) return;
76 PrintSeparator();
77 os_ << "{" << name << "}";
78 }
PrintPositive(const char * name,int value)79 void PrintPositive(const char* name, int value) {
80 if (value < 0) return;
81 PrintSeparator();
82 os_ << "{" << name << "|" << value << "}";
83 }
84
85 private:
86 std::ostream& os_;
87 bool first_;
88 };
89
PrintAttributes(RegExpNode * that)90 void DotPrinterImpl::PrintAttributes(RegExpNode* that) {
91 os_ << " a" << that << " [shape=Mrecord, color=grey, fontcolor=grey, "
92 << "margin=0.1, fontsize=10, label=\"{";
93 AttributePrinter printer(os_);
94 NodeInfo* info = that->info();
95 printer.PrintBit("NI", info->follows_newline_interest);
96 printer.PrintBit("WI", info->follows_word_interest);
97 printer.PrintBit("SI", info->follows_start_interest);
98 Label* label = that->label();
99 if (label->is_bound()) printer.PrintPositive("@", label->pos());
100 os_ << "}\"];\n"
101 << " a" << that << " -> n" << that
102 << " [style=dashed, color=grey, arrowhead=none];\n";
103 }
104
VisitChoice(ChoiceNode * that)105 void DotPrinterImpl::VisitChoice(ChoiceNode* that) {
106 os_ << " n" << that << " [shape=Mrecord, label=\"?\"];\n";
107 for (int i = 0; i < that->alternatives()->length(); i++) {
108 GuardedAlternative alt = that->alternatives()->at(i);
109 os_ << " n" << that << " -> n" << alt.node();
110 }
111 for (int i = 0; i < that->alternatives()->length(); i++) {
112 GuardedAlternative alt = that->alternatives()->at(i);
113 alt.node()->Accept(this);
114 }
115 }
116
VisitLoopChoice(LoopChoiceNode * that)117 void DotPrinterImpl::VisitLoopChoice(LoopChoiceNode* that) {
118 VisitChoice(that);
119 }
120
VisitNegativeLookaroundChoice(NegativeLookaroundChoiceNode * that)121 void DotPrinterImpl::VisitNegativeLookaroundChoice(
122 NegativeLookaroundChoiceNode* that) {
123 VisitChoice(that);
124 }
125
VisitText(TextNode * that)126 void DotPrinterImpl::VisitText(TextNode* that) {
127 Zone* zone = that->zone();
128 os_ << " n" << that << " [label=\"";
129 for (int i = 0; i < that->elements()->length(); i++) {
130 if (i > 0) os_ << " ";
131 TextElement elm = that->elements()->at(i);
132 switch (elm.text_type()) {
133 case TextElement::ATOM: {
134 Vector<const uc16> data = elm.atom()->data();
135 for (int i = 0; i < data.length(); i++) {
136 os_ << static_cast<char>(data[i]);
137 }
138 break;
139 }
140 case TextElement::CHAR_CLASS: {
141 RegExpCharacterClass* node = elm.char_class();
142 os_ << "[";
143 if (node->is_negated()) os_ << "^";
144 for (int j = 0; j < node->ranges(zone)->length(); j++) {
145 CharacterRange range = node->ranges(zone)->at(j);
146 os_ << AsUC32(range.from()) << "-" << AsUC32(range.to());
147 }
148 os_ << "]";
149 break;
150 }
151 default:
152 UNREACHABLE();
153 }
154 }
155 os_ << "\", shape=box, peripheries=2];\n";
156 PrintAttributes(that);
157 os_ << " n" << that << " -> n" << that->on_success() << ";\n";
158 Visit(that->on_success());
159 }
160
VisitBackReference(BackReferenceNode * that)161 void DotPrinterImpl::VisitBackReference(BackReferenceNode* that) {
162 os_ << " n" << that << " [label=\"$" << that->start_register() << "..$"
163 << that->end_register() << "\", shape=doubleoctagon];\n";
164 PrintAttributes(that);
165 os_ << " n" << that << " -> n" << that->on_success() << ";\n";
166 Visit(that->on_success());
167 }
168
VisitEnd(EndNode * that)169 void DotPrinterImpl::VisitEnd(EndNode* that) {
170 os_ << " n" << that << " [style=bold, shape=point];\n";
171 PrintAttributes(that);
172 }
173
VisitAssertion(AssertionNode * that)174 void DotPrinterImpl::VisitAssertion(AssertionNode* that) {
175 os_ << " n" << that << " [";
176 switch (that->assertion_type()) {
177 case AssertionNode::AT_END:
178 os_ << "label=\"$\", shape=septagon";
179 break;
180 case AssertionNode::AT_START:
181 os_ << "label=\"^\", shape=septagon";
182 break;
183 case AssertionNode::AT_BOUNDARY:
184 os_ << "label=\"\\b\", shape=septagon";
185 break;
186 case AssertionNode::AT_NON_BOUNDARY:
187 os_ << "label=\"\\B\", shape=septagon";
188 break;
189 case AssertionNode::AFTER_NEWLINE:
190 os_ << "label=\"(?<=\\n)\", shape=septagon";
191 break;
192 }
193 os_ << "];\n";
194 PrintAttributes(that);
195 RegExpNode* successor = that->on_success();
196 os_ << " n" << that << " -> n" << successor << ";\n";
197 Visit(successor);
198 }
199
VisitAction(ActionNode * that)200 void DotPrinterImpl::VisitAction(ActionNode* that) {
201 os_ << " n" << that << " [";
202 switch (that->action_type_) {
203 case ActionNode::SET_REGISTER_FOR_LOOP:
204 os_ << "label=\"$" << that->data_.u_store_register.reg
205 << ":=" << that->data_.u_store_register.value << "\", shape=octagon";
206 break;
207 case ActionNode::INCREMENT_REGISTER:
208 os_ << "label=\"$" << that->data_.u_increment_register.reg
209 << "++\", shape=octagon";
210 break;
211 case ActionNode::STORE_POSITION:
212 os_ << "label=\"$" << that->data_.u_position_register.reg
213 << ":=$pos\", shape=octagon";
214 break;
215 case ActionNode::BEGIN_SUBMATCH:
216 os_ << "label=\"$" << that->data_.u_submatch.current_position_register
217 << ":=$pos,begin\", shape=septagon";
218 break;
219 case ActionNode::POSITIVE_SUBMATCH_SUCCESS:
220 os_ << "label=\"escape\", shape=septagon";
221 break;
222 case ActionNode::EMPTY_MATCH_CHECK:
223 os_ << "label=\"$" << that->data_.u_empty_match_check.start_register
224 << "=$pos?,$" << that->data_.u_empty_match_check.repetition_register
225 << "<" << that->data_.u_empty_match_check.repetition_limit
226 << "?\", shape=septagon";
227 break;
228 case ActionNode::CLEAR_CAPTURES: {
229 os_ << "label=\"clear $" << that->data_.u_clear_captures.range_from
230 << " to $" << that->data_.u_clear_captures.range_to
231 << "\", shape=septagon";
232 break;
233 }
234 }
235 os_ << "];\n";
236 PrintAttributes(that);
237 RegExpNode* successor = that->on_success();
238 os_ << " n" << that << " -> n" << successor << ";\n";
239 Visit(successor);
240 }
241
242 #endif // DEBUG
243
DotPrint(const char * label,RegExpNode * node)244 void DotPrinter::DotPrint(const char* label, RegExpNode* node) {
245 #ifdef DEBUG
246 StdoutStream os;
247 DotPrinterImpl printer(os);
248 printer.PrintNode(label, node);
249 #endif // DEBUG
250 }
251
252 } // namespace internal
253 } // namespace v8
254