path: root/tiger-compiler/src/type/type-checker.cc

/**
 ** \file type/type-checker.cc
 ** \brief Implementation for type/type-checker.hh.
 */

#include <memory>
#include <boost/iterator/zip_iterator.hpp>
#include <misc/contract.hh>

#include <ast/all.hh>
#include <type/type-checker.hh>
#include <type/types.hh>

namespace type
{
  TypeChecker::TypeChecker()
    : super_type()
    , error_()
  {}

  const Type* TypeChecker::type(ast::Typable& e)
  {
    // FIXME DONE: Some code was deleted here.
    if (e.type_get() == nullptr)
      e.accept(*this);
    return e.type_get();
  }

  const Record* TypeChecker::type(const ast::fields_type& e)
  {
    const auto res = new Record;
    // FIXME DONE: Some code was deleted here.
    for (const auto& var : e)
      {
        if (res->field_index(var->name_get()) != -1)
          {
            error(*var,
                  var->name_get().get()
                    + " attribute is already present in record");
          }

        res->field_add(var->name_get(), *type(var->type_name_get()));
      }
    return res;
  }

  const Record* TypeChecker::type(const ast::VarChunk& e)
  {
    const auto res = new Record;

    for (const auto& var : e)
      {
        res->field_add(var->name_get(), *type(*var));
      }

    return res;
  }

  const misc::error& TypeChecker::error_get() const { return error_; }

  /*-----------------.
  | Error handling.  |
  `-----------------*/

  void TypeChecker::error(const ast::Ast& ast, const std::string& msg)
  {
    error_ << misc::error::error_type::type << ast.location_get() << ": " << msg
           << std::endl;
  }

  void TypeChecker::type_mismatch(const ast::Ast& ast,
                                  const std::string& exp1,
                                  const Type& type1,
                                  const std::string& exp2,
                                  const Type& type2)
  {
    error_ << misc::error::error_type::type << ast.location_get()
           << ": type mismatch" << misc::incendl << exp1 << " type: " << type1
           << misc::iendl << exp2 << " type: " << type2 << misc::decendl;
  }

  void TypeChecker::check_types(const ast::Ast& loc,
                                const std::string& exp1,
                                const Type& type1,
                                const std::string& exp2,
                                const Type& type2)
  {
    // FIXME DONE: Some code was deleted here (Check for type mismatch).
    if (!type1.actual().compatible_with(type2.actual()))
      type_mismatch(loc, exp1, type1, exp2, type2);

    // If any of the type is Nil, set its `record_type_` to the other type.
    if (!error_)
      {
        // FIXME DONE: Some code was deleted here.
        if (auto nil = dynamic_cast<const Nil*>(&type1); nil != nullptr)
          nil->record_type_set(type2);
        else if (nil = dynamic_cast<const Nil*>(&type2); nil != nullptr)
          nil->record_type_set(type1);
      }
  }

  void TypeChecker::check_types(const ast::Ast& ast,
                                const std::string& exp1,
                                ast::Typable& type1,
                                const std::string& exp2,
                                ast::Typable& type2)
  {
    // Ensure evaluation order.
    type(type1);
    type(type2);
    // FIXME DONE: Some code was deleted here (Check types).
    check_types(ast, exp1, *type1.type_get(), exp2, *type2.type_get());
  }

  /*--------------------------.
  | The core of the visitor.  |
  `--------------------------*/

  /*-----------------.
  | Visiting /Var/.  |
  `-----------------*/

  void TypeChecker::operator()(ast::SimpleVar& e)
  {
    // FIXME DONE: Some code was deleted here.
    // It is assumed SimpleVar references a variable that has already been typed
    precondition(e.def_get()->type_get() != nullptr);
    type_default(e, e.def_get()->type_get());
  }

  // FIXME DONE: Some code was deleted here.

  void TypeChecker::operator()(ast::FieldVar& e)
  {
    const auto record =
      dynamic_cast<const Record*>(&type(e.var_get())->actual());

    if (record == nullptr)
      {
        error(e.var_get(), "variable is not a record");
        type_default(e, &default_type);
        return;
      }

    const int index = record->field_index(e.name_get());

    if (index < 0)
      {
        error(e,
              e.name_get().get() + " attribute does not exist within record");
        type_default(e, &default_type);
        return;
      }

    const Type& type = record->fields_get().at(index).type_get();

    type_default(e, &type);
  }

