ceph/src/boost/libs/spirit/example/qi/compiler_tutorial/conjure2/compiler.cpp

   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
  16 namespace client { namespace code_gen
  17 {
  18     void function::op(int a)
  19     {
  20         code.push_back(a);
  21         size_ += 1;
  22     }
  23
  24     void function::op(int a, int b)
  25     {
  26         code.push_back(a);
  27         code.push_back(b);
  28         size_ += 2;
  29     }
  30
  31     void function::op(int a, int b, int c)
  32     {
  33         code.push_back(a);
  34         code.push_back(b);
  35         code.push_back(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(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 += 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_call:
 185                     {
 186                         line += "      op_call     ";
 187                         int nargs = *pc++;
 188                         std::size_t jump = *pc++;
 189                         line += boost::lexical_cast<std::string>(nargs) + ", ";
 190                         BOOST_ASSERT(function_calls.find(jump) != function_calls.end());
 191                         line += function_calls.find(jump)->second;
 192                     }
 193                     break;
 194
 195                 case op_stk_adj:
 196                     line += "      op_stk_adj  ";
 197                     line += boost::lexical_cast<std::string>(*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(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(op_int, x);
 225         return true;
 226     }
 227
 228     bool compiler::operator()(bool x)
 229     {
 230         BOOST_ASSERT(current != 0);
 231         current->op(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(x.name);
 239         if (p == 0)
 240         {
 241             error_handler(x.id, "Undeclared variable: " + x.name);
 242             return false;
 243         }
 244         current->op(op_load, *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(op_add); break;
 254             case token_ids::minus: current->op(op_sub); break;
 255             case token_ids::times: current->op(op_mul); break;
 256             case token_ids::divide: current->op(op_div); break;
 257
 258             case token_ids::equal: current->op(op_eq); break;
 259             case token_ids::not_equal: current->op(op_neq); break;
 260             case token_ids::less: current->op(op_lt); break;
 261             case token_ids::less_equal: current->op(op_lte); break;
 262             case token_ids::greater: current->op(op_gt); break;
 263             case token_ids::greater_equal: current->op(op_gte); break;
 264
 265             case token_ids::logical_or: current->op(op_or); break;
 266             case token_ids::logical_and: current->op(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(*this, x.operand_))
 276             return false;
 277         switch (x.operator_)
 278         {
 279             case token_ids::minus: current->op(op_neg); break;
 280             case token_ids::not_: current->op(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.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             op_call,
 313             p->nargs(),
 314             p->get_address());
 315         current->link_to(x.function_name.name, 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(rbegin->operator_) >= min_precedence))
 391         {
 392             token_ids::type op = rbegin->operator_;
 393             if (!boost::apply_visitor(*this, rbegin->operand_))
 394                 return false;
 395             ++rbegin;
 396
 397             while ((rbegin != rend) && (precedence_of(rbegin->operator_) > precedence_of(op)))
 398             {
 399                 token_ids::type next_op = rbegin->operator_;
 400                 compile_expression(precedence_of(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(*this, x.first))
 411             return false;
 412         std::list<ast::operation>::const_iterator rbegin = x.rest.begin();
 413         if (!compile_expression(0, rbegin, 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(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(op_store, *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(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(x.lhs.name);
 448                 current->op(op_store, *current->find_var(x.lhs.name));
 449             }
 450             return r;
 451         }
 452         else
 453         {
 454             current->add_var(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(*this, 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(op_jump_if, 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(op_jump, 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(op_jump_if, 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(op_jump,
 511             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(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.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(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(op_stk_adj, 0);
 560         BOOST_FOREACH(ast::identifier const& arg, x.args)
 561         {
 562             current->add_var(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(op_jump);
 576         code.push_back(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("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(name);
 616         if (i == functions.end())
 617             return boost::shared_ptr<code_gen::function>();
 618         else
 619             return i->second;
 620     }
 621 }}
 622