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