  void TypeChecker::operator()(ast::SubscriptVar& e)
  {
    check_type(e.index_get(), "array subscript value", Int::instance());

    auto array = dynamic_cast<const Array*>(&type(e.var_get())->actual());
    if (array == nullptr)
      {
        error(e, "index does not reference an array");
        type_default(e, &default_type);
      }
    else
      {
        type_default(e, array->get_element_type());
      }
  }

  /*-----------------.
  | Visiting /Exp/.  |
  `-----------------*/

  // Literals.
  void TypeChecker::operator()(ast::NilExp& e)
  {
    auto nil_ptr = std::make_unique<Nil>();
    type_default(e, nil_ptr.get());
    created_type_default(e, nil_ptr.release());
  }

  void TypeChecker::operator()(ast::IntExp& e)
  {
    // FIXME DONE: Some code was deleted here.
    type_default(e, &Int::instance());
  }

  void TypeChecker::operator()(ast::StringExp& e)
  {
    // FIXME DONE: Some code was deleted here.
    type_default(e, &String::instance());
  }

  // Complex values.

  void TypeChecker::operator()(ast::RecordExp& e)
  {
    // FIXME DONE: Some code was deleted here.

    const Type* named_record = type(e.type_name_get());
    const auto record = dynamic_cast<const Record*>(&named_record->actual());

    assertion(record != nullptr);

    // everything must be typed first !
    for (const auto field : e.fields_get())
      {
        type(field->init_get());
      }

    if (e.fields_get().size() != record->fields_get().size())
      {
        error(e, std::string("insufficient amount of arguments"));
      }
    else
      {
        auto record_fields = record->fields_get();
        auto exp_fields = e.fields_get();

        std::for_each(
          boost::make_zip_iterator(
            boost::make_tuple(record_fields.begin(), exp_fields.begin())),
          boost::make_zip_iterator(
            boost::make_tuple(record_fields.end(), exp_fields.end())),
          [this](const boost::tuple<Field&, ast::FieldInit*>& params) {
            const misc::symbol& expected_name = params.get<0>().name_get();
            const Type& expected_type = params.get<0>().type_get();

            const misc::symbol& actual_name = params.get<1>()->name_get();
            const ast::Exp& actual_node = params.get<1>()->init_get();

            if (expected_name != actual_name)
              {
                error(actual_node,
                      std::string("name mismatch: expected "
                                  + expected_name.get() + " but got "
                                  + actual_name.get()));
              }

            check_types(actual_node, expected_name.get() + " actual",
                        *actual_node.type_get(),
                        expected_name.get() + "expected", expected_type);
          });
      }

    type_default(e, named_record);
  }

  void TypeChecker::operator()(ast::OpExp& e)
  {
    // FIXME DONE: Some code was deleted here.

    ast::OpExp::Oper oper = e.oper_get();
    type(e.left_get());
    type(e.right_get());

    check_types(e, "left operand", *e.left_get().type_get(), "right operand",
                *e.right_get().type_get());

    if (const auto comparaison_type = &e.left_get().type_get()->actual();
        (oper < ast::OpExp::Oper::eq || oper > ast::OpExp::Oper::ne)
        && (dynamic_cast<const Int*>(comparaison_type) == nullptr
            && dynamic_cast<const String*>(comparaison_type) == nullptr))
      {
        error_ << misc::error::error_type::type << e.location_get()
               << ": type mismatch" << misc::incendl
               << "order operations are only possible on int and string, not "
               << *comparaison_type << misc::decendl;
      }

    type_default(e, &Int::instance());
  }

  // FIXME DONE: Some code was deleted here.

  void TypeChecker::operator()(ast::ArrayExp& e)
  {
    // Typing order
    type(e.type_name_get());
    type(e.size_get());
    type(e.init_get());

    const Type* actual_type = e.type_name_get().type_get();
    const auto array_type = dynamic_cast<const Array*>(&actual_type->actual());

    if (array_type == nullptr)
      {
        error(e.type_name_get(), "type does not reference an array");
        type_default(e, &default_type);
        return;
      }

    check_type(e.size_get(), "array size", Int::instance());
    check_types(e, "array element", *array_type->get_element_type(),
                "initializer", *e.init_get().type_get());

    type_default(e, actual_type);
  }

  void TypeChecker::operator()(ast::AssignExp& e)
  {
    check_types(e, "variable", e.var_get(), "value", e.exp_get());

    if (auto svar = dynamic_cast<ast::SimpleVar*>(&e.var_get());
        svar && var_read_only_.find(svar->def_get()) != var_read_only_.end())
      error(e, "variable is read-only");

    type_default(e, &Void::instance());
  }

