ceph/src/boost/libs/spirit/example/qi/compiler_tutorial/mini_c/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 "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 {
  17     void function::op(int a)
  18     {
  19         code.push_back(a);
  20         size_ += 1;
  21     }
  22
  23     void function::op(int a, int b)
  24     {
  25         code.push_back(a);
  26         code.push_back(b);
  27         size_ += 2;
  28     }
  29
  30     void function::op(int a, int b, int c)
  31     {
  32         code.push_back(a);
  33         code.push_back(b);
  34         code.push_back(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(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 += boost::lexical_cast<std::string>(locals[*pc++]);
 139                     break;
 140
 141                 case op_store:
 142                     line += "      op_store    ";
 143                     line += boost::lexical_cast<std::string>(locals[*pc++]);
 144                     break;
 145
 146                 case op_int:
 147                     line += "      op_int      ";
 148                     line += boost::lexical_cast<std::string>(*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>(pos);
 167                         jumps.insert(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>(pos);
 179                         jumps.insert(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>(nargs) + ", ";
 189                         BOOST_ASSERT(function_calls.find(jump) != function_calls.end());
 190                         line += function_calls.find(jump)->second;
 191                     }
 192                     break;
 193
 194                 case op_stk_adj:
 195                     line += "      op_stk_adj  ";
 196                     line += boost::lexical_cast<std::string>(*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(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(op_int, x);
 224         return true;
 225     }
 226
 227     bool compiler::operator()(bool x)
 228     {
 229         BOOST_ASSERT(current != 0);
 230         current->op(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(x.name);
 238         if (p == 0)
 239         {
 240             error_handler(x.id, "Undeclared variable: " + x.name);
 241             return false;
 242         }
 243         current->op(op_load, *p);
 244         return true;
 245     }
 246
 247     bool compiler::operator()(ast::operation const& x)
 248     {
 249         BOOST_ASSERT(current != 0);
 250         if (!boost::apply_visitor(*this, x.operand_))
 251             return false;
 252         switch (x.operator_)
 253         {
 254             case ast::op_plus: current->op(op_add); break;
 255             case ast::op_minus: current->op(op_sub); break;
 256             case ast::op_times: current->op(op_mul); break;
 257             case ast::op_divide: current->op(op_div); break;
 258
 259             case ast::op_equal: current->op(op_eq); break;
 260             case ast::op_not_equal: current->op(op_neq); break;
 261             case ast::op_less: current->op(op_lt); break;
 262             case ast::op_less_equal: current->op(op_lte); break;
 263             case ast::op_greater: current->op(op_gt); break;
 264             case ast::op_greater_equal: current->op(op_gte); break;
 265
 266             case ast::op_and: current->op(op_and); break;
 267             case ast::op_or: current->op(op_or); break;
 268             default: BOOST_ASSERT(0); return false;
 269         }
 270         return true;
 271     }
 272
 273     bool compiler::operator()(ast::unary const& x)
 274     {
 275         BOOST_ASSERT(current != 0);
 276         if (!boost::apply_visitor(*this, x.operand_))
 277             return false;
 278         switch (x.operator_)
 279         {
 280             case ast::op_negative: current->op(op_neg); break;
 281             case ast::op_not: current->op(op_not); break;
 282             case ast::op_positive: break;
 283             default: BOOST_ASSERT(0); return false;
 284         }
 285         return true;
 286     }
 287
 288     bool compiler::operator()(ast::function_call const& x)
 289     {
 290         BOOST_ASSERT(current != 0);
 291
 292         if (functions.find(x.function_name.name) == functions.end())
 293         {
 294             error_handler(x.function_name.id, "Function not found: " + x.function_name.name);
 295             return false;
 296         }
 297
 298         boost::shared_ptr<code_gen::function> p = functions[x.function_name.name];
 299
 300         if (p->nargs() != x.args.size())
 301         {
 302             error_handler(x.function_name.id, "Wrong number of arguments: " + x.function_name.name);
 303             return false;
 304         }
 305
 306         BOOST_FOREACH(ast::expression const& expr, x.args)
 307         {
 308             if (!(*this)(expr))
 309                 return false;
 310         }
 311
 312         current->op(
 313             op_call,
 314             p->nargs(),
 315             p->get_address());
 316         current->link_to(x.function_name.name, p->get_address());
 317
 318         return true;
 319     }
 320
 321     bool compiler::operator()(ast::expression const& x)
 322     {
 323         BOOST_ASSERT(current != 0);
 324         if (!boost::apply_visitor(*this, x.first))
 325             return false;
 326         BOOST_FOREACH(ast::operation const& oper, x.rest)
 327         {
 328             if (!(*this)(oper))
 329                 return false;
 330         }
 331         return true;
 332     }
 333
 334     bool compiler::operator()(ast::assignment const& x)
 335     {
 336         BOOST_ASSERT(current != 0);
 337         if (!(*this)(x.rhs))
 338             return false;
 339         int const* p = current->find_var(x.lhs.name);
 340         if (p == 0)
 341         {
 342             error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name);
 343             return false;
 344         }
 345         current->op(op_store, *p);
 346         return true;
 347     }
 348
 349     bool compiler::operator()(ast::variable_declaration const& x)
 350     {
 351         BOOST_ASSERT(current != 0);
 352         int const* p = current->find_var(x.lhs.name);
 353         if (p != 0)
 354         {
 355             error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name);
 356             return false;
 357         }
 358         if (x.rhs) // if there's an RHS initializer
 359         {
 360             bool r = (*this)(*x.rhs);
 361             if (r) // don't add the variable if the RHS fails
 362             {
 363                 current->add_var(x.lhs.name);
 364                 current->op(op_store, *current->find_var(x.lhs.name));
 365             }
 366             return r;
 367         }
 368         else
 369         {
 370             current->add_var(x.lhs.name);
 371         }
 372         return true;
 373     }
 374
 375     bool compiler::operator()(ast::statement const& x)
 376     {
 377         BOOST_ASSERT(current != 0);
 378         return boost::apply_visitor(*this, x);
 379     }
 380
 381     bool compiler::operator()(ast::statement_list const& x)
 382     {
 383         BOOST_ASSERT(current != 0);
 384         BOOST_FOREACH(ast::statement const& s, x)
 385         {
 386             if (!(*this)(s))
 387                 return false;
 388         }
 389         return true;
 390     }
 391
 392     bool compiler::operator()(ast::if_statement const& x)
 393     {
 394         BOOST_ASSERT(current != 0);
 395         if (!(*this)(x.condition))
 396             return false;
 397         current->op(op_jump_if, 0);                 // we shall fill this (0) in later
 398         std::size_t skip = current->size()-1;       // mark its position
 399         if (!(*this)(x.then))
 400             return false;
 401         (*current)[skip] = current->size()-skip;    // now we know where to jump to (after the if branch)
 402
 403         if (x.else_)                                // We got an alse
 404         {
 405             (*current)[skip] += 2;                  // adjust for the "else" jump
 406             current->op(op_jump, 0);                // we shall fill this (0) in later
 407             std::size_t exit = current->size()-1;   // mark its position
 408             if (!(*this)(*x.else_))
 409                 return false;
 410             (*current)[exit] = current->size()-exit;// now we know where to jump to (after the else branch)
 411         }
 412
 413         return true;
 414     }
 415
 416     bool compiler::operator()(ast::while_statement const& x)
 417     {
 418         BOOST_ASSERT(current != 0);
 419         std::size_t loop = current->size();         // mark our position
 420         if (!(*this)(x.condition))
 421             return false;
 422         current->op(op_jump_if, 0);                 // we shall fill this (0) in later
 423         std::size_t exit = current->size()-1;       // mark its position
 424         if (!(*this)(x.body))
 425             return false;
 426         current->op(op_jump,
 427             int(loop-1) - int(current->size()));    // loop back
 428         (*current)[exit] = current->size()-exit;    // now we know where to jump to (to exit the loop)
 429         return true;
 430     }
 431
 432     bool compiler::operator()(ast::return_statement const& x)
 433     {
 434         if (void_return)
 435         {
 436             if (x.expr)
 437             {
 438                 error_handler(x.id, "'void' function returning a value: ");
 439                 return false;
 440             }
 441         }
 442         else
 443         {
 444             if (!x.expr)
 445             {
 446                 error_handler(x.id, current_function_name + " function must return a value: ");
 447                 return false;
 448             }
 449         }
 450
 451         if (x.expr)
 452         {
 453             if (!(*this)(*x.expr))
 454                 return false;
 455         }
 456         current->op(op_return);
 457         return true;
 458     }
 459
 460     bool compiler::operator()(ast::function const& x)
 461     {
 462         void_return = x.return_type == "void";
 463         if (functions.find(x.function_name.name) != functions.end())
 464         {
 465             error_handler(x.function_name.id, "Duplicate function: " + x.function_name.name);
 466             return false;
 467         }
 468         boost::shared_ptr<code_gen::function>& p = functions[x.function_name.name];
 469         p.reset(new code_gen::function(code, x.args.size()));
 470         current = p.get();
 471         current_function_name = x.function_name.name;
 472
 473         // op_stk_adj 0 for now. we'll know how many variables
 474         // we'll have later and add them
 475         current->op(op_stk_adj, 0);
 476         BOOST_FOREACH(ast::identifier const& arg, x.args)
 477         {
 478             current->add_var(arg.name);
 479         }
 480
 481         if (!(*this)(x.body))
 482             return false;
 483         (*current)[1] = current->nvars();   // now store the actual number of variables
 484                                             // this includes the arguments
 485         return true;
 486     }
 487
 488     bool compiler::operator()(ast::function_list const& x)
 489     {
 490         // Jump to the main function
 491         code.push_back(op_jump);
 492         code.push_back(0); // we will fill this in later when we finish compiling
 493                            // and we know where the main function is
 494
 495         BOOST_FOREACH(ast::function const& f, x)
 496         {
 497             if (!(*this)(f))
 498             {
 499                 code.clear();
 500                 return false;
 501             }
 502         }
 503         // find the main function
 504         boost::shared_ptr<code_gen::function> p =
 505             find_function("main");
 506
 507         if (!p) // main function not found
 508         {
 509             std::cerr << "Error: main function not defined" << std::endl;
 510             return false;
 511         }
 512         code[1] = p->get_address()-1; // jump to this (main function) address
 513
 514         return true;
 515     }
 516
 517     void compiler::print_assembler() const
 518     {
 519         typedef std::pair<std::string, boost::shared_ptr<code_gen::function> > pair;
 520         BOOST_FOREACH(pair const& p, functions)
 521         {
 522             std::cout << ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;" << std::endl;
 523             std::cout << p.second->get_address() << ": function " << p.first << std::endl;
 524             p.second->print_assembler();
 525         }
 526     }
 527
 528     boost::shared_ptr<code_gen::function>
 529     compiler::find_function(std::string const& name) const
 530     {
 531         function_table::const_iterator i = functions.find(name);
 532         if (i == functions.end())
 533             return boost::shared_ptr<code_gen::function>();
 534         else
 535             return i->second;
 536     }
 537 }}
 538