src/ozulis/visitors/type-checker.cc

   1 #include <boost/foreach.hpp>
   2 #include <boost/format.hpp>
   3
   4 #include <ozulis/compiler.hh>
   5 #include <ozulis/core/assert.hh>
   6 #include <ozulis/ast/ast-cast.hh>
   7 #include <ozulis/ast/node-factory.hh>
   8 #include <ozulis/ast/cast-tables.hh>
   9 #include <ozulis/ast/scope.hh>
  10 #include <ozulis/visitors/type-checker.hh>
  11 #include <ozulis/visitors/browser.hh>
  12
  13 #if 0 // 1 to get a backtrace
  14 # define static
  15 #endif
  16
  17 #define CHECK(Node) Node = ctx.check(Node)
  18
  19 namespace ozulis
  20 {
  21   namespace visitors
  22   {
  23     TypeChecker::TypeChecker()
  24       : Visitor<TypeChecker>(),
  25         currentFunction(0),
  26         scope(0),
  27         replacement(0)
  28     {
  29     }
  30
  31     TypeChecker::~TypeChecker()
  32     {
  33     }
  34
  35     template <typename T>
  36     T
  37     TypeChecker::check(T node)
  38     {
  39       replacement = 0;
  40       TypeChecker::visit(*node, *this);
  41       if (!replacement)
  42         return node;
  43
  44       node = ast::ast_cast<typename T::ptr_t> (replacement.ptr());
  45       replacement = 0;
  46       return node;
  47     }
  48
  49     /** @internal keep the file's scope and visit the file */
  50     static void visitFile(ast::Node & node_, TypeChecker & ctx)
  51     {
  52       ast::File & node = reinterpret_cast<ast::File &>(node_);
  53       ctx.scope = node.scope;
  54       Browser<TypeChecker>::visit(node, ctx);
  55     }
  56
  57     static void visitFunction(ast::Node & node_, TypeChecker & ctx)
  58     {
  59       ast::Function & node = reinterpret_cast<ast::Function &>(node_);
  60       ctx.scope = node.scope;
  61       ctx.currentFunction = &node;
  62       Browser<TypeChecker>::visit(node, ctx);
  63       /// @todo check that the last statement is a branch or a return.
  64       /// maybe it should be done in the simplifier ?
  65     }
  66
  67     /** @internal get the scope, visit declarations, visit statements */
  68     static void visitBlock(ast::Node & node_, TypeChecker & ctx)
  69     {
  70       ast::Block & node = reinterpret_cast<ast::Block &>(node_);
  71       ctx.scope = node.scope;
  72       // We must respect this order
  73       BOOST_FOREACH (ast::VarDeclPtr & varDecl, (*node.varDecls))
  74         CHECK(varDecl);
  75       BOOST_FOREACH (ast::NodePtr & statement, (*node.statements))
  76         CHECK(statement);
  77     }
  78
  79     /** @internal Let's put a cast. The simplifier will  fail if the cast
  80      * is not possible */
  81     static void visitReturn(ast::Node & node_, TypeChecker & ctx)
  82     {
  83       ast::Return & node = reinterpret_cast<ast::Return &>(node_);
  84       CHECK(node.exp);
  85       node.exp = castToType(ctx.currentFunction->returnType, node.exp);
  86     }
  87
  88     /** @internal check that the type of the value is compatible with
  89      * the type of the destination. If not put a cast. */
  90     static void visitAssignExp(ast::Node & node_, TypeChecker & ctx)
  91     {
  92       ast::AssignExp & node = reinterpret_cast<ast::AssignExp &>(node_);
  93       CHECK(node.dest);
  94       CHECK(node.value);
  95
  96       ast::CastExp * castExp = new ast::CastExp();
  97       castExp->type = unreferencedType(node.dest->type);
  98       castExp->exp = node.value;
  99       node.value = castExp;
 100       node.type = castExp->type;
 101     }
 102
 103     /** @internal If the type is empty, check the symbol and assign the
 104      * type of the symbol to the node. */
 105     static void visitSymbolExp(ast::Node & node_, TypeChecker & ctx)
 106     {
 107       ast::SymbolExp & node = reinterpret_cast<ast::SymbolExp &> (node_);
 108       if (!node.type)
 109       {
 110         TypeChecker::visit(*node.symbol, ctx);
 111         node.type = node.symbol->type;
 112       }
 113     }
 114
 115     /** @internal resolve the symbol corresponding to the id. Then
 116      * create a SymbolExp, and replace IdExp by the SymbolExp */
 117     static void visitIdExp(ast::Node & node_, TypeChecker & ctx)
 118     {
 119       ast::IdExp & node = reinterpret_cast<ast::IdExp &>(node_);
 120       assert(ctx.scope);
 121       ast::Symbol * s = ctx.scope->findSymbol(node.id);
 122       assert(s);
 123       assert(s->type);
 124       assert(s->address);
 125       ast::SymbolExp * exp = new ast::SymbolExp;
 126       exp->symbol = s;
 127       exp->type = s->type;
 128       ctx.replacement = exp;
 129     }
 130
 131     /** @internal should never append: StringExp are removed by the
 132      * ScopeBuilder */
 133     static void visitStringExp(ast::Node & /*node_*/, TypeChecker & /*ctx*/)
 134     {
 135       assert_msg(false, "we should never come here");
 136     }
 137
 138     /** @internal type the expression as a pointer to the child expression.
 139      * If the child expression is typed as a reference, use the underlying
 140      * type of the reference for the type of the pointer.
 141      * It's not the role of the type checker to check if we can get the
 142      * address of the child exp. The simplifier will do this job. */
 143     static void visitAtExp(ast::Node & node_, TypeChecker & ctx)
 144     {
 145       ast::AtExp & node = reinterpret_cast<ast::AtExp &>(node_);
 146       CHECK(node.exp);
 147       ast::PointerType * type = new ast::PointerType;
 148       type->type = unreferencedType(node.exp->type);
 149       node.type = type;
 150     }
 151
 152     /** @internal obvious, will comment it later */
 153     static void visitDereferenceExp(ast::Node & node_, TypeChecker & ctx)
 154     {
 155       ast::DereferenceExp & node = reinterpret_cast<ast::DereferenceExp &>(node_);
 156       CHECK(node.exp);
 157       ast::Type * unrefType = unreferencedType(node.exp->type);
 158       if (unrefType->nodeType != ast::PointerType::nodeTypeId())
 159         Compiler::instance().error(_("you can't dereference a non pointer type"));
 160       ast::PointerType * type = ast::ast_cast<ast::PointerType *> (unrefType);
 161       node.type = type->type;
 162     }
 163
 164     /** @internal obvious, will comment it later */
 165     static void visitDereferenceByIndexExp(ast::Node & node_, TypeChecker & ctx)
 166     {
 167       ast::DereferenceByIndexExp & node =
 168         reinterpret_cast<ast::DereferenceByIndexExp &>(node_);
 169       CHECK(node.exp);
 170       CHECK(node.index);
 171       ast::Type * unrefType = unreferencedType(node.exp->type);
 172       if (unrefType->nodeType != ast::PointerType::nodeTypeId() &&
 173           unrefType->nodeType != ast::ArrayType::nodeTypeId())
 174         Compiler::instance().error(_("Error: you can't dereference a non "
 175                                      "pointer or array type"));
 176       ast::UnaryType * type = reinterpret_cast<ast::UnaryType *> (unrefType);
 177       node.type = type->type;
 178
 179       ast::IntegerType * itype = ast::NodeFactory::createUIntForPtr();
 180       node.index = castToType(itype, node.index);
 181     }
 182
 183     static void visitPointerArithExp(ast::Node & node_, TypeChecker & ctx)
 184     {
 185       ast::PointerArithExp & node = reinterpret_cast<ast::PointerArithExp &>(node_);
 186       CHECK(node.pointer);
 187       CHECK(node.offset);
 188       node.type = unreferencedType(node.pointer->type);
 189       if (node.type->nodeType != ast::PointerType::nodeTypeId())
 190         Compiler::instance().error(
 191           _("you can't do pointer arithmetics on a non pointer type"));
 192     }
 193
 194     /** @internal we should resolve named type here */
 195     static void visitSymbol(ast::Node & /*node_*/, TypeChecker & /*ctx*/)
 196     {
 197       //assert_msg(false, "should not come here");
 198     }
 199
 200     /** @internal just check the child exp */
 201     static void visitCastExp(ast::Node & node_, TypeChecker & ctx)
 202     {
 203       ast::CastExp & node = reinterpret_cast<ast::CastExp &>(node_);
 204       assert(node.exp);
 205       CHECK(node.exp);
 206     }
 207
 208     /** @internal at the begining, node.function is an IdExp. We have
 209      * to resolve the symbol. Then put casts force the right type. */
 210     static void visitCallExp(ast::Node & node_, TypeChecker & ctx)
 211     {
 212       ast::CallExp & node = reinterpret_cast<ast::CallExp &>(node_);
 213       CHECK(node.function);
 214
 215       ast::SymbolExp * sexp = ast::ast_cast<ast::SymbolExp *>(node.function);
 216       ast::FunctionType * ftype = ast::ast_cast<ast::FunctionType *>(sexp->symbol->type);
 217
 218       node.type = ftype->type;
 219       assert(ftype->argsType->size() >= node.args->size());
 220       for (unsigned i = 0; i < node.args->size(); i++)
 221       {
 222         CHECK((*node.args)[i]);
 223         (*node.args)[i] = castToType((*ftype->argsType)[i], (*node.args)[i]);
 224       }
 225     }
 226
 227     /** @internal
 228      * 1) find the best type
 229      * 2) find the "bad" member and use the cast for it */
 230     void
 231     TypeChecker::homogenizeTypes(ast::BinaryExp & node)
 232     {
 233       ast::CastExp * castExp = ast::castToBestType(node.left->type,
 234                                                    node.right->type);
 235       if (!castExp)
 236       {
 237         node.type = unreferencedType(node.left->type);
 238         return;
 239       }
 240
 241       if (castExp->type == unreferencedType(node.left->type))
 242       {
 243         castExp->exp = node.right;
 244         node.right = castExp;
 245       }
 246       else
 247       {
 248         castExp->exp = node.left;
 249         node.left = castExp;
 250       }
 251       node.type = castExp->type;
 252     }
 253
 254     /**
 255      * @internal
 256      *  - compute the new address:
 257      *   - addrui = ptrtoui addr
 258      *   - offset = index * sizeof(*addr)
 259      *   - newaddrui = ptrtoui + offset
 260      *   - newaddr = cast(*, newaddrui)
 261      */
 262     void
 263     TypeChecker::pointerArith(ast::Exp * pointer, ast::Exp * offset)
 264     {
 265 #if 0 /// move this to the simplifier or use getelementptr ?
 266       ast::PointerType * pointerType =
 267         ast::ast_cast<ast::PointerType *> (unreferencedType(pointer->type));
 268
 269       /* cast node.exp to uint */
 270       ast::CastExp * cast1 = ast::NodeFactory::createCastPtrToUInt(pointer);
 271
 272       /* compute the offset */
 273       ast::MulExp * mul = new ast::MulExp;
 274       mul->left = offset;
 275       mul->right = ast::NodeFactory::createSizeofValue(pointerType->type);
 276
 277       /* add the offset to the uint addr */
 278       ast::AddExp * add = new ast::AddExp;
 279       add->left = cast1;
 280       add->right = mul;
 281
 282       /* cast uint addr to ptr */
 283       ast::CastExp * cast2 = ast::NodeFactory::
 284         createCastUIntToPtr(add, unreferencedType(pointerType));
 285       check(cast2);
 286
 287       replacement = cast2;
 288 #endif
 289
 290       ast::PointerArithExp * exp = new ast::PointerArithExp;
 291       exp->pointer = pointer;
 292       exp->offset = offset;
 293       exp->type = unreferencedType(pointer->type);
 294       replacement = exp;
 295     }
 296
 297 /** @internal there is a particular case here for pointer arithmetics */
 298 #define VISIT_ADD_EXP(Type)                                             \
 299     static void visit##Type(ast::Node & node_, TypeChecker & ctx)       \
 300     {                                                                   \
 301       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 302       CHECK(node.left);                                                 \
 303       CHECK(node.right);                                                \
 304       if (unreferencedType(node.left->type)->nodeType ==                \
 305           ast::PointerType::nodeTypeId())                               \
 306         ctx.pointerArith(node.left, node.right);                        \
 307       else if (unreferencedType(node.right->type)->nodeType ==          \
 308                ast::PointerType::nodeTypeId())                          \
 309         ctx.pointerArith(node.right, node.left);                        \
 310       else                                                              \
 311         TypeChecker::homogenizeTypes(node);                             \
 312     }
 313
 314 #define VISIT_BINARY_ARITH(Type)                                        \
 315     static void visit##Type(ast::Node & node_, TypeChecker & ctx)       \
 316     {                                                                   \
 317       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 318       CHECK(node.left);                                                 \
 319       CHECK(node.right);                                                \
 320       TypeChecker::homogenizeTypes(node);                               \
 321     }
 322
 323     VISIT_ADD_EXP(AddExp)
 324     VISIT_ADD_EXP(SubExp)
 325     VISIT_BINARY_ARITH(MulExp)
 326     VISIT_BINARY_ARITH(DivExp)
 327     VISIT_BINARY_ARITH(ModExp)
 328
 329 #define VISIT_BITWISE_EXP(Type)                                         \
 330     static void visit##Type(ast::Node & node_, TypeChecker & ctx)       \
 331     {                                                                   \
 332       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 333       CHECK(node.left);                                                 \
 334       CHECK(node.right);                                                \
 335                                                                         \
 336       if (AST_IS_FLOATING_POINT_TYPE(node.left->type) ||                \
 337           AST_IS_FLOATING_POINT_TYPE(node.right->type))                 \
 338       {                                                                 \
 339         Compiler::instance().error(_("you can't do bitwise operation with " \
 340                                      "floating point value."));         \
 341       }                                                                 \
 342       TypeChecker::homogenizeTypes(node);                               \
 343     }
 344
 345     VISIT_BITWISE_EXP(AndExp)
 346     VISIT_BITWISE_EXP(OrExp)
 347     VISIT_BITWISE_EXP(XorExp)
 348
 349     VISIT_BITWISE_EXP(ShlExp)
 350     VISIT_BITWISE_EXP(AShrExp)
 351     VISIT_BITWISE_EXP(LShrExp)
 352
 353 #define VISIT_BINARY_CMP_EXP(Type)                                      \
 354     static void visit##Type(ast::Node & node_, TypeChecker & ctx)       \
 355     {                                                                   \
 356       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 357       CHECK(node.left);                                                 \
 358       CHECK(node.right);                                                \
 359       /**                                                               \
 360        * @todo check if type match                                      \
 361        * @todo look for an overloaded operator '+'                      \
 362        * @todo the cast can be applied on both nodes                    \
 363        */                                                               \
 364       TypeChecker::homogenizeTypes(node);                               \
 365       node.type = ast::NodeFactory::createBoolType();                   \
 366     }
 367
 368     VISIT_BINARY_CMP_EXP(EqExp)
 369     VISIT_BINARY_CMP_EXP(NeqExp)
 370     VISIT_BINARY_CMP_EXP(LtExp)
 371     VISIT_BINARY_CMP_EXP(LtEqExp)
 372     VISIT_BINARY_CMP_EXP(GtExp)
 373     VISIT_BINARY_CMP_EXP(GtEqExp)
 374
 375 #define VISIT_BINARY_BOOL_EXP(Type)                                     \
 376     static void visit##Type(ast::Node & node_, TypeChecker & ctx)       \
 377     {                                                                   \
 378       ast::Type & node = reinterpret_cast<ast::Type &> (node_);         \
 379       node.type = ast::NodeFactory::createBoolType();                   \
 380                                                                         \
 381       CHECK(node.left);                                                 \
 382       CHECK(node.right);                                                \
 383                                                                         \
 384       if (AST_IS_FLOATING_POINT_TYPE(node.left->type) ||                \
 385           AST_IS_FLOATING_POINT_TYPE(node.right->type))                 \
 386       {                                                                 \
 387         Compiler::instance().error(_("you can't do bitwise operation with " \
 388                                      "floating point value."));         \
 389       }                                                                 \
 390       node.left = castToType(node.type, node.left);                     \
 391       node.right = castToType(node.type, node.right);                   \
 392     }
 393
 394     VISIT_BINARY_BOOL_EXP(OrOrExp)
 395     VISIT_BINARY_BOOL_EXP(AndAndExp)
 396
 397     static void visitNegExp(ast::Node & node_, TypeChecker & ctx)
 398     {
 399       ast::NegExp & node = reinterpret_cast<ast::NegExp &>(node_);
 400       CHECK(node.exp);
 401       node.type = node.exp->type;
 402     }
 403
 404     static void visitNotExp(ast::Node & node_, TypeChecker & ctx)
 405     {
 406       ast::NotExp & node = reinterpret_cast<ast::NotExp &>(node_);
 407       CHECK(node.exp);
 408       if (AST_IS_FLOATING_POINT_TYPE(node.exp->type))
 409         Compiler::instance().error(_("you can't do bitwise operation with "
 410                                      "floating point value."));
 411       node.type = node.exp->type;
 412     }
 413
 414     static void visitBangExp(ast::Node & node_, TypeChecker & ctx)
 415     {
 416       ast::BangExp & node = reinterpret_cast<ast::BangExp &>(node_);
 417       CHECK(node.exp);
 418       if (AST_IS_FLOATING_POINT_TYPE(node.exp->type))
 419         Compiler::instance().error(_("you can't do bitwise operation with "
 420                                      "floating point value."));
 421       node.type = ast::NodeFactory::createBoolType();
 422       node.exp = castToType(node.type, node.exp);
 423     }
 424
 425     static void visitConditionalBranch(ast::Node & node_, TypeChecker & ctx)
 426     {
 427       ast::ConditionalBranch & node = reinterpret_cast<ast::ConditionalBranch &>(node_);
 428       CHECK(node.cond);
 429       node.cond = castToType(ast::NodeFactory::createBoolType(), node.cond);
 430     }
 431
 432     void
 433     TypeChecker::initBase()
 434     {
 435 #define REGISTER_METHOD(Class)                                  \
 436       registerMethod(ast::Class::nodeTypeId(), visit##Class)
 437
 438       REGISTER_METHOD(AssignExp);
 439
 440       REGISTER_METHOD(AddExp);
 441       REGISTER_METHOD(SubExp);
 442       REGISTER_METHOD(MulExp);
 443       REGISTER_METHOD(DivExp);
 444       REGISTER_METHOD(ModExp);
 445
 446       REGISTER_METHOD(AndExp);
 447       REGISTER_METHOD(OrExp);
 448       REGISTER_METHOD(XorExp);
 449
 450       REGISTER_METHOD(ShlExp);
 451       REGISTER_METHOD(AShrExp);
 452       REGISTER_METHOD(LShrExp);
 453
 454       REGISTER_METHOD(OrOrExp);
 455       REGISTER_METHOD(AndAndExp);
 456
 457       REGISTER_METHOD(EqExp);
 458       REGISTER_METHOD(NeqExp);
 459       REGISTER_METHOD(LtExp);
 460       REGISTER_METHOD(LtEqExp);
 461       REGISTER_METHOD(GtExp);
 462       REGISTER_METHOD(GtEqExp);
 463
 464       REGISTER_METHOD(NotExp);
 465       REGISTER_METHOD(NegExp);
 466       REGISTER_METHOD(BangExp);
 467
 468       REGISTER_METHOD(IdExp);
 469       REGISTER_METHOD(SymbolExp);
 470       REGISTER_METHOD(StringExp);
 471       REGISTER_METHOD(AtExp);
 472       REGISTER_METHOD(DereferenceExp);
 473       REGISTER_METHOD(DereferenceByIndexExp);
 474       REGISTER_METHOD(PointerArithExp);
 475       REGISTER_METHOD(CastExp);
 476       REGISTER_METHOD(CallExp);
 477
 478       REGISTER_METHOD(Symbol);
 479
 480       REGISTER_METHOD(File);
 481       REGISTER_METHOD(Function);
 482       REGISTER_METHOD(Block);
 483
 484       REGISTER_METHOD(Return);
 485
 486       REGISTER_METHOD(ConditionalBranch);
 487
 488       completeWith<Browser<TypeChecker> >();
 489     }
 490   }
 491 }