  void TypeChecker::operator()(ast::BreakExp& e)
  {
    type_default(e, &Void::instance());
  }

  void TypeChecker::operator()(ast::CallExp& e)
  {
    for (ast::Exp* exp : e.args_get())
      {
        type(*exp);
      }

    const auto actual_params = e.args_get();
    const auto expected_params = e.def_get()->formals_get().decs_get();

    if (actual_params.size() != expected_params.size())
      {
        error(e,
              std::string(std::to_string(expected_params.size())
                          + " parameters expected but got "
                          + std::to_string(actual_params.size())));
      }
    else
      {
        std::for_each(
          boost::make_zip_iterator(
            boost::make_tuple(expected_params.begin(), actual_params.begin())),
          boost::make_zip_iterator(
            boost::make_tuple(expected_params.end(), actual_params.end())),
          [this, &e](const boost::tuple<ast::VarDec*, ast::Exp*>& params) {
            check_types(e, "expected", *params.get<0>(), "actual",
                        *params.get<1>());
          });
      }

    type_default(
      e, &dynamic_cast<const Function*>(e.def_get()->type_get())->result_get());
  }

  void TypeChecker::operator()(ast::CastExp& e)
  {
    check_types(e, "target", e.ty_get(), "value", e.exp_get());

    created_type_default(e, e.ty_get().type_get());
  }

  void TypeChecker::operator()(ast::ForExp& e)
  {
    check_types(e, "iterator", e.vardec_get(), "high bound", e.hi_get());

    check_type(e.hi_get(), "high bound", Int::instance());

    var_read_only_.insert(&e.vardec_get());

    check_type(e.body_get(), "for body", Void::instance());

    /* Break cannot be used in assignments */
    const auto iterator_node =
      dynamic_cast<const ast::IntExp*>(e.vardec_get().init_get());
    const auto hi_node = dynamic_cast<const ast::IntExp*>(&e.hi_get());

    if (iterator_node != nullptr && hi_node != nullptr
        && iterator_node->value_get() > hi_node->value_get())
      {
        error(e.vardec_get(), "iterator initial value is higher than limit");
      }

    type_default(e, e.body_get().type_get());
  }

  void TypeChecker::operator()(ast::IfExp& e)
  {
    check_type(e.test_get(), "condition", Int::instance());

    check_types(e, "then chunk return", e.thenclause_get(), "else chunk return",
                e.elseclause_get());

    type_default(e, e.elseclause_get().type_get());
  }

  void TypeChecker::operator()(ast::LetExp& e)
  {
    e.chunks_get().accept(*this);

    type_default(e, type(e.body_get()));
  }

  void TypeChecker::operator()(ast::SeqExp& e)
  {
    if (e.exps_get().empty())
      {
        type_default(e, &Void::instance());
        return;
      }

    for (ast::Exp* exp : e.exps_get())
      {
        type(*exp);
      }

    type_default(e, e.exps_get().back()->type_get());
  }

  void TypeChecker::operator()(ast::WhileExp& e)
  {
    check_type(e.test_get(), "condition", Int::instance());

    check_type(e.body_get(), "while body", Void::instance());

    type_default(e, e.body_get().type_get());
  }

  /*-----------------.
  | Visiting /Dec/.  |
  `-----------------*/

  /*------------------------.
  | Visiting FunctionChunk. |
  `------------------------*/

  void TypeChecker::operator()(ast::FunctionChunk& e)
  {
    chunk_visit<ast::FunctionDec>(e);
  }

  void TypeChecker::operator()(ast::FunctionDec&)
  {
    // We must not be here.
    unreachable();
  }

  // Store the type of this function.
  template <>
  void TypeChecker::visit_dec_header<ast::FunctionDec>(ast::FunctionDec& e)
  {
    // FIXME DONE: Some code was deleted here.
    // Typing order
    const Record* formals = type(e.formals_get());

    const Type* return_type =
      e.result_get() != nullptr ? type(*e.result_get()) : &Void::instance();

    auto type = std::make_unique<Function>(formals, *return_type);

    type_default(e, type.get());
    created_type_default(e, type.release());
  }

  // Type check this function's body.
  template <>
  void TypeChecker::visit_dec_body<ast::FunctionDec>(ast::FunctionDec& e)
  {
    visit_routine_body<Function, ast::FunctionDec>(e);
  }

