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
11namespace v8 {
12namespace internal {
13
14// -------------------------------------------------------------------
15// Dot/dotty output
16
17class DotPrinterImpl : public NodeVisitor {
18 public:
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
31void 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
51void DotPrinterImpl::Visit(RegExpNode* node) {
52  if (node->info()->visited) return;
53  node->info()->visited = true;
54  node->Accept(this);
55}
56
57void DotPrinterImpl::PrintOnFailure(RegExpNode* from, RegExpNode* on_failure) {
58  os_ << "  n" << from << " -> n" << on_failure << " [style=dotted];\n";
59  Visit(on_failure);
60}
61
62class AttributePrinter {
63 public:
64  explicit AttributePrinter(std::ostream& os) : os_(os), first_(true) {}
65  void PrintSeparator() {
66    if (first_) {
67      first_ = false;
68    } else {
69      os_ << "|";
70    }
71  }
72  void PrintBit(const char* name, bool value) {
73    if (!value) return;
74    PrintSeparator();
75    os_ << "{" << name << "}";
76  }
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
88void 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
103void 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
115void DotPrinterImpl::VisitLoopChoice(LoopChoiceNode* that) {
116  VisitChoice(that);
117}
118
119void DotPrinterImpl::VisitNegativeLookaroundChoice(
120    NegativeLookaroundChoiceNode* that) {
121  VisitChoice(that);
122}
123
124void 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
159void 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
167void DotPrinterImpl::VisitEnd(EndNode* that) {
168  os_ << "  n" << that << " [style=bold, shape=point];\n";
169  PrintAttributes(that);
170}
171
172void 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
198void 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
244void 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