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

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