1 //===- AST.cpp - Helper for printing out the Toy AST ----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the AST dump for the Toy language.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "toy/AST.h"
14 
15 #include "llvm/ADT/Twine.h"
16 #include "llvm/ADT/TypeSwitch.h"
17 #include "llvm/Support/raw_ostream.h"
18 
19 using namespace toy;
20 
21 namespace {
22 
23 // RAII helper to manage increasing/decreasing the indentation as we traverse
24 // the AST
25 struct Indent {
26   Indent(int &level) : level(level) { ++level; }
27   ~Indent() { --level; }
28   int &level;
29 };
30 
31 /// Helper class that implement the AST tree traversal and print the nodes along
32 /// the way. The only data member is the current indentation level.
33 class ASTDumper {
34 public:
35   void dump(ModuleAST *node);
36 
37 private:
38   void dump(const VarType &type);
39   void dump(VarDeclExprAST *varDecl);
40   void dump(ExprAST *expr);
41   void dump(ExprASTList *exprList);
42   void dump(NumberExprAST *num);
43   void dump(LiteralExprAST *node);
44   void dump(StructLiteralExprAST *node);
45   void dump(VariableExprAST *node);
46   void dump(ReturnExprAST *node);
47   void dump(BinaryExprAST *node);
48   void dump(CallExprAST *node);
49   void dump(PrintExprAST *node);
50   void dump(PrototypeAST *node);
51   void dump(FunctionAST *node);
52   void dump(StructAST *node);
53 
54   // Actually print spaces matching the current indentation level
55   void indent() {
56     for (int i = 0; i < curIndent; i++)
57       llvm::errs() << "  ";
58   }
59   int curIndent = 0;
60 };
61 
62 } // namespace
63 
64 /// Return a formatted string for the location of any node
65 template <typename T>
66 static std::string loc(T *node) {
67   const auto &loc = node->loc();
68   return (llvm::Twine("@") + *loc.file + ":" + llvm::Twine(loc.line) + ":" +
69           llvm::Twine(loc.col))
70       .str();
71 }
72 
73 // Helper Macro to bump the indentation level and print the leading spaces for
74 // the current indentations
75 #define INDENT()                                                               \
76   Indent level_(curIndent);                                                    \
77   indent();
78 
79 /// Dispatch to a generic expressions to the appropriate subclass using RTTI
80 void ASTDumper::dump(ExprAST *expr) {
81   llvm::TypeSwitch<ExprAST *>(expr)
82       .Case<BinaryExprAST, CallExprAST, LiteralExprAST, NumberExprAST,
83             PrintExprAST, ReturnExprAST, StructLiteralExprAST, VarDeclExprAST,
84             VariableExprAST>([&](auto *node) { this->dump(node); })
85       .Default([&](ExprAST *) {
86         // No match, fallback to a generic message
87         INDENT();
88         llvm::errs() << "<unknown Expr, kind " << expr->getKind() << ">\n";
89       });
90 }
91 
92 /// A variable declaration is printing the variable name, the type, and then
93 /// recurse in the initializer value.
94 void ASTDumper::dump(VarDeclExprAST *varDecl) {
95   INDENT();
96   llvm::errs() << "VarDecl " << varDecl->getName();
97   dump(varDecl->getType());
98   llvm::errs() << " " << loc(varDecl) << "\n";
99   if (auto *initVal = varDecl->getInitVal())
100     dump(initVal);
101 }
102 
103 /// A "block", or a list of expression
104 void ASTDumper::dump(ExprASTList *exprList) {
105   INDENT();
106   llvm::errs() << "Block {\n";
107   for (auto &expr : *exprList)
108     dump(expr.get());
109   indent();
110   llvm::errs() << "} // Block\n";
111 }
112 
113 /// A literal number, just print the value.
114 void ASTDumper::dump(NumberExprAST *num) {
115   INDENT();
116   llvm::errs() << num->getValue() << " " << loc(num) << "\n";
117 }
118 
119 /// Helper to print recursively a literal. This handles nested array like:
120 ///    [ [ 1, 2 ], [ 3, 4 ] ]
121 /// We print out such array with the dimensions spelled out at every level:
122 ///    <2,2>[<2>[ 1, 2 ], <2>[ 3, 4 ] ]
123 void printLitHelper(ExprAST *litOrNum) {
124   // Inside a literal expression we can have either a number or another literal
125   if (auto *num = llvm::dyn_cast<NumberExprAST>(litOrNum)) {
126     llvm::errs() << num->getValue();
127     return;
128   }
129   auto *literal = llvm::cast<LiteralExprAST>(litOrNum);
130 
131   // Print the dimension for this literal first
132   llvm::errs() << "<";
133   llvm::interleaveComma(literal->getDims(), llvm::errs());
134   llvm::errs() << ">";
135 
136   // Now print the content, recursing on every element of the list
137   llvm::errs() << "[ ";
138   llvm::interleaveComma(literal->getValues(), llvm::errs(),
139                         [&](auto &elt) { printLitHelper(elt.get()); });
140   llvm::errs() << "]";
141 }
142 
143 /// Print a literal, see the recursive helper above for the implementation.
144 void ASTDumper::dump(LiteralExprAST *node) {
145   INDENT();
146   llvm::errs() << "Literal: ";
147   printLitHelper(node);
148   llvm::errs() << " " << loc(node) << "\n";
149 }
150 
151 /// Print a struct literal.
152 void ASTDumper::dump(StructLiteralExprAST *node) {
153   INDENT();
154   llvm::errs() << "Struct Literal: ";
155   for (auto &value : node->getValues())
156     dump(value.get());
157   indent();
158   llvm::errs() << " " << loc(node) << "\n";
159 }
160 
161 /// Print a variable reference (just a name).
162 void ASTDumper::dump(VariableExprAST *node) {
163   INDENT();
164   llvm::errs() << "var: " << node->getName() << " " << loc(node) << "\n";
165 }
166 
167 /// Return statement print the return and its (optional) argument.
168 void ASTDumper::dump(ReturnExprAST *node) {
169   INDENT();
170   llvm::errs() << "Return\n";
171   if (node->getExpr().hasValue())
172     return dump(*node->getExpr());
173   {
174     INDENT();
175     llvm::errs() << "(void)\n";
176   }
177 }
178 
179 /// Print a binary operation, first the operator, then recurse into LHS and RHS.
180 void ASTDumper::dump(BinaryExprAST *node) {
181   INDENT();
182   llvm::errs() << "BinOp: " << node->getOp() << " " << loc(node) << "\n";
183   dump(node->getLHS());
184   dump(node->getRHS());
185 }
186 
187 /// Print a call expression, first the callee name and the list of args by
188 /// recursing into each individual argument.
189 void ASTDumper::dump(CallExprAST *node) {
190   INDENT();
191   llvm::errs() << "Call '" << node->getCallee() << "' [ " << loc(node) << "\n";
192   for (auto &arg : node->getArgs())
193     dump(arg.get());
194   indent();
195   llvm::errs() << "]\n";
196 }
197 
198 /// Print a builtin print call, first the builtin name and then the argument.
199 void ASTDumper::dump(PrintExprAST *node) {
200   INDENT();
201   llvm::errs() << "Print [ " << loc(node) << "\n";
202   dump(node->getArg());
203   indent();
204   llvm::errs() << "]\n";
205 }
206 
207 /// Print type: only the shape is printed in between '<' and '>'
208 void ASTDumper::dump(const VarType &type) {
209   llvm::errs() << "<";
210   if (!type.name.empty())
211     llvm::errs() << type.name;
212   else
213     llvm::interleaveComma(type.shape, llvm::errs());
214   llvm::errs() << ">";
215 }
216 
217 /// Print a function prototype, first the function name, and then the list of
218 /// parameters names.
219 void ASTDumper::dump(PrototypeAST *node) {
220   INDENT();
221   llvm::errs() << "Proto '" << node->getName() << "' " << loc(node) << "\n";
222   indent();
223   llvm::errs() << "Params: [";
224   llvm::interleaveComma(node->getArgs(), llvm::errs(),
225                         [](auto &arg) { llvm::errs() << arg->getName(); });
226   llvm::errs() << "]\n";
227 }
228 
229 /// Print a function, first the prototype and then the body.
230 void ASTDumper::dump(FunctionAST *node) {
231   INDENT();
232   llvm::errs() << "Function \n";
233   dump(node->getProto());
234   dump(node->getBody());
235 }
236 
237 /// Print a struct.
238 void ASTDumper::dump(StructAST *node) {
239   INDENT();
240   llvm::errs() << "Struct: " << node->getName() << " " << loc(node) << "\n";
241 
242   {
243     INDENT();
244     llvm::errs() << "Variables: [\n";
245     for (auto &variable : node->getVariables())
246       dump(variable.get());
247     indent();
248     llvm::errs() << "]\n";
249   }
250 }
251 
252 /// Print a module, actually loop over the functions and print them in sequence.
253 void ASTDumper::dump(ModuleAST *node) {
254   INDENT();
255   llvm::errs() << "Module:\n";
256   for (auto &record : *node) {
257     if (FunctionAST *function = llvm::dyn_cast<FunctionAST>(record.get()))
258       dump(function);
259     else if (StructAST *str = llvm::dyn_cast<StructAST>(record.get()))
260       dump(str);
261     else
262       llvm::errs() << "<unknown Record, kind " << record->getKind() << ">\n";
263   }
264 }
265 
266 namespace toy {
267 
268 // Public API
269 void dump(ModuleAST &module) { ASTDumper().dump(&module); }
270 
271 } // namespace toy
272