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
15namespace client { namespace code_gen
16{
17 void function::op(int a)
18 {
19 code.push_back(x: a);
20 size_ += 1;
21 }
22
23 void function::op(int a, int b)
24 {
25 code.push_back(x: a);
26 code.push_back(x: b);
27 size_ += 2;
28 }
29
30 void function::op(int a, int b, int c)
31 {
32 code.push_back(x: a);
33 code.push_back(x: b);
34 code.push_back(x: c);
35 size_ += 3;
36 }
37
38 int const* function::find_var(std::string const& name) const
39 {
40 std::map<std::string, int>::const_iterator i = variables.find(x: name);
41 if (i == variables.end())
42 return 0;
43 return &i->second;
44 }
45
46 void function::add_var(std::string const& name)
47 {
48 std::size_t n = variables.size();
49 variables[name] = n;
50 }
51
52 void function::link_to(std::string const& name, std::size_t address)
53 {
54 function_calls[address] = name;
55 }
56
57 void function::print_assembler() const
58 {
59 std::vector<int>::const_iterator pc = code.begin() + address;
60
61 std::vector<std::string> locals(variables.size());
62 typedef std::pair<std::string, int> pair;
63 BOOST_FOREACH(pair const& p, variables)
64 {
65 locals[p.second] = p.first;
66 std::cout << " local "
67 << p.first << ", @" << p.second << std::endl;
68 }
69
70 std::map<std::size_t, std::string> lines;
71 std::set<std::size_t> jumps;
72
73 while (pc != (code.begin() + address + size_))
74 {
75 std::string line;
76 std::size_t address = pc - code.begin();
77
78 switch (*pc++)
79 {
80 case op_neg:
81 line += " op_neg";
82 break;
83
84 case op_not:
85 line += " op_not";
86 break;
87
88 case op_add:
89 line += " op_add";
90 break;
91
92 case op_sub:
93 line += " op_sub";
94 break;
95
96 case op_mul:
97 line += " op_mul";
98 break;
99
100 case op_div:
101 line += " op_div";
102 break;
103
104 case op_eq:
105 line += " op_eq";
106 break;
107
108 case op_neq:
109 line += " op_neq";
110 break;
111
112 case op_lt:
113 line += " op_lt";
114 break;
115
116 case op_lte:
117 line += " op_lte";
118 break;
119
120 case op_gt:
121 line += " op_gt";
122 break;
123
124 case op_gte:
125 line += " op_gte";
126 break;
127
128 case op_and:
129 line += " op_and";
130 break;
131
132 case op_or:
133 line += " op_or";
134 break;
135
136 case op_load:
137 line += " op_load ";
138 line += locals[*pc++];
139 break;
140
141 case op_store:
142 line += " op_store ";
143 line += locals[*pc++];
144 break;
145
146 case op_int:
147 line += " op_int ";
148 line += boost::lexical_cast<std::string>(arg: *pc++);
149 break;
150
151 case op_true:
152 line += " op_true";
153 break;
154
155 case op_false:
156 line += " op_false";
157 break;
158
159 case op_jump:
160 {
161 line += " op_jump ";
162 std::size_t pos = (pc - code.begin()) + *pc++;
163 if (pos == code.size())
164 line += "end";
165 else
166 line += boost::lexical_cast<std::string>(arg: pos);
167 jumps.insert(x: pos);
168 }
169 break;
170
171 case op_jump_if:
172 {
173 line += " op_jump_if ";
174 std::size_t pos = (pc - code.begin()) + *pc++;
175 if (pos == code.size())
176 line += "end";
177 else
178 line += boost::lexical_cast<std::string>(arg: pos);
179 jumps.insert(x: pos);
180 }
181 break;
182
183 case op_call:
184 {
185 line += " op_call ";
186 int nargs = *pc++;
187 std::size_t jump = *pc++;
188 line += boost::lexical_cast<std::string>(arg: nargs) + ", ";
189 BOOST_ASSERT(function_calls.find(jump) != function_calls.end());
190 line += function_calls.find(x: jump)->second;
191 }
192 break;
193
194 case op_stk_adj:
195 line += " op_stk_adj ";
196 line += boost::lexical_cast<std::string>(arg: *pc++);
197 break;
198
199
200 case op_return:
201 line += " op_return";
202 break;
203 }
204 lines[address] = line;
205 }
206
207 std::cout << "start:" << std::endl;
208 typedef std::pair<std::size_t, std::string> line_info;
209 BOOST_FOREACH(line_info const& l, lines)
210 {
211 std::size_t pos = l.first;
212 if (jumps.find(x: pos) != jumps.end())
213 std::cout << pos << ':' << std::endl;
214 std::cout << l.second << std::endl;
215 }
216
217 std::cout << "end:" << std::endl << std::endl;
218 }
219
220 bool compiler::operator()(unsigned int x)
221 {
222 BOOST_ASSERT(current != 0);
223 current->op(a: op_int, b: x);
224 return true;
225 }
226
227 bool compiler::operator()(bool x)
228 {
229 BOOST_ASSERT(current != 0);
230 current->op(a: x ? op_true : op_false);
231 return true;
232 }
233
234 bool compiler::operator()(ast::identifier const& x)
235 {
236 BOOST_ASSERT(current != 0);
237 int const* p = current->find_var(name: x.name);
238 if (p == 0)
239 {
240 error_handler(x.id, "Undeclared variable: " + x.name);
241 return false;
242 }
243 current->op(a: op_load, b: *p);
244 return true;
245 }
246
247 bool compiler::operator()(ast::optoken const& x)
248 {
249 BOOST_ASSERT(current != 0);
250 switch (x)
251 {
252 case ast::op_plus: current->op(a: op_add); break;
253 case ast::op_minus: current->op(a: op_sub); break;
254 case ast::op_times: current->op(a: op_mul); break;
255 case ast::op_divide: current->op(a: op_div); break;
256
257 case ast::op_equal: current->op(a: op_eq); break;
258 case ast::op_not_equal: current->op(a: op_neq); break;
259 case ast::op_less: current->op(a: op_lt); break;
260 case ast::op_less_equal: current->op(a: op_lte); break;
261 case ast::op_greater: current->op(a: op_gt); break;
262 case ast::op_greater_equal: current->op(a: op_gte); break;
263
264 case ast::op_logical_or: current->op(a: op_or); break;
265 case ast::op_logical_and: current->op(a: op_and); break;
266 default: BOOST_ASSERT(0); return false;
267 }
268 return true;
269 }
270
271 bool compiler::operator()(ast::unary const& x)
272 {
273 BOOST_ASSERT(current != 0);
274 if (!boost::apply_visitor(visitor&: *this, visitable: x.operand_))
275 return false;
276 switch (x.operator_)
277 {
278 case ast::op_negative: current->op(a: op_neg); break;
279 case ast::op_not: current->op(a: op_not); break;
280 case ast::op_positive: break;
281 default: BOOST_ASSERT(0); return false;
282 }
283 return true;
284 }
285
286 bool compiler::operator()(ast::function_call const& x)
287 {
288 BOOST_ASSERT(current != 0);
289
290 if (functions.find(x: x.function_name.name) == functions.end())
291 {
292 error_handler(x.function_name.id, "Function not found: " + x.function_name.name);
293 return false;
294 }
295
296 boost::shared_ptr<code_gen::function> p = functions[x.function_name.name];
297
298 if (p->nargs() != x.args.size())
299 {
300 error_handler(x.function_name.id, "Wrong number of arguments: " + x.function_name.name);
301 return false;
302 }
303
304 BOOST_FOREACH(ast::expression const& expr, x.args)
305 {
306 if (!(*this)(expr))
307 return false;
308 }
309
310 current->op(
311 a: op_call,
312 b: p->nargs(),
313 c: p->get_address());
314 current->link_to(name: x.function_name.name, address: p->get_address());
315
316 return true;
317 }
318
319 namespace
320 {
321 int precedence[] = {
322 // precedence 1
323 1, // op_comma
324
325 // precedence 2
326 2, // op_assign
327 2, // op_plus_assign
328 2, // op_minus_assign
329 2, // op_times_assign
330 2, // op_divide_assign
331 2, // op_mod_assign
332 2, // op_bit_and_assign
333 2, // op_bit_xor_assign
334 2, // op_bitor_assign
335 2, // op_shift_left_assign
336 2, // op_shift_right_assign
337
338 // precedence 3
339 3, // op_logical_or
340
341 // precedence 4
342 4, // op_logical_and
343
344 // precedence 5
345 5, // op_bit_or
346
347 // precedence 6
348 6, // op_bit_xor
349
350 // precedence 7
351 7, // op_bit_and
352
353 // precedence 8
354 8, // op_equal
355 8, // op_not_equal
356
357 // precedence 9
358 9, // op_less
359 9, // op_less_equal
360 9, // op_greater
361 9, // op_greater_equal
362
363 // precedence 10
364 10, // op_shift_left
365 10, // op_shift_right
366
367 // precedence 11
368 11, // op_plus
369 11, // op_minus
370
371 // precedence 12
372 12, // op_times
373 12, // op_divide
374 12, // op_mod
375
376 // precedence 13
377 13, // op_positive
378 13, // op_negative
379 13, // op_pre_incr
380 13, // op_pre_decr
381 13, // op_compl
382 13, // op_not
383
384 // precedence 14
385 14, // op_post_incr
386 14 // op_post_decr
387 };
388 }
389
390 // The Shunting-yard algorithm
391 bool compiler::compile_expression(
392 int min_precedence,
393 std::list<ast::operation>::const_iterator& rbegin,
394 std::list<ast::operation>::const_iterator rend)
395 {
396 while ((rbegin != rend) && (precedence[rbegin->operator_] >= min_precedence))
397 {
398 ast::optoken op = rbegin->operator_;
399 if (!boost::apply_visitor(visitor&: *this, visitable: rbegin->operand_))
400 return false;
401 ++rbegin;
402
403 while ((rbegin != rend) && (precedence[rbegin->operator_] > precedence[op]))
404 {
405 ast::optoken next_op = rbegin->operator_;
406 compile_expression(min_precedence: precedence[next_op], rbegin, rend);
407 }
408 (*this)(op);
409 }
410 return true;
411 }
412
413 bool compiler::operator()(ast::expression const& x)
414 {
415 BOOST_ASSERT(current != 0);
416 if (!boost::apply_visitor(visitor&: *this, visitable: x.first))
417 return false;
418 std::list<ast::operation>::const_iterator rbegin = x.rest.begin();
419 if (!compile_expression(min_precedence: 0, rbegin, rend: x.rest.end()))
420 return false;
421 return true;
422 }
423
424 bool compiler::operator()(ast::assignment const& x)
425 {
426 BOOST_ASSERT(current != 0);
427 if (!(*this)(x.rhs))
428 return false;
429 int const* p = current->find_var(name: x.lhs.name);
430 if (p == 0)
431 {
432 error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name);
433 return false;
434 }
435 current->op(a: op_store, b: *p);
436 return true;
437 }
438
439 bool compiler::operator()(ast::variable_declaration const& x)
440 {
441 BOOST_ASSERT(current != 0);
442 int const* p = current->find_var(name: x.lhs.name);
443 if (p != 0)
444 {
445 error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name);
446 return false;
447 }
448 if (x.rhs) // if there's an RHS initializer
449 {
450 bool r = (*this)(*x.rhs);
451 if (r) // don't add the variable if the RHS fails
452 {
453 current->add_var(name: x.lhs.name);
454 current->op(a: op_store, b: *current->find_var(name: x.lhs.name));
455 }
456 return r;
457 }
458 else
459 {
460 current->add_var(name: x.lhs.name);
461 }
462 return true;
463 }
464
465 bool compiler::operator()(ast::statement const& x)
466 {
467 BOOST_ASSERT(current != 0);
468 return boost::apply_visitor(visitor&: *this, visitable: x);
469 }
470
471 bool compiler::operator()(ast::statement_list const& x)
472 {
473 BOOST_ASSERT(current != 0);
474 BOOST_FOREACH(ast::statement const& s, x)
475 {
476 if (!(*this)(s))
477 return false;
478 }
479 return true;
480 }
481
482 bool compiler::operator()(ast::if_statement const& x)
483 {
484 BOOST_ASSERT(current != 0);
485 if (!(*this)(x.condition))
486 return false;
487 current->op(a: op_jump_if, b: 0); // we shall fill this (0) in later
488 std::size_t skip = current->size()-1; // mark its position
489 if (!(*this)(x.then))
490 return false;
491 (*current)[skip] = current->size()-skip; // now we know where to jump to (after the if branch)
492
493 if (x.else_) // We got an alse
494 {
495 (*current)[skip] += 2; // adjust for the "else" jump
496 current->op(a: op_jump, b: 0); // we shall fill this (0) in later
497 std::size_t exit = current->size()-1; // mark its position
498 if (!(*this)(*x.else_))
499 return false;
500 (*current)[exit] = current->size()-exit;// now we know where to jump to (after the else branch)
501 }
502
503 return true;
504 }
505
506 bool compiler::operator()(ast::while_statement const& x)
507 {
508 BOOST_ASSERT(current != 0);
509 std::size_t loop = current->size(); // mark our position
510 if (!(*this)(x.condition))
511 return false;
512 current->op(a: op_jump_if, b: 0); // we shall fill this (0) in later
513 std::size_t exit = current->size()-1; // mark its position
514 if (!(*this)(x.body))
515 return false;
516 current->op(a: op_jump,
517 b: int(loop-1) - int(current->size())); // loop back
518 (*current)[exit] = current->size()-exit; // now we know where to jump to (to exit the loop)
519 return true;
520 }
521
522 bool compiler::operator()(ast::return_statement const& x)
523 {
524 if (void_return)
525 {
526 if (x.expr)
527 {
528 error_handler(x.id, "'void' function returning a value: ");
529 return false;
530 }
531 }
532 else
533 {
534 if (!x.expr)
535 {
536 error_handler(x.id, current_function_name + " function must return a value: ");
537 return false;
538 }
539 }
540
541 if (x.expr)
542 {
543 if (!(*this)(*x.expr))
544 return false;
545 }
546 current->op(a: op_return);
547 return true;
548 }
549
550 bool compiler::operator()(ast::function const& x)
551 {
552 void_return = x.return_type == "void";
553 if (functions.find(x: x.function_name.name) != functions.end())
554 {
555 error_handler(x.function_name.id, "Duplicate function: " + x.function_name.name);
556 return false;
557 }
558 boost::shared_ptr<code_gen::function>& p = functions[x.function_name.name];
559 p.reset(p: new code_gen::function(code, x.args.size()));
560 current = p.get();
561 current_function_name = x.function_name.name;
562
563 // op_stk_adj 0 for now. we'll know how many variables
564 // we'll have later and add them
565 current->op(a: op_stk_adj, b: 0);
566 BOOST_FOREACH(ast::identifier const& arg, x.args)
567 {
568 current->add_var(name: arg.name);
569 }
570
571 if (!(*this)(x.body))
572 return false;
573 (*current)[1] = current->nvars(); // now store the actual number of variables
574 // this includes the arguments
575 return true;
576 }
577
578 bool compiler::operator()(ast::function_list const& x)
579 {
580 // Jump to the main function
581 code.push_back(x: op_jump);
582 code.push_back(x: 0); // we will fill this in later when we finish compiling
583 // and we know where the main function is
584
585 BOOST_FOREACH(ast::function const& f, x)
586 {
587 if (!(*this)(f))
588 {
589 code.clear();
590 return false;
591 }
592 }
593 // find the main function
594 boost::shared_ptr<code_gen::function> p =
595 find_function(name: "main");
596
597 if (!p) // main function not found
598 {
599 std::cerr << "Error: main function not defined" << std::endl;
600 return false;
601 }
602 code[1] = p->get_address()-1; // jump to this (main function) address
603
604 return true;
605 }
606
607 void compiler::print_assembler() const
608 {
609 typedef std::pair<std::string, boost::shared_ptr<code_gen::function> > pair;
610 BOOST_FOREACH(pair const& p, functions)
611 {
612 std::cout << ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;" << std::endl;
613 std::cout << p.second->get_address() << ": function " << p.first << std::endl;
614 p.second->print_assembler();
615 }
616 }
617
618 boost::shared_ptr<code_gen::function>
619 compiler::find_function(std::string const& name) const
620 {
621 function_table::const_iterator i = functions.find(x: name);
622 if (i == functions.end())
623 return boost::shared_ptr<code_gen::function>();
624 else
625 return i->second;
626 }
627}}
628
629

source code of boost/libs/spirit/example/qi/compiler_tutorial/conjure1/compiler.cpp