1 /*=============================================================================
2     Copyright (c) 2001-2011 Joel de Guzman
3 
4     Distributed under the Boost Software License, Version 1.0. (See accompanying
5     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 =============================================================================*/
7 #include "compiler.hpp"
8 #include "vm.hpp"
9 #include <boost/foreach.hpp>
10 #include <boost/variant/apply_visitor.hpp>
11 #include <boost/assert.hpp>
12 #include <boost/lexical_cast.hpp>
13 #include <set>
14 
15 namespace client { namespace code_gen
16 {
op(int a)17     void program::op(int a)
18     {
19         code.push_back(a);
20     }
21 
op(int a,int b)22     void program::op(int a, int b)
23     {
24         code.push_back(a);
25         code.push_back(b);
26     }
27 
op(int a,int b,int c)28     void program::op(int a, int b, int c)
29     {
30         code.push_back(a);
31         code.push_back(b);
32         code.push_back(c);
33     }
34 
find_var(std::string const & name) const35     int const* program::find_var(std::string const& name) const
36     {
37         std::map<std::string, int>::const_iterator i = variables.find(name);
38         if (i == variables.end())
39             return 0;
40         return &i->second;
41     }
42 
add_var(std::string const & name)43     void program::add_var(std::string const& name)
44     {
45         std::size_t n = variables.size();
46         variables[name] = n;
47     }
48 
print_variables(std::vector<int> const & stack) const49     void program::print_variables(std::vector<int> const& stack) const
50     {
51         typedef std::pair<std::string, int> pair;
52         BOOST_FOREACH(pair const& p, variables)
53         {
54             std::cout << "    " << p.first << ": " << stack[p.second] << std::endl;
55         }
56     }
57 
print_assembler() const58     void program::print_assembler() const
59     {
60         std::vector<int>::const_iterator pc = code.begin();
61 
62         std::vector<std::string> locals(variables.size());
63         typedef std::pair<std::string, int> pair;
64         BOOST_FOREACH(pair const& p, variables)
65         {
66             locals[p.second] = p.first;
67             std::cout << "      local       "
68                 << p.first << ", @" << p.second << std::endl;
69         }
70 
71         std::map<std::size_t, std::string> lines;
72         std::set<std::size_t> jumps;
73 
74         while (pc != code.end())
75         {
76             std::string line;
77             std::size_t address = pc - code.begin();
78 
79             switch (*pc++)
80             {
81                 case op_neg:
82                     line += "      op_neg";
83                     break;
84 
85                 case op_not:
86                     line += "      op_not";
87                     break;
88 
89                 case op_add:
90                     line += "      op_add";
91                     break;
92 
93                 case op_sub:
94                     line += "      op_sub";
95                     break;
96 
97                 case op_mul:
98                     line += "      op_mul";
99                     break;
100 
101                 case op_div:
102                     line += "      op_div";
103                     break;
104 
105                 case op_eq:
106                     line += "      op_eq";
107                     break;
108 
109                 case op_neq:
110                     line += "      op_neq";
111                     break;
112 
113                 case op_lt:
114                     line += "      op_lt";
115                     break;
116 
117                 case op_lte:
118                     line += "      op_lte";
119                     break;
120 
121                 case op_gt:
122                     line += "      op_gt";
123                     break;
124 
125                 case op_gte:
126                     line += "      op_gte";
127                     break;
128 
129                 case op_and:
130                     line += "      op_and";
131                     break;
132 
133                 case op_or:
134                     line += "      op_or";
135                     break;
136 
137                 case op_load:
138                     line += "      op_load     ";
139                     line += boost::lexical_cast<std::string>(locals[*pc++]);
140                     break;
141 
142                 case op_store:
143                     line += "      op_store    ";
144                     line += boost::lexical_cast<std::string>(locals[*pc++]);
145                     break;
146 
147                 case op_int:
148                     line += "      op_int      ";
149                     line += boost::lexical_cast<std::string>(*pc++);
150                     break;
151 
152                 case op_true:
153                     line += "      op_true";
154                     break;
155 
156                 case op_false:
157                     line += "      op_false";
158                     break;
159 
160                 case op_jump:
161                     {
162                         line += "      op_jump     ";
163                         std::size_t pos = (pc - code.begin()) + *pc++;
164                         if (pos == code.size())
165                             line += "end";
166                         else
167                             line += boost::lexical_cast<std::string>(pos);
168                         jumps.insert(pos);
169                     }
170                     break;
171 
172                 case op_jump_if:
173                     {
174                         line += "      op_jump_if  ";
175                         std::size_t pos = (pc - code.begin()) + *pc++;
176                         if (pos == code.size())
177                             line += "end";
178                         else
179                             line += boost::lexical_cast<std::string>(pos);
180                         jumps.insert(pos);
181                     }
182                     break;
183 
184                 case op_stk_adj:
185                     line += "      op_stk_adj  ";
186                     line += boost::lexical_cast<std::string>(*pc++);
187                     break;
188             }
189             lines[address] = line;
190         }
191 
192         std::cout << "start:" << std::endl;
193         typedef std::pair<std::size_t, std::string> line_info;
194         BOOST_FOREACH(line_info const& l, lines)
195         {
196             std::size_t pos = l.first;
197             if (jumps.find(pos) != jumps.end())
198                 std::cout << pos << ':' << std::endl;
199             std::cout << l.second << std::endl;
200         }
201 
202         std::cout << "end:" << std::endl;
203     }
204 
operator ()(unsigned int x) const205     bool compiler::operator()(unsigned int x) const
206     {
207         program.op(op_int, x);
208         return true;
209     }
210 
operator ()(bool x) const211     bool compiler::operator()(bool x) const
212     {
213         program.op(x ? op_true : op_false);
214         return true;
215     }
216 
operator ()(ast::variable const & x) const217     bool compiler::operator()(ast::variable const& x) const
218     {
219         int const* p = program.find_var(x.name);
220         if (p == 0)
221         {
222             std::cout << x.id << std::endl;
223             error_handler(x.id, "Undeclared variable: " + x.name);
224             return false;
225         }
226         program.op(op_load, *p);
227         return true;
228     }
229 
operator ()(ast::operation const & x) const230     bool compiler::operator()(ast::operation const& x) const
231     {
232         if (!boost::apply_visitor(*this, x.operand_))
233             return false;
234         switch (x.operator_)
235         {
236             case ast::op_plus: program.op(op_add); break;
237             case ast::op_minus: program.op(op_sub); break;
238             case ast::op_times: program.op(op_mul); break;
239             case ast::op_divide: program.op(op_div); break;
240 
241             case ast::op_equal: program.op(op_eq); break;
242             case ast::op_not_equal: program.op(op_neq); break;
243             case ast::op_less: program.op(op_lt); break;
244             case ast::op_less_equal: program.op(op_lte); break;
245             case ast::op_greater: program.op(op_gt); break;
246             case ast::op_greater_equal: program.op(op_gte); break;
247 
248             case ast::op_and: program.op(op_and); break;
249             case ast::op_or: program.op(op_or); break;
250             default: BOOST_ASSERT(0); return false;
251         }
252         return true;
253     }
254 
operator ()(ast::unary const & x) const255     bool compiler::operator()(ast::unary const& x) const
256     {
257         if (!boost::apply_visitor(*this, x.operand_))
258             return false;
259         switch (x.operator_)
260         {
261             case ast::op_negative: program.op(op_neg); break;
262             case ast::op_not: program.op(op_not); break;
263             case ast::op_positive: break;
264             default: BOOST_ASSERT(0); return false;
265         }
266         return true;
267     }
268 
operator ()(ast::expression const & x) const269     bool compiler::operator()(ast::expression const& x) const
270     {
271         if (!boost::apply_visitor(*this, x.first))
272             return false;
273         BOOST_FOREACH(ast::operation const& oper, x.rest)
274         {
275             if (!(*this)(oper))
276                 return false;
277         }
278         return true;
279     }
280 
operator ()(ast::assignment const & x) const281     bool compiler::operator()(ast::assignment const& x) const
282     {
283         if (!(*this)(x.rhs))
284             return false;
285         int const* p = program.find_var(x.lhs.name);
286         if (p == 0)
287         {
288             std::cout << x.lhs.id << std::endl;
289             error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name);
290             return false;
291         }
292         program.op(op_store, *p);
293         return true;
294     }
295 
operator ()(ast::variable_declaration const & x) const296     bool compiler::operator()(ast::variable_declaration const& x) const
297     {
298         int const* p = program.find_var(x.assign.lhs.name);
299         if (p != 0)
300         {
301             std::cout << x.assign.lhs.id << std::endl;
302             error_handler(x.assign.lhs.id, "Duplicate variable: " + x.assign.lhs.name);
303             return false;
304         }
305         bool r = (*this)(x.assign.rhs);
306         if (r) // don't add the variable if the RHS fails
307         {
308             program.add_var(x.assign.lhs.name);
309             program.op(op_store, *program.find_var(x.assign.lhs.name));
310         }
311         return r;
312     }
313 
operator ()(ast::statement const & x) const314     bool compiler::operator()(ast::statement const& x) const
315     {
316         return boost::apply_visitor(*this, x);
317     }
318 
operator ()(ast::statement_list const & x) const319     bool compiler::operator()(ast::statement_list const& x) const
320     {
321         BOOST_FOREACH(ast::statement const& s, x)
322         {
323             if (!(*this)(s))
324                 return false;
325         }
326         return true;
327     }
328 
operator ()(ast::if_statement const & x) const329     bool compiler::operator()(ast::if_statement const& x) const
330     {
331         if (!(*this)(x.condition))
332             return false;
333         program.op(op_jump_if, 0);                  // we shall fill this (0) in later
334         std::size_t skip = program.size()-1;        // mark its position
335         if (!(*this)(x.then))
336             return false;
337         program[skip] = program.size()-skip;        // now we know where to jump to (after the if branch)
338 
339         if (x.else_)                                // We got an alse
340         {
341             program[skip] += 2;                     // adjust for the "else" jump
342             program.op(op_jump, 0);                 // we shall fill this (0) in later
343             std::size_t exit = program.size()-1;    // mark its position
344             if (!(*this)(*x.else_))
345                 return false;
346             program[exit] = program.size()-exit;    // now we know where to jump to (after the else branch)
347         }
348 
349         return true;
350     }
351 
operator ()(ast::while_statement const & x) const352     bool compiler::operator()(ast::while_statement const& x) const
353     {
354         std::size_t loop = program.size();          // mark our position
355         if (!(*this)(x.condition))
356             return false;
357         program.op(op_jump_if, 0);                  // we shall fill this (0) in later
358         std::size_t exit = program.size()-1;        // mark its position
359         if (!(*this)(x.body))
360             return false;
361         program.op(op_jump,
362             int(loop-1) - int(program.size()));     // loop back
363         program[exit] = program.size()-exit;        // now we know where to jump to (to exit the loop)
364         return true;
365     }
366 
start(ast::statement_list const & x) const367     bool compiler::start(ast::statement_list const& x) const
368     {
369         program.clear();
370         // op_stk_adj 0 for now. we'll know how many variables we'll have later
371         program.op(op_stk_adj, 0);
372 
373         if (!(*this)(x))
374         {
375             program.clear();
376             return false;
377         }
378         program[1] = program.nvars(); // now store the actual number of variables
379         return true;
380     }
381 }}
382 
383