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> static std::string loc(T *node) {
66   const auto &loc = node->loc();
67   return (llvm::Twine("@") + *loc.file + ":" + llvm::Twine(loc.line) + ":" +
68           llvm::Twine(loc.col))
69       .str();
70 }
71 
72 // Helper Macro to bump the indentation level and print the leading spaces for
73 // the current indentations
74 #define INDENT()                                                               \
75   Indent level_(curIndent);                                                    \
76   indent();
77 
78 /// Dispatch to a generic expressions to the appropriate subclass using RTTI
79 void ASTDumper::dump(ExprAST *expr) {
80   llvm::TypeSwitch<ExprAST *>(expr)
81       .Case<BinaryExprAST, CallExprAST, LiteralExprAST, NumberExprAST,
82             PrintExprAST, ReturnExprAST, StructLiteralExprAST, VarDeclExprAST,
83             VariableExprAST>([&](auto *node) { this->dump(node); })
84       .Default([&](ExprAST *) {
85         // No match, fallback to a generic message
86         INDENT();
87         llvm::errs() << "<unknown Expr, kind " << expr->getKind() << ">\n";
88       });
89 }
90 
91 /// A variable declaration is printing the variable name, the type, and then
92 /// recurse in the initializer value.
93 void ASTDumper::dump(VarDeclExprAST *varDecl) {
94   INDENT();
95   llvm::errs() << "VarDecl " << varDecl->getName();
96   dump(varDecl->getType());
97   llvm::errs() << " " << loc(varDecl) << "\n";
98   if (auto *initVal = varDecl->getInitVal())
99     dump(initVal);
100 }
101 
102 /// A "block", or a list of expression
103 void ASTDumper::dump(ExprASTList *exprList) {
104   INDENT();
105   llvm::errs() << "Block {\n";
106   for (auto &expr : *exprList)
107     dump(expr.get());
108   indent();
109   llvm::errs() << "} // Block\n";
110 }
111 
112 /// A literal number, just print the value.
113 void ASTDumper::dump(NumberExprAST *num) {
114   INDENT();
115   llvm::errs() << num->getValue() << " " << loc(num) << "\n";
116 }
117 
118 /// Helper to print recursively a literal. This handles nested array like:
119 ///    [ [ 1, 2 ], [ 3, 4 ] ]
120 /// We print out such array with the dimensions spelled out at every level:
121 ///    <2,2>[<2>[ 1, 2 ], <2>[ 3, 4 ] ]
122 void printLitHelper(ExprAST *litOrNum) {
123   // Inside a literal expression we can have either a number or another literal
124   if (auto *num = llvm::dyn_cast<NumberExprAST>(litOrNum)) {
125     llvm::errs() << num->getValue();
126     return;
127   }
128   auto *literal = llvm::cast<LiteralExprAST>(litOrNum);
129 
130   // Print the dimension for this literal first
131   llvm::errs() << "<";
132   llvm::interleaveComma(literal->getDims(), llvm::errs());
133   llvm::errs() << ">";
134 
135   // Now print the content, recursing on every element of the list
136   llvm::errs() << "[ ";
137   llvm::interleaveComma(literal->getValues(), llvm::errs(),
138                         [&](auto &elt) { printLitHelper(elt.get()); });
139   llvm::errs() << "]";
140 }
141 
142 /// Print a literal, see the recursive helper above for the implementation.
143 void ASTDumper::dump(LiteralExprAST *node) {
144   INDENT();
145   llvm::errs() << "Literal: ";
146   printLitHelper(node);
147   llvm::errs() << " " << loc(node) << "\n";
148 }
149 
150 /// Print a struct literal.
151 void ASTDumper::dump(StructLiteralExprAST *node) {
152   INDENT();
153   llvm::errs() << "Struct Literal: ";
154   for (auto &value : node->getValues())
155     dump(value.get());
156   indent();
157   llvm::errs() << " " << loc(node) << "\n";
158 }
159 
160 /// Print a variable reference (just a name).
161 void ASTDumper::dump(VariableExprAST *node) {
162   INDENT();
163   llvm::errs() << "var: " << node->getName() << " " << loc(node) << "\n";
164 }
165 
166 /// Return statement print the return and its (optional) argument.
167 void ASTDumper::dump(ReturnExprAST *node) {
168   INDENT();
169   llvm::errs() << "Return\n";
170   if (node->getExpr().hasValue())
171     return dump(*node->getExpr());
172   {
173     INDENT();
174     llvm::errs() << "(void)\n";
175   }
176 }
177 
178 /// Print a binary operation, first the operator, then recurse into LHS and RHS.
179 void ASTDumper::dump(BinaryExprAST *node) {
180   INDENT();
181   llvm::errs() << "BinOp: " << node->getOp() << " " << loc(node) << "\n";
182   dump(node->getLHS());
183   dump(node->getRHS());
184 }
185 
186 /// Print a call expression, first the callee name and the list of args by
187 /// recursing into each individual argument.
188 void ASTDumper::dump(CallExprAST *node) {
189   INDENT();
190   llvm::errs() << "Call '" << node->getCallee() << "' [ " << loc(node) << "\n";
191   for (auto &arg : node->getArgs())
192     dump(arg.get());
193   indent();
194   llvm::errs() << "]\n";
195 }
196 
197 /// Print a builtin print call, first the builtin name and then the argument.
198 void ASTDumper::dump(PrintExprAST *node) {
199   INDENT();
200   llvm::errs() << "Print [ " << loc(node) << "\n";
201   dump(node->getArg());
202   indent();
203   llvm::errs() << "]\n";
204 }
205 
206 /// Print type: only the shape is printed in between '<' and '>'
207 void ASTDumper::dump(const VarType &type) {
208   llvm::errs() << "<";
209   if (!type.name.empty())
210     llvm::errs() << type.name;
211   else
212     llvm::interleaveComma(type.shape, llvm::errs());
213   llvm::errs() << ">";
214 }
215 
216 /// Print a function prototype, first the function name, and then the list of
217 /// parameters names.
218 void ASTDumper::dump(PrototypeAST *node) {
219   INDENT();
220   llvm::errs() << "Proto '" << node->getName() << "' " << loc(node) << "\n";
221   indent();
222   llvm::errs() << "Params: [";
223   llvm::interleaveComma(node->getArgs(), llvm::errs(),
224                         [](auto &arg) { llvm::errs() << arg->getName(); });
225   llvm::errs() << "]\n";
226 }
227 
228 /// Print a function, first the prototype and then the body.
229 void ASTDumper::dump(FunctionAST *node) {
230   INDENT();
231   llvm::errs() << "Function \n";
232   dump(node->getProto());
233   dump(node->getBody());
234 }
235 
236 /// Print a struct.
237 void ASTDumper::dump(StructAST *node) {
238   INDENT();
239   llvm::errs() << "Struct: " << node->getName() << " " << loc(node) << "\n";
240 
241   {
242     INDENT();
243     llvm::errs() << "Variables: [\n";
244     for (auto &variable : node->getVariables())
245       dump(variable.get());
246     indent();
247     llvm::errs() << "]\n";
248   }
249 }
250 
251 /// Print a module, actually loop over the functions and print them in sequence.
252 void ASTDumper::dump(ModuleAST *node) {
253   INDENT();
254   llvm::errs() << "Module:\n";
255   for (auto &record : *node) {
256     if (FunctionAST *function = llvm::dyn_cast<FunctionAST>(record.get()))
257       dump(function);
258     else if (StructAST *str = llvm::dyn_cast<StructAST>(record.get()))
259       dump(str);
260     else
261       llvm::errs() << "<unknown Record, kind " << record->getKind() << ">\n";
262   }
263 }
264 
265 namespace toy {
266 
267 // Public API
268 void dump(ModuleAST &module) { ASTDumper().dump(&module); }
269 
270 } // namespace toy
271