From 4974b4763bd60eb875f93a71dbe2fe82ecfed9fc Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Sat, 5 Sep 2009 16:29:23 +0200 Subject: Add semantic graph and traversal mechanism The parser now builds the semantic graph. --- cli/semantics/class.cxx | 28 +++ cli/semantics/class.hxx | 25 +++ cli/semantics/elements.cxx | 117 ++++++++++++ cli/semantics/elements.hxx | 421 +++++++++++++++++++++++++++++++++++++++++++ cli/semantics/expression.cxx | 28 +++ cli/semantics/expression.hxx | 79 ++++++++ cli/semantics/namespace.cxx | 28 +++ cli/semantics/namespace.hxx | 25 +++ cli/semantics/option.cxx | 48 +++++ cli/semantics/option.hxx | 168 +++++++++++++++++ cli/semantics/unit.cxx | 64 +++++++ cli/semantics/unit.hxx | 298 ++++++++++++++++++++++++++++++ 12 files changed, 1329 insertions(+) create mode 100644 cli/semantics/class.cxx create mode 100644 cli/semantics/class.hxx create mode 100644 cli/semantics/elements.cxx create mode 100644 cli/semantics/elements.hxx create mode 100644 cli/semantics/expression.cxx create mode 100644 cli/semantics/expression.hxx create mode 100644 cli/semantics/namespace.cxx create mode 100644 cli/semantics/namespace.hxx create mode 100644 cli/semantics/option.cxx create mode 100644 cli/semantics/option.hxx create mode 100644 cli/semantics/unit.cxx create mode 100644 cli/semantics/unit.hxx (limited to 'cli/semantics') diff --git a/cli/semantics/class.cxx b/cli/semantics/class.cxx new file mode 100644 index 0000000..baa056c --- /dev/null +++ b/cli/semantics/class.cxx @@ -0,0 +1,28 @@ +// file : cli/semantics/class.cxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include + +namespace semantics +{ + // type info + // + namespace + { + struct init + { + init () + { + using compiler::type_info; + + type_info ti (typeid (class_)); + ti.add_base (typeid (scope)); + insert (ti); + } + } init_; + } +} diff --git a/cli/semantics/class.hxx b/cli/semantics/class.hxx new file mode 100644 index 0000000..1e6b59c --- /dev/null +++ b/cli/semantics/class.hxx @@ -0,0 +1,25 @@ +// file : cli/semantics/class.hxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef CLI_SEMANTICS_CLASS_HXX +#define CLI_SEMANTICS_CLASS_HXX + +#include + +namespace semantics +{ + class class_: public scope + { + protected: + friend class graph; + + class_ (path const& file, size_t line, size_t column) + : node (file, line, column) + { + } + }; +} + +#endif // CLI_SEMANTICS_CLASS_HXX diff --git a/cli/semantics/elements.cxx b/cli/semantics/elements.cxx new file mode 100644 index 0000000..de9e03a --- /dev/null +++ b/cli/semantics/elements.cxx @@ -0,0 +1,117 @@ +// file : cli/semantics/elements.cxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include + +namespace semantics +{ + // scope + // + + scope::names_iterator_pair scope:: + find (name_type const& name) const + { + names_map::const_iterator i (names_map_.find (name)); + + if (i == names_map_.end ()) + return names_iterator_pair (names_.end (), names_.end ()); + else + return names_iterator_pair (i->second.begin (), i->second.end ()); + } + + scope::names_iterator scope:: + find (names& e) + { + list_iterator_map::iterator i (iterator_map_.find (&e)); + return i != iterator_map_.end () ? i->second : names_.end (); + } + + void scope:: + add_edge_left (names& e) + { + names_list::iterator it (names_.insert (names_.end (), &e)); + iterator_map_[&e] = it; + + for (names::name_iterator i (e.name_begin ()); i != e.name_end (); ++i) + names_map_[*i].push_back (&e); + } + + void scope:: + remove_edge_left (names& e) + { + list_iterator_map::iterator i (iterator_map_.find (&e)); + assert (i != iterator_map_.end ()); + + names_.erase (i->second); + iterator_map_.erase (i); + + for (names::name_iterator ni (e.name_begin ()); ni != e.name_end (); ++ni) + { + names_map::iterator j (names_map_.find (*ni)); + + for (names_list::iterator i (j->second.begin ()); + i != j->second.end (); ++i) + { + if (*i == &e) + i = j->second.erase (i); + } + } + } + + // type info + // + namespace + { + struct init + { + init () + { + using compiler::type_info; + + // node + // + insert (type_info (typeid (node))); + + // edge + // + insert (type_info (typeid (edge))); + + // names + // + { + type_info ti (typeid (names)); + ti.add_base (typeid (edge)); + insert (ti); + } + + // nameable + // + { + type_info ti (typeid (nameable)); + ti.add_base (typeid (node)); + insert (ti); + } + + // scope + // + { + type_info ti (typeid (scope)); + ti.add_base (typeid (nameable)); + insert (ti); + } + + // type + // + { + type_info ti (typeid (type)); + ti.add_base (typeid (node)); + insert (ti); + } + } + } init_; + } +} diff --git a/cli/semantics/elements.hxx b/cli/semantics/elements.hxx new file mode 100644 index 0000000..f9b08fc --- /dev/null +++ b/cli/semantics/elements.hxx @@ -0,0 +1,421 @@ +// file : cli/semantics/elements.hxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef CLI_SEMANTICS_ELEMENTS_HXX +#define CLI_SEMANTICS_ELEMENTS_HXX + +#include +#include +#include +#include +#include // std::size_t +#include // std::abort +#include // std::pair +#include + +#include +#include + +#include + +namespace semantics +{ + using namespace cutl; + + using std::size_t; + using std::string; + + using container::graph; + using container::pointer_iterator; + + using compiler::context; + + + // + // + typedef string path; + typedef string name; + + + // + // + class node; + class edge; + + + // + // + class edge + { + public: + virtual + ~edge () {} + + public: + typedef semantics::context context_type; + + context_type& + context () + { + return context_; + } + + public: + template + bool + is_a () const + { + return dynamic_cast (this) != 0; + } + + protected: + friend class graph; + + private: + context_type context_; + }; + + /* + inline bool + operator== (edge const& x, edge const& y) + { + return &x == &y; + } + */ + + + // + // + class node + { + public: + virtual + ~node () {} + + public: + typedef semantics::context context_type; + + context_type& + context () + { + return context_; + } + + public: + path const& + file () const + { + return file_; + } + + size_t + line () const + { + return line_; + } + + size_t + column () const + { + return column_; + } + + public: + template + bool + is_a () const + { + return dynamic_cast (this) != 0; + } + + protected: + friend class graph; + + node (path const& file, size_t line, size_t column) + : file_ (file), line_ (line), column_ (column) + { + } + + // For virtual inheritance. Should never be actually called. + // + node () + { + std::abort (); + } + + // Sink functions that allow extensions in the form of one-way + // edges. + // + void + add_edge_right (edge&) + { + } + + private: + context_type context_; + path file_; + size_t line_; + size_t column_; + }; + + /* + inline bool + operator== (node const& x, node const& y) + { + return &x == &y; + } + */ + + + // + // + class scope; + class nameable; + + + // + // + class names: public edge + { + public: + typedef semantics::name name_type; + typedef semantics::scope scope_type; + + typedef std::vector name_list; + typedef name_list::const_iterator name_iterator; + + // First name. + // + name_type const& + name () const + { + return names_[0]; + } + + name_iterator + name_begin () const + { + return names_.begin (); + } + + name_iterator + name_end () const + { + return names_.end (); + } + + scope_type& + scope () const + { + return *scope_; + } + + nameable& + named () const + { + return *named_; + } + + protected: + friend class graph; + + names (name_type const& name) + { + names_.push_back (name); + } + + names (name_list const& names) + : names_ (names) + { + } + + void + set_left_node (scope_type& n) + { + scope_ = &n; + } + + void + set_right_node (nameable& n) + { + named_ = &n; + } + + void + clear_left_node (scope_type& n) + { + assert (scope_ == &n); + scope_ = 0; + } + + void + clear_right_node (nameable& n) + { + assert (named_ == &n); + named_ = 0; + } + + protected: + scope_type* scope_; + nameable* named_; + name_list names_; + }; + + + // + // + class nameable: public virtual node + { + public: + typedef semantics::name name_type; + typedef semantics::scope scope_type; + + name_type + name () const + { + return named_->name (); + } + + scope_type& + scope () + { + return named_->scope (); + } + + names& + named () + { + return *named_; + } + + protected: + friend class graph; + + nameable () + : named_ (0) + { + } + + void + add_edge_right (names& e) + { + assert (named_ == 0); + named_ = &e; + } + + void + remove_edge_right (names& e) + { + assert (named_ == &e); + named_ = 0; + } + + using node::add_edge_right; + + private: + names* named_; + }; + + + // + // + class scope: public virtual nameable + { + protected: + typedef std::list names_list; + typedef std::map list_iterator_map; + typedef std::map names_map; + + public: + typedef pointer_iterator names_iterator; + typedef pointer_iterator names_const_iterator; + + typedef + std::pair + names_iterator_pair; + + public: + names_iterator + names_begin () + { + return names_.begin (); + } + + names_iterator + names_end () + { + return names_.end (); + } + + names_const_iterator + names_begin () const + { + return names_.begin (); + } + + names_const_iterator + names_end () const + { + return names_.end (); + } + + virtual names_iterator_pair + find (name_type const&) const; + + names_iterator + find (names&); + + protected: + friend class graph; + + scope (path const& file, size_t line, size_t column) + : node (file, line, column) + { + } + + scope () + { + } + + void + add_edge_left (names&); + + void + remove_edge_left (names&); + + protected: + using nameable::add_edge_right; + + private: + names_list names_; + list_iterator_map iterator_map_; + names_map names_map_; + }; + + // + // + class type: public node + { + public: + string const& + name () const + { + return name_; + } + + protected: + friend class graph; + + type (path const& file, size_t line, size_t column, string const& name) + : node (file, line, column), name_ (name) + { + } + + private: + string name_; + }; +} + +#endif // CLI_SEMANTICS_ELEMENTS_HXX diff --git a/cli/semantics/expression.cxx b/cli/semantics/expression.cxx new file mode 100644 index 0000000..13f6a20 --- /dev/null +++ b/cli/semantics/expression.cxx @@ -0,0 +1,28 @@ +// file : cli/semantics/expression.cxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include + +namespace semantics +{ + // type info + // + namespace + { + struct init + { + init () + { + using compiler::type_info; + + type_info ti (typeid (expression)); + ti.add_base (typeid (node)); + insert (ti); + } + } init_; + } +} diff --git a/cli/semantics/expression.hxx b/cli/semantics/expression.hxx new file mode 100644 index 0000000..00f62da --- /dev/null +++ b/cli/semantics/expression.hxx @@ -0,0 +1,79 @@ +// file : cli/semantics/expression.hxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef CLI_SEMANTICS_EXPRESSION_HXX +#define CLI_SEMANTICS_EXPRESSION_HXX + +#include +#include + +namespace semantics +{ + // + // + class initialized; + + // + // + class expression: public node + { + public: + enum expression_type + { + string_lit, + char_lit, + bool_lit, + int_lit, + float_lit, + call_expr, + identifier + }; + + expression_type + type () const + { + return type_; + } + + std::string const& + value () const + { + return value_; + } + + public: + initialized& + initializes () const + { + return *initializes_; + } + + protected: + friend class graph; + + expression (path const& file, + size_t line, + size_t column, + expression_type type, + std::string const& value) + : node (file, line, column), type_ (type), value_ (value) + { + } + + void + add_edge_right (initialized& e) + { + initializes_ = &e; + } + + private: + initialized* initializes_; + + expression_type type_; + std::string value_; + }; +} + +#endif // CLI_SEMANTICS_EXPRESSION_HXX diff --git a/cli/semantics/namespace.cxx b/cli/semantics/namespace.cxx new file mode 100644 index 0000000..79fe48c --- /dev/null +++ b/cli/semantics/namespace.cxx @@ -0,0 +1,28 @@ +// file : cli/semantics/namespace.cxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include + +namespace semantics +{ + // type info + // + namespace + { + struct init + { + init () + { + using compiler::type_info; + + type_info ti (typeid (namespace_)); + ti.add_base (typeid (scope)); + insert (ti); + } + } init_; + } +} diff --git a/cli/semantics/namespace.hxx b/cli/semantics/namespace.hxx new file mode 100644 index 0000000..92a3b13 --- /dev/null +++ b/cli/semantics/namespace.hxx @@ -0,0 +1,25 @@ +// file : cli/semantics/namespace.hxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef CLI_SEMANTICS_NAMESPACE_HXX +#define CLI_SEMANTICS_NAMESPACE_HXX + +#include + +namespace semantics +{ + class namespace_: public scope + { + protected: + friend class graph; + + namespace_ (path const& file, size_t line, size_t column) + : node (file, line, column) + { + } + }; +} + +#endif // CLI_SEMANTICS_NAMESPACE_HXX diff --git a/cli/semantics/option.cxx b/cli/semantics/option.cxx new file mode 100644 index 0000000..94b02a2 --- /dev/null +++ b/cli/semantics/option.cxx @@ -0,0 +1,48 @@ +// file : cli/semantics/option.cxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include + +namespace semantics +{ + // type info + // + namespace + { + struct init + { + init () + { + using compiler::type_info; + + // belongs + // + { + type_info ti (typeid (belongs)); + ti.add_base (typeid (edge)); + insert (ti); + } + + // initializes + // + { + type_info ti (typeid (initialized)); + ti.add_base (typeid (edge)); + insert (ti); + } + + // option + // + { + type_info ti (typeid (option)); + ti.add_base (typeid (nameable)); + insert (ti); + } + } + } init_; + } +} diff --git a/cli/semantics/option.hxx b/cli/semantics/option.hxx new file mode 100644 index 0000000..21fc900 --- /dev/null +++ b/cli/semantics/option.hxx @@ -0,0 +1,168 @@ +// file : cli/semantics/option.hxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef CLI_SEMANTICS_OPTION_HXX +#define CLI_SEMANTICS_OPTION_HXX + +#include + +namespace semantics +{ + // + // + class option; + + // + // + class belongs: public edge + { + public: + typedef semantics::type type_type; + typedef semantics::option option_type; + + option_type& + option () const + { + return *option_; + } + + type_type& + type () const + { + return *type_; + } + + protected: + friend class graph; + + void + set_left_node (option_type& n) + { + option_ = &n; + } + + void + set_right_node (type_type& n) + { + type_ = &n; + } + + private: + option_type* option_; + type_type* type_; + }; + + // + // + class expression; + + // + // + class initialized: public edge + { + public: + typedef semantics::option option_type; + typedef semantics::expression expression_type; + + option_type& + option () const + { + return *option_; + } + + expression_type& + expression () const + { + return *expression_; + } + + protected: + friend class graph; + + void + set_left_node (option_type& n) + { + option_ = &n; + } + + void + set_right_node (expression_type& n) + { + expression_ = &n; + } + + private: + option_type* option_; + expression_type* expression_; + }; + + // + // + class option: public nameable + { + public: + typedef semantics::belongs belongs_type; + typedef semantics::type type_type; + + belongs_type& + belongs () const + { + return *belongs_; + } + + type_type& + type () const + { + return belongs_->type (); + } + + public: + typedef semantics::initialized initialized_type; + + bool + initialized_p () const + { + return initialized_ != 0; + } + + initialized_type& + initialized () const + { + return *initialized_; + } + + expression& + initializer () const + { + return initialized_->expression (); + } + + protected: + friend class graph; + + option (path const& file, size_t line, size_t column) + : node (file, line, column), initialized_ (0) + { + } + + void + add_edge_left (belongs_type& e) + { + belongs_ = &e; + } + + void + add_edge_left (initialized_type& e) + { + initialized_ = &e; + } + + private: + belongs_type* belongs_; + initialized_type* initialized_; + }; +} + +#endif // CLI_SEMANTICS_OPTION_HXX diff --git a/cli/semantics/unit.cxx b/cli/semantics/unit.cxx new file mode 100644 index 0000000..288f20f --- /dev/null +++ b/cli/semantics/unit.cxx @@ -0,0 +1,64 @@ +// file : cli/semantics/unit.cxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include + +#include + +namespace semantics +{ + // type info + // + namespace + { + struct init + { + init () + { + using compiler::type_info; + + // includes + // + { + type_info ti (typeid (includes)); + ti.add_base (typeid (edge)); + insert (ti); + } + + // cxx_includes + // + { + type_info ti (typeid (cxx_includes)); + ti.add_base (typeid (includes)); + insert (ti); + } + + // cli_includes + // + { + type_info ti (typeid (cli_includes)); + ti.add_base (typeid (includes)); + insert (ti); + } + + // cxx_unit + // + { + type_info ti (typeid (cxx_unit)); + ti.add_base (typeid (node)); + insert (ti); + } + + // cli_unit + // + { + type_info ti (typeid (cli_unit)); + ti.add_base (typeid (namespace_)); + insert (ti); + } + } + } init_; + } +} diff --git a/cli/semantics/unit.hxx b/cli/semantics/unit.hxx new file mode 100644 index 0000000..01bb195 --- /dev/null +++ b/cli/semantics/unit.hxx @@ -0,0 +1,298 @@ +// file : cli/semantics/unit.hxx +// author : Boris Kolpackov +// copyright : Copyright (c) 2009 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#ifndef CLI_SEMANTICS_UNIT_HXX +#define CLI_SEMANTICS_UNIT_HXX + +#include +#include + +#include +#include + +namespace semantics +{ + // + // + class cli_unit; + class cxx_unit; + + // + // + class includes: public edge + { + public: + cli_unit& + includer () const + { + return *includer_; + } + + path + file () const + { + return file_; + } + + protected: + friend class graph; + + includes (path const& file) + : file_ (file) + { + } + + void + set_left_node (cli_unit& n) + { + includer_ = &n; + } + + protected: + path file_; + cli_unit* includer_; + }; + + // + // + class cli_includes: public includes + { + public: + cli_unit& + includee () const + { + return *includee_; + } + + protected: + friend class graph; + + cli_includes (path const& file) + : includes (file) + { + } + + void + set_right_node (cli_unit& n) + { + includee_ = &n; + } + + private: + cli_unit* includee_; + }; + + // + // + class cxx_includes: public includes + { + public: + cxx_unit& + includee () const + { + return *includee_; + } + + protected: + friend class graph; + + cxx_includes (path const& file) + : includes (file) + { + } + + void + set_right_node (cxx_unit& n) + { + includee_ = &n; + } + + private: + cxx_unit* includee_; + }; + + // + // + class cxx_unit: public node + { + protected: + friend class graph; + + cxx_unit (path const& file, size_t line, size_t column) + : node (file, line, column) + { + } + + void + add_edge_right (cxx_includes&) + { + } + }; + + // + // + class cli_unit: public graph, public namespace_ + { + typedef std::vector includes_list; + + public: + typedef + pointer_iterator + includes_iterator; + + includes_iterator + includes_begin () const + { + return includes_.begin (); + } + + includes_iterator + includes_end () const + { + return includes_.end (); + } + + public: + cli_unit (path const& file) + : namespace_ (file, 1, 1) + { + // Use a special edge to get this->name() return the global + // namespace name (""). + // + new_edge (*this, *this); + } + + public: + template + T& + new_node (path const& file, size_t line, size_t column) + { + return graph ().new_node (file, line, column); + } + + template + T& + new_node (path const& file, size_t line, size_t column, A0 const& a0) + { + return graph ().new_node (file, line, column, a0); + } + + template + T& + new_node (path const& file, size_t line, size_t column, + A0 const& a0, A1 const& a1) + { + return graph ().new_node (file, line, column, a0, a1); + } + + template + T& + new_node (path const& file, size_t line, size_t column, + A0 const& a0, A1 const& a1, A2 const& a2) + { + return graph ().new_node (file, line, column, a0, a1, a2); + } + + template + T& + new_node (path const& file, size_t line, size_t column, + A0 const& a0, A1 const& a1, A2 const& a2, A3 const& a3) + { + return graph ().new_node (file, line, column, a0, a1, a2, a3); + } + + public: + type& + new_type (path const& file, size_t l, size_t c, string const& name) + { + type_map::iterator i (types_.find (name)); + + return i != types_.end () + ? *i->second + : *(types_[name] = &new_node (file, l, c, name)); + } + + protected: + // Special names edge for the global namespace. + // + class global_names: public names + { + protected: + friend class graph; + + global_names () + : names ("") + { + scope_ = 0; + } + + void + set_left_node (cli_unit&) + { + } + + void + set_right_node (nameable& n) + { + named_ = &n; + } + + void + clear_left_node (cli_unit&) + { + } + + void + clear_right_node (nameable& n) + { + assert (named_ == &n); + named_ = 0; + } + }; + + protected: + friend class graph; + + void + add_edge_left (cli_includes& e) + { + includes_.push_back (&e); + } + + void + add_edge_left (cxx_includes& e) + { + includes_.push_back (&e); + } + + void + add_edge_left (global_names&) + { + } + + void + add_edge_right (cli_includes&) + { + } + + using namespace_::add_edge_right; + + private: + semantics::graph& + graph () + { + return *this; + } + + private: + typedef std::map type_map; + + private: + includes_list includes_; + type_map types_; + }; +} + +#endif // CLI_SEMANTICS_UNIT_HXX -- cgit v1.1