  /*---------------.
  | Visit VarDec.  |
  `---------------*/

  void TypeChecker::operator()(ast::VarDec& e)
  {
    // FIXME DONE: Some code was deleted here.
    const Type* declared_type =
      e.type_name_get() != nullptr ? type(*e.type_name_get()) : nullptr;

    const Type* actual_type =
      e.init_get() != nullptr ? type(*e.init_get()) : nullptr;

    if (actual_type != nullptr && actual_type->actual() == Void::instance())
      {
        error(e, "VarDec type cannot be void");
        actual_type = &default_type;
      }

    if (declared_type == nullptr)
      {
        if (actual_type != nullptr
            && dynamic_cast<const Nil*>(&actual_type->actual()) != nullptr)
          {
            error(e, "Nil cannot be used with anonymous type declaration");
          }

        type_default(e, actual_type);
      }
    else
      {
        if (actual_type != nullptr)
          check_types(e, "explicit variable declaration", *declared_type,
                      "init expression", *actual_type);

        type_default(e, declared_type);
      }
  }

  /*--------------------.
  | Visiting TypeChunk. |
  `--------------------*/

  void TypeChecker::operator()(ast::TypeChunk& e)
  {
    chunk_visit<ast::TypeDec>(e);
  }

  void TypeChecker::operator()(ast::TypeDec&)
  {
    // We must not be here.
    unreachable();
  }

  // Store this type.
  template <> void TypeChecker::visit_dec_header<ast::TypeDec>(ast::TypeDec& e)
  {
    // We only process the head of the type declaration, to set its
    // name in E.  A declaration has no type in itself; here we store
    // the type declared by E.
    // FIXME DONE: Some code was deleted here.
    if (e.type_get() != nullptr)
      {
        return;
      }

    auto type = std::make_unique<Named>(e.name_get());

    type_default(e, type.get());
    created_type_default(e, type.release());
  }

  // Bind the type body to its name.
  template <> void TypeChecker::visit_dec_body<ast::TypeDec>(ast::TypeDec& e)
  {
    // FIXME DONE: Some code was deleted here.
    const auto named = dynamic_cast<const Named*>(e.type_get());

    assertion(named != nullptr);

    named->type_set(type(e.ty_get()));

    if (!named->sound())
      {
        error(e, "infinite type reference recursion detected");
      }
  }

  /*------------------.
  | Visiting /Chunk/. |
  `------------------*/

  template <class D> void TypeChecker::chunk_visit(ast::Chunk<D>& e)
  {
    // FIXME DONE: Some code was deleted here.
    if (auto var = dynamic_cast<ast::VarDec*>(e.decs_get().front());
        var != nullptr)
      {
        type(*var);
        return;
      }

    for (D* declaration : e)
      {
        visit_dec_header(*declaration);
      }

    for (D* declaration : e)
      {
        visit_dec_body(*declaration);
      }

    for (D* declaration : e)
      {
        if (const auto maybe_main =
              dynamic_cast<ast::FunctionDec*>(declaration);
            maybe_main != nullptr && maybe_main->name_get() == "_main")
          type_main(maybe_main);
      }
  }

  void TypeChecker::type_main(ast::FunctionDec* const e)
  {
    if (!e->formals_get().decs_get().empty())
      {
        error(*e, "_main function should have no arguments");
      }

    check_type(*e->body_get(), "_main return type", Void::instance());
  }

  /*-------------.
  | Visit /Ty/.  |
  `-------------*/

  void TypeChecker::operator()(ast::NameTy& e)
  {
    // FIXME DONE: Some code was deleted here (Recognize user defined types, and built-in types).
    const Type* type = e.name_get() == "int" ? &Int::instance()
      : e.name_get() == "string"             ? &String::instance()
                                             : this->type(*e.def_get());

    auto named = std::make_unique<Named>(e.name_get(), type);

    type_default(e, named.get());
    created_type_default(e, named.release());
  }

  void TypeChecker::operator()(ast::RecordTy& e)
  {
    // FIXME DONE: Some code was deleted here.
    std::unique_ptr<const Record> record(type(e.fields_get()));

    type_default(e, record.get());
    created_type_default(e, record.release());
  }

  void TypeChecker::operator()(ast::ArrayTy& e)
  {
    // FIXME DONE: Some code was deleted here.
    auto array = std::make_unique<const Array>(type(e.base_type_get()));

    type_default(e, array.get());
    created_type_default(e, array.release());
  }

} // namespace type