diff options
Diffstat (limited to 'tiger-compiler/src/type')
48 files changed, 3229 insertions, 0 deletions
diff --git a/tiger-compiler/src/type/README.txt b/tiger-compiler/src/type/README.txt new file mode 100644 index 0000000..12bc011 --- /dev/null +++ b/tiger-compiler/src/type/README.txt @@ -0,0 +1,92 @@ +* README + +Hierarchy of types for the Tiger language, with (most of) their +interfaces. + + +ostream& operator<<(ostream& ostr, const Type& t) +bool operator==(const Type& lhs, const Type& rhs); +bool operator!=(const Type& lhs, const Type& rhs); + +/Type/ + virtual ~Type() {} + virtual const Type& actual() const; + virtual bool compatible_with(const Type& other) const; + virtual void accept(ConstVisitor& v) const; + virtual void accept(Visitor& v); + + Nil + bool compatible_with(const Type& other) const override; + const Type* record_type_get() const; + void set_record_type(const Type& type) const; + + Void + + Int + + String + + Named(misc::symbol name, const Type* type) + const Type* type_get() const; + void type_set(const Type *type) const; + misc::symbol name_get() const; + void name_set(misc::symbol name); + const Type& actual() const override; + const bool sound() const; + bool compatible_with(const Type& other) const override; + + Array(const Type& type) + const Type& type_get() const; + + Record() + const Type* field_type(misc::symbol key) const; + int field_index(misc::symbol key) const; + const list<Field> fields_get() const; + void field_add(const Field& field); + void field_add(misc::symbol name, const Type& type); + const_iterator begin() const; + const_iterator end() const; + + Class(const Class* super = nullptr) + const Type* attr_type(misc::symbol key) const; + const Type* meth_type(misc::symbol key) const; + const attrs_type& attrs_get() const; + const meths_type& meths_get() const; + const Attribute* attr_find(misc::symbol key) const; + const Attribute* owner_attr_find(misc::symbol key) const; + const Method* owned_meth_find(misc::symbol key) const; + void attr_add(const Attribute& attr); + void attr_add(const VarDec* def); + void meth_add(const Method* method); + bool has_data() const; + unsigned id_get() const; + const Class* super_get() const; + void super_set(const Class* type); + const subclasses_type& subclasses_get() const; + void subclass_add(const Class* subclass) const; + void subclasses_clear() const; + const Class* common_root(const Class& other) const; + bool sound() const; + static const Class& object_instance(); + + Function(const Record* formals, const Type& result) + + Method(misc::symbol name, const Class* owner, const Record* formals, + const Type& result, MethodDec* def) + misc::symbol name_get() const; + const Class* owner_get() const; + const Type& type_get() const; + const MethodDec* def_get() const; + MethodDec* def_get(); + void name_set(misc::symbol name); + void def_set(MethodDec* def); + +Field(misc::symbol name, const Type& type) + misc::symbol name_get() const; + const Type& type_get() const; + +Attribute(const ast::VarDec* def) + misc::symbol name_get() const; + const Type& type_get() const; + const ast::VarDec* def_get() const; + void def_set(const ast::VarDec* def); diff --git a/tiger-compiler/src/type/array.cc b/tiger-compiler/src/type/array.cc new file mode 100644 index 0000000..1cf51ca --- /dev/null +++ b/tiger-compiler/src/type/array.cc @@ -0,0 +1,28 @@ +/** + ** \file type/array.cc + ** \brief Implementation for type/array.hh. + */ + +#include <type/array.hh> +#include <type/visitor.hh> + +namespace type +{ + + // FIXME DONE: Some code was deleted here. + + Array::Array(const Type* const element_type) + : element_type_(element_type) + {} + + void Array::accept(ConstVisitor& v) const + { + v(*this); + } + + void Array::accept(Visitor& v) + { + v(*this); + } + +} // namespace type diff --git a/tiger-compiler/src/type/array.hh b/tiger-compiler/src/type/array.hh new file mode 100644 index 0000000..417eeee --- /dev/null +++ b/tiger-compiler/src/type/array.hh @@ -0,0 +1,30 @@ +/** + ** \file type/array.hh + ** \brief The class Array. + */ +#pragma once + +#include <type/fwd.hh> +#include <type/type.hh> + +namespace type +{ + /// Array types. + class Array : public Type + { + // FIXME DONE: Some code was deleted here. + public: + Array(const Type* element_type); + + void accept(ConstVisitor& v) const override; + void accept(Visitor& v) override; + + inline const Type* get_element_type() const; + + protected: + const Type* const element_type_; + }; + +} // namespace type + +#include <type/array.hxx> diff --git a/tiger-compiler/src/type/array.hxx b/tiger-compiler/src/type/array.hxx new file mode 100644 index 0000000..1ed65da --- /dev/null +++ b/tiger-compiler/src/type/array.hxx @@ -0,0 +1,18 @@ +/** + ** \file type/array.hxx + ** \brief Inline methods for type::Array. + */ +#pragma once + +#include <misc/contract.hh> +#include <type/array.hh> + +namespace type +{ + // FIXME DONE: Some code was deleted here. + inline const Type* Array::get_element_type() const + { + return element_type_; + } + +} // namespace type diff --git a/tiger-compiler/src/type/attribute.cc b/tiger-compiler/src/type/attribute.cc new file mode 100644 index 0000000..bfbe537 --- /dev/null +++ b/tiger-compiler/src/type/attribute.cc @@ -0,0 +1,16 @@ +/** + ** \file type/attribute.cc + ** \brief Implementation for type/attribute.hh. + */ + +#include <ostream> + +#include <type/attribute.hh> + +namespace type +{ + Attribute::Attribute(const ast::VarDec* def) + : def_(def) + {} + +} // namespace type diff --git a/tiger-compiler/src/type/attribute.hh b/tiger-compiler/src/type/attribute.hh new file mode 100644 index 0000000..d252da4 --- /dev/null +++ b/tiger-compiler/src/type/attribute.hh @@ -0,0 +1,44 @@ +/** + ** \file type/attribute.hh + ** \brief The class Attribute (of a class type). + */ +#pragma once + +#include <ast/var-dec.hh> + +namespace type +{ + + /** \brief The base object for Class attributes. + ** + ** Very much like Named, but it is *not* a Type. */ + class Attribute + { + /** \name Constructor. + ** \{ */ + public: + /** \brief Construct a Attribute. + ** \param def attribute's definition site.*/ + explicit Attribute(const ast::VarDec* def); + /** \} */ + + /** \name Accessors. + ** \{ */ + public: + /// Return the attribute's name. + misc::symbol name_get() const; + /// Return the attribute's type. + const Type& type_get() const; + /// Return attribute's definition site. + const ast::VarDec* def_get() const; + /// Set the attribute's definition site. + void def_set(const ast::VarDec* def); + /** \} */ + + private: + const ast::VarDec* def_; + }; + +} // namespace type + +#include <type/attribute.hxx> diff --git a/tiger-compiler/src/type/attribute.hxx b/tiger-compiler/src/type/attribute.hxx new file mode 100644 index 0000000..e59177d --- /dev/null +++ b/tiger-compiler/src/type/attribute.hxx @@ -0,0 +1,25 @@ +/** + ** \file type/attribute.hxx + ** \brief Inline methods for type::Attribute. + */ +#pragma once + +#include <misc/contract.hh> + +namespace type +{ + inline misc::symbol Attribute::name_get() const { return def_->name_get(); } + + inline const Type& Attribute::type_get() const + { + // FIXME DONE: Some code was deleted here. + precondition(def_->type_get() != nullptr); + + return *def_->type_get(); + } + + inline const ast::VarDec* Attribute::def_get() const { return def_; } + + inline void Attribute::def_set(const ast::VarDec* def) { def_ = def; } + +} // namespace type diff --git a/tiger-compiler/src/type/builtin-types.cc b/tiger-compiler/src/type/builtin-types.cc new file mode 100644 index 0000000..7ea70ad --- /dev/null +++ b/tiger-compiler/src/type/builtin-types.cc @@ -0,0 +1,22 @@ +/** + ** \file type/builtin-types.cc + ** \brief Implementation for type/builtin-types.hh. + */ + +#include <ostream> + +#include <type/builtin-types.hh> +#include <type/visitor.hh> + +namespace type +{ + // FIXME DONE: Some code was deleted here (Int, String, Void). + void Int::accept(ConstVisitor& v) const { v(instance()); } + void Int::accept(Visitor& v) { v(instance()); } + + void Void::accept(ConstVisitor& v) const { v(instance()); } + void Void::accept(Visitor& v) { v(instance()); } + + void String::accept(ConstVisitor& v) const { v(instance()); } + void String::accept(Visitor& v) { v(instance()); } +} // namespace type diff --git a/tiger-compiler/src/type/builtin-types.hh b/tiger-compiler/src/type/builtin-types.hh new file mode 100644 index 0000000..40295eb --- /dev/null +++ b/tiger-compiler/src/type/builtin-types.hh @@ -0,0 +1,40 @@ +/** + ** \file type/builtin-types.hh + ** \brief The classes Int, String, Void. + */ +#pragma once + +#include <misc/singleton.hh> +#include <type/fwd.hh> +#include <type/type.hh> + +namespace type +{ + // FIXME DONE: Some code was deleted here (Other types : Int, String, Void). + + class Int + : public Type + , public misc::Singleton<Int> + { + public: + void accept(ConstVisitor& v) const override; + void accept(Visitor& v) override; + }; + class Void + : public Type + , public misc::Singleton<Void> + { + public: + void accept(ConstVisitor& v) const override; + void accept(Visitor& v) override; + }; + class String + : public Type + , public misc::Singleton<String> + { + public: + void accept(ConstVisitor& v) const override; + void accept(Visitor& v) override; + }; + +} // namespace type diff --git a/tiger-compiler/src/type/class.cc b/tiger-compiler/src/type/class.cc new file mode 100644 index 0000000..a1876d3 --- /dev/null +++ b/tiger-compiler/src/type/class.cc @@ -0,0 +1,123 @@ +/** + ** \file type/class.cc + ** \brief Implementation for type/class.hh. + */ + +#include <ostream> + +#include <misc/algorithm.hh> +#include <type/class.hh> +#include <type/visitor.hh> + +namespace type +{ + Class::Class(const Class* super) + : Type() + , id_(fresh_id()) + , super_(super) + , subclasses_() + {} + + void Class::accept(ConstVisitor& v) const { v(*this); } + + void Class::accept(Visitor& v) { v(*this); } + + const Type* Class::attr_type(misc::symbol key) const + { + // FIXME DONE: Some code was deleted here. + const auto& attribute = std::ranges::find_if( + attrs_, + [&key] (const misc::symbol& name) { return name == key; }, + [] (const Attribute& attr) { return attr.name_get(); } + ); + + return attribute != attrs_.end() ? &attribute->type_get() : nullptr; + } + + const Type* Class::meth_type(misc::symbol key) const + { + // FIXME DONE: Some code was deleted here. + const auto& method = std::ranges::find_if( + meths_, + [&key] (const misc::symbol& name) { return name == key; }, + [] (const Method* const meth) { return meth->name_get(); } + ); + + return method != meths_.end() ? &(*method)->type_get() : nullptr; + } + + // FIXME DONE: Some code was deleted here (Find common super class). + const Class* Class::common_root(const Class& other) const + { + // temporary note: i'm tired so maybe the algo sucks ass :c + if (*this == other) + { + return this; + } + + std::vector<const Class*> super_classes; + + for (auto this_sc = this; this_sc != nullptr; this_sc = this_sc->super_) + { + super_classes.push_back(this_sc); + } + + for (auto other_sc = &other; other_sc != nullptr; other_sc = other_sc->super_) + { + if (auto matching = std::ranges::find(super_classes, other_sc); + matching != super_classes.end()) + { + return *matching; + } + } + + return nullptr; + } + + // FIXME DONE: Some code was deleted here (Super class soundness test). + bool Class::sound() const + { + auto reference = this; + std::vector<const Class*> previous; + + while (reference != nullptr) + { + if (std::ranges::find(previous, reference) != previous.end()) + { + return false; + } + + previous.push_back(reference); + reference = reference->super_; + } + + return true; + } + + // FIXME DONE: Some code was deleted here (Special implementation of "compatible_with" for Class). + bool Class::compatible_with(const Type& other) const + { + if (Type::compatible_with(other) || dynamic_cast<const Nil*>(&other)) + { + return true; + } + + const auto ptr = dynamic_cast<const Class*>(&other); + + return ptr && common_root(*ptr); + } + + const Class& Class::object_instance() + { + // FIXME DONE: Some code was deleted here. + static const Class object { nullptr }; + return object; + } + + unsigned Class::fresh_id() + { + static unsigned counter_ = 0; + return counter_++; + } + +} // namespace type diff --git a/tiger-compiler/src/type/class.hh b/tiger-compiler/src/type/class.hh new file mode 100644 index 0000000..37779e8 --- /dev/null +++ b/tiger-compiler/src/type/class.hh @@ -0,0 +1,159 @@ +/** + ** \file type/class.hh + ** \brief The class Class. + */ +#pragma once + +#include <vector> + +#include <misc/symbol.hh> +#include <type/attribute.hh> +#include <type/method.hh> +#include <type/type.hh> + +namespace type +{ + /** \brief Class types. + ** + ** List of Attributes and Methods. */ + class Class : public Type + { + /** \name Constructor. + ** \{ */ + public: + /** \brief Construct a Class. + ** + ** \param super Super class. */ + explicit Class(const Class* super = nullptr); + /** \} */ + + /// \name Visitors entry point. + /** \{ */ + /// Accept a const visitor \a v. + void accept(ConstVisitor& v) const override; + /// Accept a non-const visitor \a v. + void accept(Visitor& v) override; + /** \} */ + + /** \name Attribute and Method elementary manipulation. + ** \{ */ + /// \brief Return the attribute type associated to \a key. + /// + /// The search is performed throughout the super classes. + const Type* attr_type(misc::symbol key) const; + /// \brief Return the method type associated to \a key. + /// + /// The search is performed throughout the super classes. + const Type* meth_type(misc::symbol key) const; + /** \} */ + + /** \name Internal Attribute list manipulators. + ** \{ */ + /// List of Attribute's. + using attrs_type = std::vector<Attribute>; + /// List of Method's. + using meths_type = std::vector<const Method*>; + /// List of Subclasses's. + using subclasses_type = std::vector<const Class*>; + + /// Return the list of stored Attributes (read only). + const attrs_type& attrs_get() const; + /// Return the list of stored Methods (read only). + const meths_type& meths_get() const; + + /// \brief Find an attribute using its name, return `nullptr' if + /// not found. + /// + /// The search is performed throughout the super classes. + const Attribute* attr_find(misc::symbol key) const; + /// \brief Find a method using its name, return `nullptr' if + /// not found. + /// + /// The search is performed throughout the super classes. + const Method* meth_find(misc::symbol key) const; + + /// \brief Find an owned attribute using its name, return + /// `nullptr' if not found. + /// + /// The search is restricted to the class. + const Attribute* owned_attr_find(misc::symbol key) const; + + /// \brief Find an owned method using its name, return `nullptr' + /// if not found. + /// + /// The search is restricted to the class. + const Method* owned_meth_find(misc::symbol key) const; + + /// Add an already existing Attribute to the list. + void attr_add(const Attribute& attr); + /// Create a Attribute then add it to the list. + void attr_add(const ast::VarDec* def); + + /// Add an already existing Method to the list. + void meth_add(const Method* method); + /** \} */ + + /// Does this class have actual data (i.e., owned attributes)? + bool has_data() const; + + /** \name Accessors. + ** \{ */ + /// Return the unique identifier of the class. + unsigned id_get() const; + + /// Return the type of the super class. + const Class* super_get() const; + /// Set the type of the super class. + void super_set(const Class* type); + + /// Return (the transitive closure of) the list of subclasses. + const subclasses_type& subclasses_get() const; + + /// \brief Add a class to the list of subclasses. + /// + /// Although this method alters \a this, it is const, since types + /// are mostly manipulated as const entities. + void subclass_add(const Class* subclass) const; + + /// \brief Erase all the subclasses. + /// + /// This method is const for the same reason as + /// type::Class::subclass_add. + void subclasses_clear() const; + /** \} */ + + /** \name Type resolution. + ** \{ */ + /** \brief Find the common super class. */ + const Class* common_root(const Class& other) const; + + /** \brief Check that the definition of this class is sound, + ** i.e. that there is no recursive inheritance. */ + bool sound() const; + /** \} */ + + // FIXME DONE: Some code was deleted here (Inherited methods). + bool compatible_with(const Type& other) const override; + + /// Return the unique instance of the class type `Object'. + static const Class& object_instance(); + + private: + /// Return a fresh identifier. + static unsigned fresh_id(); + + /// Class unique identifier + unsigned id_; + /// Super class. + const Class* super_; + /// Sub classes. + mutable subclasses_type subclasses_; + /// Attributes list. + attrs_type attrs_; + /// Methods list. + meths_type meths_; + }; + +} // namespace type + +#include <type/class.hxx> diff --git a/tiger-compiler/src/type/class.hxx b/tiger-compiler/src/type/class.hxx new file mode 100644 index 0000000..0a41d17 --- /dev/null +++ b/tiger-compiler/src/type/class.hxx @@ -0,0 +1,88 @@ +/** + ** \file type/class.hxx + ** \brief Inline methods for type::Class. + */ +#pragma once + +#include <iostream> + +#include <misc/algorithm.hh> +#include <type/class.hh> + +namespace type +{ + inline const Class::attrs_type& Class::attrs_get() const { return attrs_; } + + inline const Attribute* Class::attr_find(misc::symbol key) const + { + for (const Class* cur = this; cur; cur = cur->super_get()) + { + const Attribute* attr = cur->owned_attr_find(key); + if (attr) + return attr; + } + return nullptr; + } + + inline const Method* Class::meth_find(misc::symbol key) const + { + for (const Class* cur = this; cur; cur = cur->super_get()) + { + const Method* meth = cur->owned_meth_find(key); + if (meth) + return meth; + } + return nullptr; + } + + inline const Attribute* Class::owned_attr_find(misc::symbol key) const + { + for (const Attribute& at : attrs_get()) + if (at.name_get() == key) + return &at; + return nullptr; + } + + inline const Method* Class::owned_meth_find(misc::symbol key) const + { + for (const Method* m : meths_get()) + if (m->name_get() == key) + return m; + return nullptr; + } + + inline void Class::attr_add(const Attribute& attr) + { + attrs_.emplace_back(attr); + } + + inline void Class::attr_add(const ast::VarDec* def) + { + attrs_.emplace_back(def); + } + + inline const Class::meths_type& Class::meths_get() const { return meths_; } + + inline void Class::meth_add(const Method* meth) { meths_.emplace_back(meth); } + + inline bool Class::has_data() const { return !attrs_.empty(); } + + inline unsigned Class::id_get() const { return id_; } + + inline const Class* Class::super_get() const { return super_; } + + inline void Class::super_set(const Class* super) { super_ = super; } + + inline const Class::subclasses_type& Class::subclasses_get() const + { + return subclasses_; + } + + inline void Class::subclass_add(const Class* subclass) const + { + subclasses_.emplace_back(subclass); + } + + inline void Class::subclasses_clear() const { subclasses_.clear(); } + +} // namespace type diff --git a/tiger-compiler/src/type/default-visitor.hh b/tiger-compiler/src/type/default-visitor.hh new file mode 100644 index 0000000..dbcfc0c --- /dev/null +++ b/tiger-compiler/src/type/default-visitor.hh @@ -0,0 +1,65 @@ +/** + ** \file type/default-visitor.hh + ** \brief Traverse a Type, doing nothing. + */ + +#pragma once + +#include <type/visitor.hh> + +namespace type +{ + template <template <typename> class Const> + class GenDefaultVisitor : public GenVisitor<Const> + { + public: + /// Convenient abbreviation. + template <typename Type> using const_t = typename Const<Type>::type; + + /// Super class type. + using super_type = GenVisitor<Const>; + + // Import overloaded \c operator() methods. + using super_type::operator(); + + /** \name Ctor & dtor. + ** \{ */ + /// Construct a default visitor. + GenDefaultVisitor(); + /// Destroy a default visitor. + virtual ~GenDefaultVisitor(); + /** \} */ + + /** \name Visit basic types. + ** \{ */ + void operator()(const_t<Nil>& e) override; + void operator()(const_t<Void>& e) override; + void operator()(const_t<Int>& e) override; + void operator()(const_t<String>& e) override; + /** \} */ + + /** \name Visit composed types. + ** \{ */ + void operator()(const_t<Named>& e) override; + void operator()(const_t<Array>& e) override; + void operator()(const_t<Record>& e) override; + void operator()(const_t<Class>& e) override; + void operator()(const_t<Function>& e) override; + void operator()(const_t<Method>& e) override; + /** \} */ + }; + + /// Shorthand for a const visitor. + using DefaultConstVisitor = GenDefaultVisitor<misc::constify_traits>; + /// Shorthand for a non const visitor. + using DefaultVisitor = GenDefaultVisitor<misc::id_traits>; + +#ifdef SWIG + /// Shorthand for a const visitor. + %template(DefaultConstVisitor) GenDefaultVisitor<misc::constify_traits>; + /// Shorthand for a non const visitor. + %template(DefaultVisitor) GenDefaultVisitor<misc::id_traits>; +#endif +} // namespace type + +#include <type/default-visitor.hxx> diff --git a/tiger-compiler/src/type/default-visitor.hxx b/tiger-compiler/src/type/default-visitor.hxx new file mode 100644 index 0000000..02cbd15 --- /dev/null +++ b/tiger-compiler/src/type/default-visitor.hxx @@ -0,0 +1,95 @@ +/** + ** \file type/default-visitor.hxx + ** \brief Implementation for type/default-visitor.hh. + */ + +#pragma once + +#include <misc/algorithm.hh> +#include <type/class.hh> +#include <type/default-visitor.hh> +#include <type/types.hh> + +namespace type +{ + template <template <typename> class Const> + GenDefaultVisitor<Const>::GenDefaultVisitor() + : GenVisitor<Const>() + {} + + template <template <typename> class Const> + GenDefaultVisitor<Const>::~GenDefaultVisitor() = default; + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Nil>&) + {} + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Void>&) + {} + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Int>&) + {} + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<String>&) + {} + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Named>& e) + { + // FIXME DONE: Some code was deleted here. + e.type_get()->accept(*this); + } + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Array>& e) + { + // FIXME DONE: Some code was deleted here. + e.get_element_type()->accept(*this); + } + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Record>& e) + { + // FIXME DONE: Some code was deleted here. + for (auto field : e) + { + field.type_get().accept(*this); + } + } + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Class>& e) + { + // FIXME DONE: Some code was deleted here. + for (auto attr : e.attrs_get()) + { + attr.type_get().accept(*this); + } + for (auto meth : e.meths_get()) + { + meth->accept(*this); + } + for (auto subclass : e.attrs_get()) + { + subclass.type_get().accept(*this); + } + } + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Function>& e) + { + // FIXME DONE: Some code was deleted here. + e.formals_get().accept(*this); + e.result_get().accept(*this); + } + + template <template <typename> class Const> + void GenDefaultVisitor<Const>::operator()(const_t<Method>& e) + { + e.Function::accept(*this); + } + +} // namespace type diff --git a/tiger-compiler/src/type/field.cc b/tiger-compiler/src/type/field.cc new file mode 100644 index 0000000..e7ec949 --- /dev/null +++ b/tiger-compiler/src/type/field.cc @@ -0,0 +1,17 @@ +/** + ** \file type/field.cc + ** \brief Implementation for type/field.hh. + */ + +#include <ostream> + +#include <type/field.hh> + +namespace type +{ + Field::Field(misc::symbol name, const Type& type) + : name_(name) + , type_(type) + {} + +} // namespace type diff --git a/tiger-compiler/src/type/field.hh b/tiger-compiler/src/type/field.hh new file mode 100644 index 0000000..e1f5609 --- /dev/null +++ b/tiger-compiler/src/type/field.hh @@ -0,0 +1,45 @@ +/** + ** \file type/field.hh + ** \brief The class Field (of a record type). + */ +#pragma once + +#include <misc/symbol.hh> +#include <type/fwd.hh> +#include <type/type.hh> + +namespace type +{ + /** \brief The base type for Record fields. + ** + ** Very much like Named, but it is *not* a Type. */ + class Field + { + public: + /** \name Ctor & dtor. + ** \{ */ + /** \brief Construct a Field. + ** \param name field's identifier. + ** \param type field's type. */ + Field(misc::symbol name, const Type& type); + /** \} */ + + /** \name Accessors. + ** \{ */ + /// Return the field's name. + misc::symbol name_get() const; + /// Return the field's type. + const Type& type_get() const; + /** \} */ + + protected: + /// Field's identifier. + misc::symbol name_; + + /// Field's type. + const Type& type_; + }; + +} // namespace type + +#include <type/field.hxx> diff --git a/tiger-compiler/src/type/field.hxx b/tiger-compiler/src/type/field.hxx new file mode 100644 index 0000000..b4d9630 --- /dev/null +++ b/tiger-compiler/src/type/field.hxx @@ -0,0 +1,16 @@ +/** + ** \file type/field.hxx + ** \brief Inline methods for type::Field. + */ +#pragma once + +#include <misc/contract.hh> +#include <type/field.hh> + +namespace type +{ + inline misc::symbol Field::name_get() const { return name_; } + + inline const Type& Field::type_get() const { return type_; } + +} // namespace type diff --git a/tiger-compiler/src/type/function.cc b/tiger-compiler/src/type/function.cc new file mode 100644 index 0000000..91cef2c --- /dev/null +++ b/tiger-compiler/src/type/function.cc @@ -0,0 +1,38 @@ +/** + ** \file type/function.cc + ** \brief Implementation for type/function.hh. + */ + +#include <ostream> +#include <ranges> + +#include <type/function.hh> +#include <type/visitor.hh> + +namespace type +{ + Function::Function(const Record* formals, const Type& result) + : result_(result) + { + precondition(formals); + + formals_ = formals; + } + + Function::~Function() { delete formals_; } + + void Function::accept(ConstVisitor& v) const { v(*this); } + + void Function::accept(Visitor& v) { v(*this); } + + // FIXME DONE: Some code was deleted here. + bool Function::compatible_with(const Type& other) const + { + const auto other_function = dynamic_cast<const Function*>(&other); + + return other_function != nullptr \ + && other_function->formals_get().compatible_with(this->formals_get()) \ + && other_function->result_get().compatible_with(this->result_get()); + } + +} // namespace type diff --git a/tiger-compiler/src/type/function.hh b/tiger-compiler/src/type/function.hh new file mode 100644 index 0000000..2accb82 --- /dev/null +++ b/tiger-compiler/src/type/function.hh @@ -0,0 +1,59 @@ +/** + ** \file type/function.hh + ** \brief The class Function. + */ +#pragma once + +#include <type/fwd.hh> +#include <type/record.hh> +#include <type/type.hh> + +namespace type +{ + /** \brief Function types. + ** + ** Encapsulate the signature of a function, i.e. the type structures + ** of both function's arguments and its result. */ + class Function : public Type + { + public: + /** \brief Construct a Function. + ** + ** \param formals type structures of formal arguments. + ** \param result type structure of what function returns. */ + Function(const Record* formals, const Type& result); + + /** \brief Destructor. + **/ + ~Function() override; + + /// \name Visitors entry point. + /** \{ */ + /// Accept a const visitor \a v. + void accept(ConstVisitor& v) const override; + /// Accept a non-const visitor \a v. + void accept(Visitor& v) override; + /** \} */ + + /** \name Accessors. + ** \{ */ + /// Return the type structures of the function's arguments. + const Record& formals_get() const; + /// Return the type structure of the function's result. + const Type& result_get() const; + /** \} */ + + // FIXME DONE: Some code was deleted here (Special implementation of "compatible_with" for Function). + bool compatible_with(const Type& other) const override; + + protected: + /// Formals' types. + const Record* formals_; + + /// Result's type. + const Type& result_; + }; + +} // namespace type + +#include <type/function.hxx> diff --git a/tiger-compiler/src/type/function.hxx b/tiger-compiler/src/type/function.hxx new file mode 100644 index 0000000..1784650 --- /dev/null +++ b/tiger-compiler/src/type/function.hxx @@ -0,0 +1,16 @@ +/** + ** \file type/function.hxx + ** \brief Inline methods for type::Function. + */ +#pragma once + +#include <misc/contract.hh> +#include <type/function.hh> + +namespace type +{ + inline const Record& Function::formals_get() const { return *formals_; } + + inline const Type& Function::result_get() const { return result_; } + +} // namespace type diff --git a/tiger-compiler/src/type/fwd.hh b/tiger-compiler/src/type/fwd.hh new file mode 100644 index 0000000..9fa9fca --- /dev/null +++ b/tiger-compiler/src/type/fwd.hh @@ -0,0 +1,31 @@ +/** + ** \file type/fwd.hh + ** \brief Forward declarations for the type module. + */ + +#pragma once + +#include <misc/fwd.hh> + +namespace type +{ + class Array; + class Attribute; + class Class; + class Field; + class Function; + class Int; + class Method; + class Named; + class Nil; + class Record; + class String; + class Type; + class Void; + + // From visitor.hh + template <template <typename> class Const> class GenVisitor; + using ConstVisitor = GenVisitor<misc::constify_traits>; + using Visitor = GenVisitor<misc::id_traits>; + +} // namespace type diff --git a/tiger-compiler/src/type/libtype.cc b/tiger-compiler/src/type/libtype.cc new file mode 100644 index 0000000..50392d7 --- /dev/null +++ b/tiger-compiler/src/type/libtype.cc @@ -0,0 +1,19 @@ +/** + ** \file type/libtype.cc + ** \brief Define the function exported by type module. + */ + +#include <ast/exp.hh> +#include <type/libtype.hh> +#include <type/type-checker.hh> + +namespace type +{ + misc::error types_check(ast::Ast& tree) + { + TypeChecker type; + type(tree); + return type.error_get(); + } + +} // namespace type diff --git a/tiger-compiler/src/type/libtype.hh b/tiger-compiler/src/type/libtype.hh new file mode 100644 index 0000000..01fa60e --- /dev/null +++ b/tiger-compiler/src/type/libtype.hh @@ -0,0 +1,19 @@ +/** + ** \file type/libtype.hh + ** \brief Declare the function exported by type module. + */ + +#pragma once + +#include <ast/fwd.hh> +#include <misc/error.hh> + +/// Type-checking an ast::Ast. +namespace type +{ + /** \brief Check types in a (bound) AST. + ** \param tree abstract syntax tree's root. + ** \return synthesis of the errors possibly found. */ + misc::error types_check(::ast::Ast& tree); + +} // namespace type diff --git a/tiger-compiler/src/type/local.am b/tiger-compiler/src/type/local.am new file mode 100644 index 0000000..e071bc1 --- /dev/null +++ b/tiger-compiler/src/type/local.am @@ -0,0 +1,29 @@ +## type module. +EXTRA_DIST += %D%/README.txt + +src_libtc_la_SOURCES += \ + %D%/fwd.hh %D%/types.hh \ + %D%/array.hh %D%/array.cc %D%/array.hxx \ + %D%/builtin-types.hh %D%/builtin-types.cc \ + %D%/nil.hh %D%/nil.cc \ + %D%/default-visitor.hh %D%/default-visitor.hxx \ + %D%/field.hh %D%/field.cc %D%/field.hxx \ + %D%/named.hh %D%/named.cc %D%/named.hxx \ + %D%/pretty-printer.hh %D%/pretty-printer.cc \ + %D%/record.hh %D%/record.cc %D%/record.hxx \ + %D%/type.hh %D%/type.hxx %D%/type.cc \ + %D%/type-checker.hh %D%/type-checker.hxx %D%/type-checker.cc \ + %D%/libtype.hh %D%/libtype.cc \ + %D%/visitor.hh %D%/visitor.hxx + +src_libtc_la_SOURCES += \ + %D%/function.hh %D%/function.cc %D%/function.hxx +src_libtc_la_SOURCES += \ + %D%/attribute.hh %D%/attribute.cc %D%/attribute.hxx \ + %D%/class.hh %D%/class.cc %D%/class.hxx \ + %D%/method.hh %D%/method.cc %D%/method.hxx + +check_PROGRAMS += %D%/test-type +%C%_test_type_LDADD = src/libtc.la + +TASKS += %D%/tasks.hh %D%/tasks.cc diff --git a/tiger-compiler/src/type/method.cc b/tiger-compiler/src/type/method.cc new file mode 100644 index 0000000..5726948 --- /dev/null +++ b/tiger-compiler/src/type/method.cc @@ -0,0 +1,48 @@ +/** + ** \file type/method.cc + ** \brief Implementation for type/method.hh. + */ + +#include <iostream> + +#include <type/method.hh> +#include <type/visitor.hh> + +namespace type +{ + Method::Method(misc::symbol name, + const Class* owner, + const Record* formals, + const Type& result, + ast::MethodDec* def) + : Function(formals, result) + , name_(name) + , owner_(owner) + , def_(def) + {} + + Method::Method(misc::symbol name, + const Record* formals, + const Type& result, + ast::MethodDec* def) + : Function(formals, result) + , name_(name) + , owner_(nullptr) + , def_(def) + {} + + void Method::accept(ConstVisitor& v) const { v(*this); } + + void Method::accept(Visitor& v) { v(*this); } + + // FIXME DONE: Some code was deleted here. + bool Method::compatible_with(const Type& other) const + { + const auto other_method = dynamic_cast<const Method*>(&other); + + return other_method != nullptr \ + && other_method->formals_get().compatible_with(other) \ + && other_method->result_get().compatible_with(other); + } + +} // namespace type diff --git a/tiger-compiler/src/type/method.hh b/tiger-compiler/src/type/method.hh new file mode 100644 index 0000000..f9c3d8c --- /dev/null +++ b/tiger-compiler/src/type/method.hh @@ -0,0 +1,90 @@ +/** + ** \file type/method.hh + ** \brief The class Method. + */ +#pragma once + +#include <ast/method-dec.hh> +#include <type/function.hh> + +namespace type +{ + // Forward declaration. + class Class; + + /** \brief Method types. + ** + ** Encapsulate the signature of a method, i.e. the type structures + ** of both method's arguments and its result. */ + class Method : public Function + { + /// A shortcut for the super type of this class. + using super_type = Function; + + public: + /** \brief Construct a FunEntry. + ** + ** \param name The method's identifier. + ** \param owner The type::Class owning this method. + ** \param formals The type structures of formal arguments. + ** \param result The type structure of what method returns. + ** \param def The method's definition site. */ + Method(misc::symbol name, + const Class* owner, + const Record* formals, + const Type& result, + ast::MethodDec* def); + + /** \brief Construct a FunEntry. + ** + ** \param name The method's identifier. + ** \param formals The type structures of formal arguments. + ** \param result The type structure of what method returns. + ** \param def The method's definition site. */ + Method(misc::symbol name, + const Record* formals, + const Type& result, + ast::MethodDec* def); + + /// \name Visitors entry point. + /** \{ */ + /// Accept a const visitor \a v. + void accept(ConstVisitor& v) const override; + /// Accept a non-const visitor \a v. + void accept(Visitor& v) override; + /** \} */ + + /** \name Accessors. + ** \{ */ + /// Return the method's name. + misc::symbol name_get() const; + /// Return the method's owner (enclosing class). + const Class* owner_get() const; + /// Return the method's type. + const Type& type_get() const; + /// Return the method's definiton site. + const ast::MethodDec* def_get() const; + /// Return the method's definiton site. + ast::MethodDec* def_get(); + + /// Set the method's name. + void name_set(misc::symbol name); + /// set the method's definiton site. + void def_set(ast::MethodDec* def); + /** \} */ + + // FIXME DONE: Some code was deleted here (Special implementation of "compatible_with" for type::Method). + bool compatible_with(const Type& other) const override; + + private: + /// Method's identifier. + misc::symbol name_; + /// The Class where this Method is defined. + const Class* owner_; + /// Method's definition site. + ast::MethodDec* def_; + }; + +} // namespace type + +#include <type/method.hxx> diff --git a/tiger-compiler/src/type/method.hxx b/tiger-compiler/src/type/method.hxx new file mode 100644 index 0000000..d026252 --- /dev/null +++ b/tiger-compiler/src/type/method.hxx @@ -0,0 +1,27 @@ +/** + ** \file type/method.hxx + ** \brief Inline methods for type::Method. + */ +#pragma once + +namespace type +{ + inline misc::symbol Method::name_get() const { return name_; } + + inline const Class* Method::owner_get() const { return owner_; } + + inline const Type& Method::type_get() const + { + // FIXME DONE: Some code was deleted here. + return *def_->type_get(); + } + + inline const ast::MethodDec* Method::def_get() const { return def_; } + + inline ast::MethodDec* Method::def_get() { return def_; } + + inline void Method::name_set(misc::symbol name) { name_ = name; } + + inline void Method::def_set(ast::MethodDec* def) { def_ = def; } + +} // namespace type diff --git a/tiger-compiler/src/type/named.cc b/tiger-compiler/src/type/named.cc new file mode 100644 index 0000000..ff092f6 --- /dev/null +++ b/tiger-compiler/src/type/named.cc @@ -0,0 +1,61 @@ +/** + ** \file type/named.cc + ** \brief Implementation for type/named.hh. + */ + +#include <type/named.hh> +#include <type/visitor.hh> +#include <vector> + +namespace type +{ + Named::Named(misc::symbol name) + : name_(name) + , type_(nullptr) + {} + + Named::Named(misc::symbol name, const Type* type) + : name_(name) + , type_(type) + {} + + // Inherited functions + void Named::accept(ConstVisitor& v) const + { + // FIXME DONE: Some code was deleted here. + v(*this); + } + + void Named::accept(Visitor& v) + { + // FIXME DONE: Some code was deleted here. + v(*this); + } + + bool Named::sound() const + { + // FIXME DONE: Some code was deleted here (Sound). + auto reference = dynamic_cast<const Named*>(type_); + std::vector<const Named*> previous; + + while (reference != nullptr) + { + if (std::ranges::find(previous, reference) != previous.end()) + { + return false; + } + + previous.push_back(reference); + reference = dynamic_cast<const Named*>(reference->type_get()); + } + + return true; + } + + bool Named::compatible_with(const Type& other) const + { + // FIXME DONE: Some code was deleted here (Special implementation of "compatible_with" for Named). + return type_->compatible_with(other); + } + +} // namespace type diff --git a/tiger-compiler/src/type/named.hh b/tiger-compiler/src/type/named.hh new file mode 100644 index 0000000..f8b914f --- /dev/null +++ b/tiger-compiler/src/type/named.hh @@ -0,0 +1,90 @@ +/** + ** \file type/named.hh + ** \brief The class Named. + */ +#pragma once + +#include <misc/symbol.hh> +#include <type/fwd.hh> +#include <type/type.hh> + +namespace type +{ + /** \brief Named types. + ** + ** Named types are used when new types are defined, i.e., in + ** \b Example: let type name_ = type_. + */ + class Named : public Type + { + /** \name Ctor & dtor. + ** \{ */ + public: + /** \brief Construct a Named type. + ** \param name user defined type's identifier. */ + explicit Named(misc::symbol name); + /** \brief Construct a Named type. + ** \param name user defined type's identifier. + ** \param type defined type's structure */ + Named(misc::symbol name, const Type* type); + /** \} */ + + /// \name Visitors entry point. + /** \{ */ + /// Accept a const visitor \a v. + void accept(ConstVisitor& v) const override; + /// Accept a non-const visitor \a v. + void accept(Visitor& v) override; + /** \} */ + + /** \name Accessors. + ** \{ */ + /// Return the user defined type's structure. + const Type* type_get() const; + + /** \brief Set the defined type's structure. + ** + ** This is the version which is used by TypeChecker which needs to + ** assign a value to the Named type. */ + void type_set(const Type* type) const; + + /// Return the name of this type. + misc::symbol name_get() const; + + /// (Re)set the name of this type. + void name_set(misc::symbol name); + /** \} */ + + /** \name Type resolution. + ** \{ */ + /// The type pointed to ultimately. + const Type& actual() const override; + + /** \brief Whether the definition of this named type is sound, + ** i.e. that there is no recursive dependency. */ + bool sound() const; + /** \} */ + + bool compatible_with(const Type& other) const override; + + protected: + /// Name of the defined type. + misc::symbol name_; + + /** \brief The Type pointed to. + ** + ** "Mutable const" because most of the time types are handled as + ** const objects. But Named types are built in two steps: first + ** they are built without any value for \a type_ (by + ** TypeChecker::visit_dec_header <ast::TypeDec>), and then + ** they are completed (by TypeChecker::visit_dec_body <ast::TypeDec>). + ** Because the second step of the construction is actually seen + ** as a modification by the C++ type system, we have it accept + ** it thanks to mutable. + **/ + mutable const Type* type_{}; + }; + +} // namespace type + +#include <type/named.hxx> diff --git a/tiger-compiler/src/type/named.hxx b/tiger-compiler/src/type/named.hxx new file mode 100644 index 0000000..1b84bb6 --- /dev/null +++ b/tiger-compiler/src/type/named.hxx @@ -0,0 +1,28 @@ +/** + ** \file type/named.hxx + ** \brief Inline methods for type::Named. + */ +#pragma once + +#include <misc/contract.hh> +#include <type/named.hh> + +namespace type +{ + inline const Type* Named::type_get() const { return type_; } + + inline void Named::type_set(const Type* type) const { type_ = type; } + + inline misc::symbol Named::name_get() const { return name_; } + + inline void Named::name_set(misc::symbol name) { name_ = name; } + + inline const Type& Named::actual() const + { + // FIXME DONE: Some code was deleted here. + precondition(type_ != nullptr); + + return type_->actual(); + } + +} // namespace type diff --git a/tiger-compiler/src/type/nil.cc b/tiger-compiler/src/type/nil.cc new file mode 100644 index 0000000..d3c663c --- /dev/null +++ b/tiger-compiler/src/type/nil.cc @@ -0,0 +1,34 @@ +/** + ** \file type/nil.cc + ** \brief Implementation for type/nil.hh. + */ + +#include <ostream> + +#include <type/class.hh> +#include <type/nil.hh> +#include <type/record.hh> +#include <type/visitor.hh> + +namespace type +{ + /*------. + | Nil. | + `------*/ + + void Nil::accept(ConstVisitor& v) const { v(*this); } + + void Nil::accept(Visitor& v) { v(*this); } + + bool Nil::compatible_with(const Type& other) const + { + // FIXME DONE: Some code was deleted here + return dynamic_cast<const Record*>(&other.actual()) != nullptr + || dynamic_cast<const Class*>(&other.actual()) != nullptr; + } + + const Type* Nil::record_type_get() const { return record_type_; } + + void Nil::record_type_set(const Type& type) const { record_type_ = &type; } + +} // namespace type diff --git a/tiger-compiler/src/type/nil.hh b/tiger-compiler/src/type/nil.hh new file mode 100644 index 0000000..4807ac0 --- /dev/null +++ b/tiger-compiler/src/type/nil.hh @@ -0,0 +1,47 @@ +/** + ** \file type/nil.hh + ** \brief The Nil type. + */ +#pragma once + +#include <type/fwd.hh> +#include <type/type.hh> + +namespace type +{ + /*------. + | Nil. | + `------*/ + + class Record; + + /// The builtin type of `nil'. + /// The Nil type is the type of a `nil` expression. + class Nil : public Type + { + public: + /// \name Visitors entry point. + /** \{ */ + /// Accept a const visitor \a v. + void accept(ConstVisitor& v) const override; + /// Accept a non-const visitor \a v. + void accept(Visitor& v) override; + /** \} */ + + bool compatible_with(const Type& other) const override; + + /// Get the associated record type. + const Type* record_type_get() const; + + /// Set the record type used with the nil. + void record_type_set(const Type& type) const; + + private: + /// The actual record_type that it represents. + /// Nil types are either compatible with `type::Record` or `type::Class`. + /// record_type represents the actual type that the `nil` was meant to be + /// used with. + mutable const Type* record_type_ = nullptr; + }; + +} // namespace type diff --git a/tiger-compiler/src/type/pretty-printer.cc b/tiger-compiler/src/type/pretty-printer.cc new file mode 100644 index 0000000..a6f4a99 --- /dev/null +++ b/tiger-compiler/src/type/pretty-printer.cc @@ -0,0 +1,127 @@ +/** + ** \file type/pretty-printer.cc + ** \brief Implementation for type/pretty-printer.hh. + */ + +#include <type/libtype.hh> +#include <type/pretty-printer.hh> +#include <type/type.hh> +#include <type/types.hh> + +namespace type +{ + namespace + { + template <typename Type> + std::ostream& print_type(std::ostream& ostr, const Type& type) + { + PrettyPrinter printer{ostr}; + printer(type); + return ostr; + } + + /// How many times did we go through operator()(const Named&)? + inline long int& indent(std::ostream& o) + { + // The slot to store the current indentation level. + static const int indent_index = std::ios::xalloc(); + return o.iword(indent_index); + } + + } // namespace + + std::ostream& operator<<(std::ostream& ostr, const Attribute& e) + { + return print_type(ostr, e); + } + + std::ostream& operator<<(std::ostream& ostr, const Field& e) + { + return print_type(ostr, e); + } + + std::ostream& operator<<(std::ostream& ostr, const Type& e) + { + return print_type(ostr, e); + } + + PrettyPrinter::PrettyPrinter(std::ostream& ostr) + : ostr_{ostr} + {} + + void PrettyPrinter::operator()(const Nil& e) + { + ostr_ << "nil = "; + if (auto record_type = e.record_type_get()) + ostr_ << *record_type; + else + ostr_ << "(null)"; + } + + void PrettyPrinter::operator()(const Void&) { ostr_ << "void"; } + + void PrettyPrinter::operator()(const Int&) + { + // FIXME DONE: Some code was deleted here. + ostr_ << "int"; + } + + void PrettyPrinter::operator()(const String&) + { + // FIXME DONE: Some code was deleted here. + ostr_ << "string"; + } + + void PrettyPrinter::operator()(const Named& e) + { + // FIXME DONE: Some code was deleted here. + if (const misc::symbol& name = e.name_get(); + name != "int" && name != "string") + ostr_ << name << ": "; + + super_type::operator()(e); + } + + void PrettyPrinter::operator()(const Array& e) + { + // FIXME DONE: Some code was deleted here. + ostr_ << "array of "; + super_type::operator()(e); + } + + void PrettyPrinter::operator()(const Record& e) + { + // FIXME DONE: Some code was deleted here. + ostr_ << "record {" << misc::incendl; + super_type::operator()(e); + ostr_ << misc::decendl << "}"; + } + + void PrettyPrinter::operator()(const Class& e) + { + // FIXME DONE: Some code was deleted here. + ostr_ << "class {" << misc::incendl; + super_type::operator()(e); + ostr_ << misc::decendl << "}"; + } + + void PrettyPrinter::operator()(const Function& e) + { + // FIXME DONE: Some code was deleted here. + ostr_ << "function ("; + e.formals_get().accept(*this); + ostr_ << ") -> "; + e.result_get().accept(*this); + } + + void PrettyPrinter::operator()(const Attribute& e) + { + ostr_ << e.name_get() << " : " << e.type_get(); + } + + void PrettyPrinter::operator()(const Field& e) + { + ostr_ << e.name_get() << " : " << e.type_get(); + } + +} // namespace type diff --git a/tiger-compiler/src/type/pretty-printer.hh b/tiger-compiler/src/type/pretty-printer.hh new file mode 100644 index 0000000..786cfcf --- /dev/null +++ b/tiger-compiler/src/type/pretty-printer.hh @@ -0,0 +1,67 @@ +/** + ** \file type/pretty-printer.hh + ** \brief Print the type hierarchy. + */ + +#pragma once + +#include <ostream> + +#include <type/default-visitor.hh> +#include <type/fwd.hh> + +namespace type +{ + class PrettyPrinter : public DefaultConstVisitor + { + public: + /// Super class type. + using super_type = DefaultConstVisitor; + + // Import overloaded \c operator() methods. + using super_type::operator(); + + /** \name Ctor & dtor. + ** \{ */ + /// Construct a pretty printer. + explicit PrettyPrinter(std::ostream& ostr); + /** \} */ + + /** \name Visit basic types. + ** \{ */ + void operator()(const Nil& e) override; + void operator()(const Void& e) override; + void operator()(const Int& e) override; + void operator()(const String& e) override; + /** \} */ + + /** \name Visit composed types. + ** \{ */ + void operator()(const Named& e) override; + void operator()(const Array& e) override; + void operator()(const Record& e) override; + void operator()(const Class& e) override; + void operator()(const Function& e) override; + /** \} */ + + /** \name Visit Non type types. + ** \{ */ + void operator()(const Attribute& e); + void operator()(const Field& e); + /** \} */ + + private: + /// The stream to print on. + std::ostream& ostr_; + }; + + /// Overload redirection operator for Type. + std::ostream& operator<<(std::ostream& ostr, const Type& t); + + /// Overload redirection operator for Attribute. + std::ostream& operator<<(std::ostream& ostr, const Attribute& obj); + + /// Overload redirection operator for Field. + std::ostream& operator<<(std::ostream& ostr, const Field& obj); + +} // namespace type diff --git a/tiger-compiler/src/type/record.cc b/tiger-compiler/src/type/record.cc new file mode 100644 index 0000000..174e192 --- /dev/null +++ b/tiger-compiler/src/type/record.cc @@ -0,0 +1,52 @@ +/** + ** \file type/record.cc + ** \brief Implementation for type/record.hh. + */ + +#include <algorithm> +#include <ostream> + +#include <type/builtin-types.hh> +#include <type/nil.hh> +#include <type/record.hh> +#include <type/visitor.hh> + +namespace type +{ + void Record::accept(ConstVisitor& v) const { v(*this); } + + void Record::accept(Visitor& v) { v(*this); } + + // FIXME DONE: Some code was deleted here (Field manipulators). + const Type* Record::field_type(const misc::symbol key) const + { + const auto result = std::ranges::find_if( + fields_, + [&key] (const misc::symbol& name) { return name == key; }, + [] (const Field& field) { return field.name_get(); } + ); + + return result != fields_.end() ? &result->type_get() : nullptr; + } + + int Record::field_index(const misc::symbol key) const + { + const auto result = std::ranges::find_if( + fields_, + [&key] (const misc::symbol& name) { return name == key; }, + [] (const Field& field) { return field.name_get(); } + ); + + return result != fields_.end() \ + ? static_cast<int>(std::distance(fields_.begin(), result)) \ + : -1; + } + + // FIXME DONE: Some code was deleted here (Special implementation of "compatible_with" for Record). + bool Record::compatible_with(const Type& other) const + { + return Type::compatible_with(other) \ + || dynamic_cast<const Nil*>(&other) != nullptr; + } + +} // namespace type diff --git a/tiger-compiler/src/type/record.hh b/tiger-compiler/src/type/record.hh new file mode 100644 index 0000000..d5a7d82 --- /dev/null +++ b/tiger-compiler/src/type/record.hh @@ -0,0 +1,69 @@ +/** + ** \file type/record.hh + ** \brief The class Record. + */ +#pragma once + +#include <vector> + +#include <misc/indent.hh> +#include <misc/symbol.hh> +#include <type/field.hh> +#include <type/fwd.hh> +#include <type/type.hh> + +namespace type +{ + /** \brief Record types. + ** + ** List of Field s. */ + class Record : public Type + { + /// \name Visitors entry point. + /// \{ */ + public: + /// Accept a const visitor \a v. + void accept(ConstVisitor& v) const override; + /// Accept a non-const visitor \a v. + void accept(Visitor& v) override; + /// \} + + /** \name Field elementary manipulation. + ** \{ */ + /// Return the type associated to \a key. + const Type* field_type(misc::symbol key) const; + /** \brief Return the index of the field associated to \a key. + ** + ** The index of a field is its position in the list. */ + int field_index(misc::symbol key) const; + /** \} */ + + /** \name Internal Field list manipulators. + ** \{ */ + /// List of Field's. + using fields_type = std::vector<Field>; + /// Return the Field list stored in this (read only). + const fields_type& fields_get() const; + + /// Add an already existing Field to the list. + void field_add(const Field& field); + /// Create a Field then add it to the list. + void field_add(misc::symbol name, const Type& type); + + /// Iterators over Field's. + using const_iterator = fields_type::const_iterator; + const_iterator begin() const; + const_iterator end() const; + /** \} */ + + // FIXME DONE: Some code was deleted here (Inherited method). + bool compatible_with(const Type& other) const override; + + protected: + /// Fields list. + fields_type fields_; + }; + +} // namespace type + +#include <type/record.hxx> diff --git a/tiger-compiler/src/type/record.hxx b/tiger-compiler/src/type/record.hxx new file mode 100644 index 0000000..2907cb0 --- /dev/null +++ b/tiger-compiler/src/type/record.hxx @@ -0,0 +1,34 @@ +/** + ** \file type/record.hxx + ** \brief Inline methods for type::Record. + */ +#pragma once + +#include <misc/contract.hh> +#include <type/record.hh> + +namespace type +{ + inline const Record::fields_type& Record::fields_get() const + { + return fields_; + } + + inline void Record::field_add(const Field& field) + { + fields_.emplace_back(field); + } + + inline void Record::field_add(misc::symbol name, const Type& type) + { + fields_.emplace_back(name, type); + } + + inline Record::const_iterator Record::begin() const + { + return fields_.begin(); + } + + inline Record::const_iterator Record::end() const { return fields_.end(); } + +} // namespace type diff --git a/tiger-compiler/src/type/tasks.cc b/tiger-compiler/src/type/tasks.cc new file mode 100644 index 0000000..261e015 --- /dev/null +++ b/tiger-compiler/src/type/tasks.cc @@ -0,0 +1,22 @@ +/** + ** \file type/tasks.cc + ** \brief Type module task implementations. + */ + +#include <ast/tasks.hh> +#include <common.hh> +#include <type/libtype.hh> +#define DEFINE_TASKS 1 +#include <type/tasks.hh> +#undef DEFINE_TASKS + +// Type module related tasks' implementation. +namespace type::tasks +{ + void types_check() + { + task_error() << ::type::types_check(*ast::tasks::the_program) + << &misc::error::exit_on_error; + } + +} // namespace type::tasks diff --git a/tiger-compiler/src/type/tasks.hh b/tiger-compiler/src/type/tasks.hh new file mode 100644 index 0000000..e6add54 --- /dev/null +++ b/tiger-compiler/src/type/tasks.hh @@ -0,0 +1,29 @@ +/** + ** \file type/tasks.hh + ** \brief Type module tasks. + */ + +#pragma once + +#include <task/libtask.hh> + +namespace type::tasks +{ + TASK_GROUP("4. Type checking"); + + /// Default the type-checking to Tiger (without objects nor overloading). + DISJUNCTIVE_TASK_DECLARE("T|typed", + "default the type-checking to Tiger " + "(without objects nor overloading)", + "types-compute" + " combine-types-compute" + " object-types-compute" + " assert-types-compute"); + + /// Check for type violation. + TASK_DECLARE("types-compute", + "check for type violations", + types_check, + "bindings-compute"); + +} // namespace type::tasks diff --git a/tiger-compiler/src/type/type-checker.cc b/tiger-compiler/src/type/type-checker.cc new file mode 100644 index 0000000..fcecc87 --- /dev/null +++ b/tiger-compiler/src/type/type-checker.cc @@ -0,0 +1,639 @@ +/** + ** \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 diff --git a/tiger-compiler/src/type/type-checker.hh b/tiger-compiler/src/type/type-checker.hh new file mode 100644 index 0000000..789a31f --- /dev/null +++ b/tiger-compiler/src/type/type-checker.hh @@ -0,0 +1,279 @@ +/** + ** \file type/type-checker.hh + ** \brief Perform type checking and other semantical checks. + */ + +#pragma once + +#include <cassert> +#include <string> + +#include <ast/default-visitor.hh> +#include <ast/non-assert-visitor.hh> +#include <ast/non-object-visitor.hh> +#include <misc/error.hh> +#include <misc/set.hh> +#include <type/fwd.hh> + +namespace type +{ + class TypeChecker + : public ast::DefaultVisitor + , public ast::NonObjectVisitor + , public ast::NonAssertVisitor + { + public: + using super_type = ast::DefaultVisitor; + using super_type::operator(); + + /// Construction. + TypeChecker(); + /// The error handler. + const misc::error& error_get() const; + + protected: + /// Run this visitor on \a e, and return its type. + /// + /// Note that it is also guaranteed that \a type_ is set to this type. + /// More generally, using \a type allows to avoid calling \a accept + /// directly. + const Type* type(ast::Typable& e); + const Record* type(const ast::fields_type& e); + const Record* type(const ast::VarChunk& e); + + // ------------------ // + // Helping routines. // + // ------------------ // + protected: + /// \name Error handling. + /// \{ + + /// Report an error. + void error(const ast::Ast& ast, const std::string& msg); + + /// Report an error. + /// + /// \param ast the node whose location is used in the error message + /// \param msg the error message + /// \param exp the culprit. It must support << output + template <typename T> + void error(const ast::Ast& ast, const std::string& msg, const T& exp); + + /// Report an error, and recover from it. + /// + /// \param loc the node whose location is used in the error message + /// and whose type is set to nil as an attempt to + /// recover. + /// \param msg the error message + /// \param exp the culprit. It must support << output + template <typename T, typename U> + void error_and_recover(T& loc, const std::string& msg, const U& exp); + + /// Report a type_mismatch between two entities. + /// \param ast the guilty node, used to report the location. + /// \param exp1 the string denoting the first exp. + /// \param type1 its type + /// \param exp2 similarly + /// \param type2 similarly + void type_mismatch(const ast::Ast& ast, + const std::string& exp1, + const Type& type1, + const std::string& exp2, + const Type& type2); + /// \} + + /// \name Checking types. + /// \{ + + /// \brief Check the type of an Exp. + /// + /// \param e the expression/declaration to check + /// \param s the string to refer to \a e in error messages + /// (e.g., "index", "left operand" etc.). + /// \param t the expected type + /// + /// On failure, report the error, and set the type of \a e to \a t. + /// This should be used for `ast::Exp` and `ast::Dec` nodes. + template <typename NodeType> + void check_type(NodeType& e, const std::string& s, const Type& t); + + /** \brief Check the type compatibility. + ** + ** An error message is output if types are incompatible. + ** + ** \param loc a node which location is used to report errors + ** \param exp1 the syntactic category of the first entity, + ** (used in error messages) + ** \param type1 the first type + ** \param exp2 same as above + ** \param type2 same as above + **/ + void check_types(const ast::Ast& loc, + const std::string& exp1, + const Type& type1, + const std::string& exp2, + const Type& type2); + void check_types(const ast::Ast& loc, + const std::string& exp1, + ast::Typable& type1, + const std::string& exp2, + ast::Typable& type2); + /// \} + + protected: + /// \name Setting types. + /// \{ + + /// Set the type of a node, if it isn't already set + /// (an existing type won't be overwritten). + /// + /// \param e the bound node + /// \param type the type + template <typename NodeType> + void type_default(NodeType& e, const type::Type* type); + + /// Same as type_default, but for a created type. + template <typename NodeType> + void created_type_default(NodeType& e, const type::Type* type); + + /// Set the type of a node (overwriting allowed). + /// + /// \param e the bound node + /// \param type the type + template <typename NodeType> + void type_set(NodeType& e, const type::Type* type); + /// \} + + // ------------------------- // + // The core of the visitor. // + // ------------------------- // + + // ---------------- // + // Visiting /Var/. // + // ---------------- // + + void operator()(ast::SimpleVar& e) override; + // FIXME DONE: Some code was deleted here (Other Var nodes). + void operator()(ast::FieldVar& e) override; + void operator()(ast::SubscriptVar& e) override; + + // ---------------- // + // Visiting /Exp/. // + // ---------------- // + + // Literals. + void operator()(ast::NilExp&) override; + void operator()(ast::IntExp&) override; + void operator()(ast::StringExp&) override; + + // Complex values. + void operator()(ast::RecordExp& e) override; + void operator()(ast::OpExp& e) override; + // FIXME DONE: Some code was deleted here (Other Exp nodes). + void operator()(ast::ArrayExp& e) override; + void operator()(ast::AssignExp& e) override; + void operator()(ast::BreakExp& e) override; + // I don't put MethodCallExp because it should be managed by CallExp + void operator()(ast::CallExp& e) override; + void operator()(ast::CastExp& e) override; + void operator()(ast::ForExp& e) override; + void operator()(ast::IfExp& e) override; + void operator()(ast::LetExp& e) override; + void operator()(ast::SeqExp& e) override; + void operator()(ast::WhileExp& e) override; + + // ---------------- // + // Visiting /Dec/. // + // ---------------- // + + /// \name Type and Function declarations. + /// \{ + + /// Be sure to read the documentation of + /// bind::Binder::chunk_visit. + /// + /// When type-checking a function (or a type) we need two + /// traversals: one to register the function's type (to enable + /// mutual recursions) and a second one to check the bodies. + + /// This is why there are actually three methods: chunk_visit, + /// visit_dec_header, and visit_dec_body. It turns out that + /// chunk_visit can be written for both functions and types, but of + /// course, traversals of headers and bodies differ. + + /// Check a set of definitions: unique names, browse headers, then + /// bodies. + template <class D> void chunk_visit(ast::Chunk<D>& e); + + /// Check a Function or Type declaration header. + template <class D> void visit_dec_header(D& e); + + /// Check a Function or Type declaration body. + template <class D> void visit_dec_body(D& e); + + /// Generic type-checking of a routine's body. + template <typename Routine_Type, typename Routine_Node> + void visit_routine_body(Routine_Node& e); + + /// Visit a chunk of function declarations. + void operator()(ast::FunctionChunk& e) override; + /// No longer used. + void operator()(ast::FunctionDec&) override; + + /// Visit a chunk of type declarations. + void operator()(ast::TypeChunk& e) override; + /// No longer used. + void operator()(ast::TypeDec&) override; + /// \} + + /// Visit a single Variable Declaration. + void operator()(ast::VarDec& e) override; + + // --------------- // + // Visiting /Ty/. // + // --------------- // + + void operator()(ast::NameTy& e) override; + void operator()(ast::RecordTy& e) override; + void operator()(ast::ArrayTy& e) override; + + protected: + /// Error handler. + misc::error error_; + /// Set of for index variable definitions, which are read only. + misc::set<const ast::VarDec*> var_read_only_; + + // ------------------- // + // Custom attributes. // + // ------------------- // + + // Default type to use when a node is badly typed + const Type& default_type = Int::instance(); + + // ------------------- // + // Custom methods. // + // ------------------- // + + /** + * @brief Check that the provided FunctionDec represents a valid main_ + * function, typing-wise. + * @param e Node to check. It is assumed it represents a main_ function + */ + void type_main(ast::FunctionDec* e); + }; + + /// Visit the lhs of an ast::FunctionDec. + template <> + void TypeChecker::visit_dec_header<ast::FunctionDec>(ast::FunctionDec& e); + /// Visit the rhs of an ast::FunctionDec. + template <> + void TypeChecker::visit_dec_body<ast::FunctionDec>(ast::FunctionDec& e); + + /// Visit the lhs of an ast::TypeDec. + template <> void TypeChecker::visit_dec_header<ast::TypeDec>(ast::TypeDec& e); + /// Visit the rhs of an ast::TypeDec. + template <> void TypeChecker::visit_dec_body<ast::TypeDec>(ast::TypeDec& e); + +} // namespace type + +#include <type/type-checker.hxx> diff --git a/tiger-compiler/src/type/type-checker.hxx b/tiger-compiler/src/type/type-checker.hxx new file mode 100644 index 0000000..bcdf348 --- /dev/null +++ b/tiger-compiler/src/type/type-checker.hxx @@ -0,0 +1,127 @@ +/** + ** \file type/type-checker.hxx + ** \brief Inline methods of type::TypeChecker. + */ + +#pragma once + +#include <ast/all.hh> +#include <type/pretty-printer.hh> +#include <type/type-checker.hh> +#include <type/types.hh> + +namespace type +{ + namespace + { + const Nil nil_error_instance{}; + + } + + /*----------------. + | Setting types. | + `----------------*/ + + template <typename NodeType> + void TypeChecker::type_default(NodeType& e, const type::Type* type) + { + // FIXME DONE: Some code was deleted here. + // We can check here to be sure that the type we use really is a native Tiger type + const auto casted = dynamic_cast<ast::Typable*>(&e); + + assertion(casted != nullptr); + + if (casted->type_get() != nullptr) + { + return; + } + + type_set(e, type); + } + + template <typename NodeType> + void TypeChecker::created_type_default(NodeType& e, const type::Type* type) + { + // FIXME DONE: Some code was deleted here. + const auto casted = dynamic_cast<ast::TypeConstructor*>(&e); + + assertion(casted != nullptr); + + if (casted->created_type_get() != nullptr) + { + return; + } + + casted->created_type_set(type); + } + + template <typename NodeType> + void TypeChecker::type_set(NodeType& e, const type::Type* type) + { + // FIXME DONE: Some code was deleted here (Basically e.type_set(type)). + const auto casted = dynamic_cast<ast::Typable*>(&e); + + assertion(casted != nullptr); + + casted->type_set(type); + } + + /*-----------------. + | Error handling. | + `-----------------*/ + + template <typename T> + void + TypeChecker::error(const ast::Ast& ast, const std::string& msg, const T& exp) + { + error_ << misc::error::error_type::type << ast.location_get() << ": " << msg + << ": " << exp << std::endl; + } + + template <typename T, typename U> + void + TypeChecker::error_and_recover(T& loc, const std::string& msg, const U& exp) + { + error(loc, msg, exp); + loc.type_set(&nil_error_instance); + } + + template <typename NodeType> + void TypeChecker::check_type(NodeType& e, + const std::string& s, + const Type& t) + { + // FIXME DONE: Some code was deleted here. + const auto casted = dynamic_cast<ast::Typable*>(&e); + + assertion(casted != nullptr); + + if (type(*casted)->actual() == t) + return; + + type_mismatch(e, s, *casted->type_get(), "expected", t); + } + + /*------------. + | Functions. | + `------------*/ + + template <typename Routine_Type, typename Routine_Node> + void TypeChecker::visit_routine_body(Routine_Node& e) + { + // FIXME DONE: Some code was deleted here. + if (e.body_get() == nullptr) + return; + type(*e.body_get()); + if (e.type_get()) + { + auto rt = dynamic_cast<const Routine_Type*>(e.type_get()); + check_types(e, "routine", rt->result_get(), "body", *e.body_get()->type_get()); + } + else + { + created_type_default(e, e.body_get()->type_get()); + } + } + +} // namespace type diff --git a/tiger-compiler/src/type/type.cc b/tiger-compiler/src/type/type.cc new file mode 100644 index 0000000..e0e448d --- /dev/null +++ b/tiger-compiler/src/type/type.cc @@ -0,0 +1,18 @@ +/** + ** \file type/type.cc + ** \brief Implementation for type/type.hh. + */ + +#include <ostream> + +#include <type/type.hh> + +namespace type +{ + const Type& Type::actual() const { return *this; } + + bool Type::compatible_with(const Type& other) const { return *this == other; } + + const misc::xalloc<bool> hide_actual_types; + +} // namespace type diff --git a/tiger-compiler/src/type/type.hh b/tiger-compiler/src/type/type.hh new file mode 100644 index 0000000..a5f9777 --- /dev/null +++ b/tiger-compiler/src/type/type.hh @@ -0,0 +1,66 @@ +/** + ** \file type/type.hh + ** \brief The class Type. + */ +#pragma once + +#include <misc/xalloc.hh> +#include <type/fwd.hh> + +namespace type +{ + /// Abstract a type. + class Type + { + /** \name Ctor & dtor. + ** \{ */ + public: + /// Destroys a Type. + virtual ~Type() = default; + /** \} */ + + /// \name Visitors entry point. + /// \{ */ + /// Accept a const visitor \a v. + virtual void accept(ConstVisitor& v) const = 0; + /// Accept a non-const visitor \a v. + virtual void accept(Visitor& v) = 0; + /// \} + + /** \name Accessors. + ** \{ */ + /// Return the actual type held by THIS. + virtual const Type& actual() const; + /** \} */ + + /** \brief Whether two types are "compatible". + ** + ** I.e., whether "a = b", "a <> b", "a := b" are correctly typed + ** with a of type \a this, and b of type \a other). + ** + ** By default two types are compatible (in the sense of "=" and "<>", + ** not w.r.t. an order) only when they are equal. + ** + ** In the case of assignment, "rec := nil" is valid, but "nil := rec" + ** is not, which suggest that we should have a non commutative + ** assignment specific compatibility check. But since "nil := ..." + ** is incorrect syntactically, that is not needed. + */ + virtual bool compatible_with(const Type& other) const; + }; + + /** \brief Compare two Type s. + ** + ** Return true if \a a and \a b are equivalent Tiger Types. E.g., + ** if \a a and \a b are different but point to the same type, then + ** return true. */ + bool operator==(const Type& lhs, const Type& rhs); + /// !(a == b). + bool operator!=(const Type& lhs, const Type& rhs); + + /// Hide actual types? (i.e., print only the surface type?) + extern const misc::xalloc<bool> hide_actual_types; + +} // namespace type + +#include <type/type.hxx> diff --git a/tiger-compiler/src/type/type.hxx b/tiger-compiler/src/type/type.hxx new file mode 100644 index 0000000..392c854 --- /dev/null +++ b/tiger-compiler/src/type/type.hxx @@ -0,0 +1,37 @@ +/** + ** \file type/type.hxx + ** \brief Inline methods for type::Type. + */ +#pragma once + +#include <misc/contract.hh> +#include <type/type.hh> + +namespace type +{ + inline bool operator==(const Type& lhs, const Type& rhs) + { + // FIXME DONE: Some code was deleted here. + const Type* lhs_primal = &lhs.actual(); + const Type* rhs_primal = &rhs.actual(); + + while (&rhs_primal->actual() != rhs_primal && rhs_primal != lhs_primal) + { + rhs_primal = &rhs_primal->actual(); + } + + while (&lhs_primal->actual() != lhs_primal && lhs_primal != rhs_primal) + { + lhs_primal = &lhs_primal->actual(); + } + + return lhs_primal == rhs_primal; + } + + inline bool operator!=(const Type& lhs, const Type& rhs) + { + // FIXME DONE: Some code was deleted here. + return !(lhs == rhs); + } + +} // namespace type diff --git a/tiger-compiler/src/type/types.hh b/tiger-compiler/src/type/types.hh new file mode 100644 index 0000000..b0d3771 --- /dev/null +++ b/tiger-compiler/src/type/types.hh @@ -0,0 +1,18 @@ +/** + ** \file type/types.hh + ** \brief Include all exported headers. + */ + +#pragma once + +#include <type/array.hh> +// FIXME: We should include "attribute.hh" and "class.hh" as well, but +// currently that would break the compilation (because of recursive +// dependencies). Investigate and fix this. +#include <type/builtin-types.hh> +#include <type/field.hh> +#include <type/function.hh> +#include <type/named.hh> +#include <type/nil.hh> +#include <type/record.hh> +#include <type/type.hh> diff --git a/tiger-compiler/src/type/visitor.hh b/tiger-compiler/src/type/visitor.hh new file mode 100644 index 0000000..4e78ec0 --- /dev/null +++ b/tiger-compiler/src/type/visitor.hh @@ -0,0 +1,57 @@ +/** + ** \file type/visitor.hh + ** \brief Definition of type::Visitor. + */ +#pragma once + +#include <misc/select-const.hh> +#include <type/fwd.hh> + +namespace type +{ + /** \brief Root class of all Type visitors. + ** + ** GenVisitor<CONSTIFY> is the root class of all Type visitors. */ + template <template <typename> class Const> class GenVisitor + { + /** \name Ctor & dtor. + ** \{ */ + public: + /// Convenient abbreviation. + template <typename T> using const_t = typename Const<T>::type; + + /// Destroy a GenVisitor. + virtual ~GenVisitor(); + /** \} */ + + /// The entry point: visit \a e. + virtual void operator()(const_t<Type>& e); + virtual void operator()(const_t<Nil>&) = 0; + virtual void operator()(const_t<Void>&) = 0; + virtual void operator()(const_t<Int>&) = 0; + virtual void operator()(const_t<String>&) = 0; + virtual void operator()(const_t<Named>&) = 0; + virtual void operator()(const_t<Array>&) = 0; + virtual void operator()(const_t<Record>&) = 0; + virtual void operator()(const_t<Class>&) = 0; + virtual void operator()(const_t<Function>&) = 0; + virtual void operator()(const_t<Method>&) = 0; + + /// Helper to visit nodes manipulated via a pointer. + template <class E> void operator()(E* e); + }; + + /// Shorthand for a const visitor. + using ConstVisitor = GenVisitor<misc::constify_traits>; + /// Shorthand for a non const visitor. + using Visitor = GenVisitor<misc::id_traits>; + +#ifdef SWIG + /// Shorthand for a const visitor. + %template(GenConstVisitor) GenVisitor<misc::constify_traits>; + /// Shorthand for a non const visitor. + %template(GenVisitor) GenVisitor<misc::id_traits>; +#endif +} // namespace type + +#include <type/visitor.hxx> diff --git a/tiger-compiler/src/type/visitor.hxx b/tiger-compiler/src/type/visitor.hxx new file mode 100644 index 0000000..93a0f9b --- /dev/null +++ b/tiger-compiler/src/type/visitor.hxx @@ -0,0 +1,29 @@ +/** + ** \file type/visitor.hxx + ** \brief Definition of type::Visitor. + */ + +#pragma once + +#include <type/type.hh> +#include <type/visitor.hh> + +namespace type +{ + template <template <typename> class Const> + GenVisitor<Const>::~GenVisitor() = default; + + template <template <typename> class Const> + void GenVisitor<Const>::operator()(const_t<Type>& e) + { + e.accept(*this); + } + + template <template <typename> class Const> + template <class E> + void GenVisitor<Const>::operator()(E* e) + { + e->accept(*this); + } + +} // namespace type |