Semantic graph and parsing code

Currently covers/handles namespace, class definitions (including bases
and data members), and typedefs in namespace-scopes.

13 files changed, 1890 insertions, 0 deletions

diff --git a/odb/semantics/class.cxx b/odb/semantics/class.cxx
new file mode 100644
index 0000000..5575745
--- /dev/null
+++ b/odb/semantics/class.cxx
@@ -0,0 +1,49 @@
+// file      : odb/semantics/class.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/class.hxx>
+
+namespace semantics
+{
+  // type info
+  //
+  namespace
+  {
+    struct init
+    {
+      init ()
+      {
+        using compiler::type_info;
+
+        // data_member
+        //
+        {
+          type_info ti (typeid (data_member));
+          ti.add_base (typeid (nameable));
+          ti.add_base (typeid (instance));
+          insert (ti);
+        }
+
+        // inherits
+        //
+        {
+          type_info ti (typeid (inherits));
+          ti.add_base (typeid (edge));
+          insert (ti);
+        }
+
+        // class_
+        //
+        {
+          type_info ti (typeid (class_));
+          ti.add_base (typeid (scope));
+          insert (ti);
+        }
+      }
+    } init_;
+  }
+}
diff --git a/odb/semantics/class.hxx b/odb/semantics/class.hxx
new file mode 100644
index 0000000..d4a0900
--- /dev/null
+++ b/odb/semantics/class.hxx
@@ -0,0 +1,135 @@
+// file      : odb/semantics/class.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#ifndef ODB_SEMANTICS_CLASS_HXX
+#define ODB_SEMANTICS_CLASS_HXX
+
+#include <vector>
+#include <semantics/elements.hxx>
+
+namespace semantics
+{
+  class class_;
+
+  //
+  //
+  class data_member: public nameable, public instance
+  {
+  public:
+    data_member (path const& file, size_t line, size_t column)
+        : node (file, line, column)
+    {
+    }
+  };
+
+  //
+  //
+  class inherits: public edge
+  {
+  public:
+    typedef semantics::access access_type;
+
+    class_&
+    base () const
+    {
+      return *base_;
+    }
+
+    class_&
+    derived () const
+    {
+      return *derived_;
+    }
+
+    bool
+    virtual_ () const
+    {
+      return virt_;
+    }
+
+    access_type
+    access () const
+    {
+      return access_;
+    }
+
+  public:
+    inherits (access_type access, bool virt)
+        : virt_ (virt), access_ (access)
+    {
+    }
+
+    void
+    set_left_node (class_& n)
+    {
+      derived_ = &n;
+    }
+
+    void
+    set_right_node (class_& n)
+    {
+      base_ = &n;
+    }
+
+  protected:
+    bool virt_;
+    access_type access_;
+
+    class_* base_;
+    class_* derived_;
+  };
+
+  //
+  //
+  class class_: public type, public scope
+  {
+  private:
+    typedef std::vector<inherits*> inherits_list;
+
+  public:
+    typedef inherits_list::const_iterator inherits_iterator;
+
+    inherits_iterator
+    inherits_begin () const
+    {
+      return inherits_.begin ();
+    }
+
+    inherits_iterator
+    inherits_end () const
+    {
+      return inherits_.end ();
+    }
+
+  public:
+    class_ (path const& file, size_t line, size_t column)
+        : node (file, line, column)
+    {
+    }
+
+    void
+    add_edge_left (inherits& e)
+    {
+      inherits_.push_back (&e);
+    }
+
+    void
+    add_edge_right (inherits&)
+    {
+    }
+
+    using scope::add_edge_left;
+    using scope::add_edge_right;
+
+    // Resolve conflict between scope::scope and nameable::scope.
+    //
+    using nameable::scope;
+
+  private:
+    inherits_list inherits_;
+  };
+}
+
+#endif // ODB_SEMANTICS_CLASS_HXX
diff --git a/odb/semantics/derived.cxx b/odb/semantics/derived.cxx
new file mode 100644
index 0000000..490dac4
--- /dev/null
+++ b/odb/semantics/derived.cxx
@@ -0,0 +1,96 @@
+// file      : odb/semantics/derived.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/derived.hxx>
+
+namespace semantics
+{
+  // type info
+  //
+  namespace
+  {
+    struct init
+    {
+      init ()
+      {
+        using compiler::type_info;
+
+        // derived_type
+        //
+        {
+          type_info ti (typeid (derived_type));
+          ti.add_base (typeid (type));
+          insert (ti);
+        }
+
+        // qualifies
+        //
+        {
+          type_info ti (typeid (qualifies));
+          ti.add_base (typeid (edge));
+          insert (ti);
+        }
+
+        // qualifier
+        //
+        {
+          type_info ti (typeid (qualifier));
+          ti.add_base (typeid (derived_type));
+          insert (ti);
+        }
+
+        // points
+        //
+        {
+          type_info ti (typeid (points));
+          ti.add_base (typeid (edge));
+          insert (ti);
+        }
+
+        // pointer
+        //
+        {
+          type_info ti (typeid (pointer));
+          ti.add_base (typeid (derived_type));
+          insert (ti);
+        }
+
+        // references
+        //
+        {
+          type_info ti (typeid (references));
+          ti.add_base (typeid (edge));
+          insert (ti);
+        }
+
+        // reference
+        //
+        {
+          type_info ti (typeid (reference));
+          ti.add_base (typeid (derived_type));
+          insert (ti);
+        }
+
+        // contains
+        //
+        {
+          type_info ti (typeid (contains));
+          ti.add_base (typeid (edge));
+          insert (ti);
+        }
+
+        // array
+        //
+        {
+          type_info ti (typeid (array));
+          ti.add_base (typeid (derived_type));
+          insert (ti);
+        }
+      }
+    } init_;
+  }
+}
diff --git a/odb/semantics/derived.hxx b/odb/semantics/derived.hxx
new file mode 100644
index 0000000..5e20de8
--- /dev/null
+++ b/odb/semantics/derived.hxx
@@ -0,0 +1,376 @@
+// file      : odb/semantics/derived.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#ifndef ODB_SEMANTICS_DERIVED_HXX
+#define ODB_SEMANTICS_DERIVED_HXX
+
+#include <semantics/elements.hxx>
+
+namespace semantics
+{
+  //
+  // Derived types (cvr-qualifiers, pointer, reference, and array).
+  //
+
+  class derived_type: public type
+  {
+  public:
+    virtual type&
+    base_type () const = 0;
+  };
+
+  //
+  //
+  class qualifier;
+
+  class qualifies: public edge
+  {
+  public:
+    typedef semantics::type type_type;
+    typedef semantics::qualifier qualifier_type;
+
+    type_type&
+    type () const
+    {
+      return *type_;
+    }
+
+    qualifier_type&
+    qualifier () const
+    {
+      return *qualifier_;
+    }
+
+  public:
+    qualifies ()
+    {
+    }
+
+    void
+    set_left_node (qualifier_type& n)
+    {
+      qualifier_ = &n;
+    }
+
+    void
+    set_right_node (type_type& n)
+    {
+      type_ = &n;
+    }
+
+  protected:
+    type_type* type_;
+    qualifier_type* qualifier_;
+  };
+
+  class qualifier: public derived_type
+  {
+  public:
+    typedef semantics::qualifies qualifies_type;
+
+    bool
+    const_ () const
+    {
+      return c_;
+    }
+
+    bool
+    volatile_ () const
+    {
+      return v_;
+    }
+
+    bool
+    restrict_ () const
+    {
+      return r_;
+    }
+
+    virtual type&
+    base_type () const
+    {
+      return qualifies_->type ();
+    }
+
+    qualifies_type&
+    qualifies () const
+    {
+      return *qualifies_;
+    }
+
+  public:
+    qualifier (path const& file,
+               size_t line,
+               size_t column,
+               bool c,
+               bool v,
+               bool r)
+        : node (file, line, column), c_ (c), v_ (v), r_ (r), qualifies_ (0)
+    {
+    }
+
+    void
+    add_edge_left (qualifies_type& e)
+    {
+      assert (qualifies_ == 0);
+      qualifies_ = &e;
+    }
+
+  private:
+    bool c_, v_, r_;
+    qualifies_type* qualifies_;
+  };
+
+  //
+  //
+  class pointer;
+
+  class points: public edge
+  {
+  public:
+    typedef semantics::type type_type;
+    typedef semantics::pointer pointer_type;
+
+    type_type&
+    type () const
+    {
+      return *type_;
+    }
+
+    pointer_type&
+    pointer () const
+    {
+      return *pointer_;
+    }
+
+  public:
+    points ()
+    {
+    }
+
+    void
+    set_left_node (pointer_type& n)
+    {
+      pointer_ = &n;
+    }
+
+    void
+    set_right_node (type_type& n)
+    {
+      type_ = &n;
+    }
+
+  protected:
+    type_type* type_;
+    pointer_type* pointer_;
+  };
+
+  class pointer: public type
+  {
+  public:
+    typedef semantics::points points_type;
+
+    virtual type&
+    base_type () const
+    {
+      return points_->type ();
+    }
+
+    points_type&
+    points () const
+    {
+      return *points_;
+    }
+
+  public:
+    pointer (path const& file, size_t line, size_t column)
+        : node (file, line, column), points_ (0)
+    {
+    }
+
+    void
+    add_edge_left (points_type& e)
+    {
+      assert (points_ == 0);
+      points_ = &e;
+    }
+
+  private:
+    points_type* points_;
+  };
+
+
+  //
+  //
+  class reference;
+
+  class references: public edge
+  {
+  public:
+    typedef semantics::type type_type;
+    typedef semantics::reference reference_type;
+
+    type_type&
+    type () const
+    {
+      return *type_;
+    }
+
+    reference_type&
+    reference () const
+    {
+      return *reference_;
+    }
+
+  public:
+    references ()
+    {
+    }
+
+    void
+    set_left_node (reference_type& n)
+    {
+      reference_ = &n;
+    }
+
+    void
+    set_right_node (type_type& n)
+    {
+      type_ = &n;
+    }
+
+  protected:
+    type_type* type_;
+    reference_type* reference_;
+  };
+
+  class reference: public type
+  {
+  public:
+    typedef semantics::references references_type;
+
+    virtual type&
+    base_type () const
+    {
+      return references_->type ();
+    }
+
+    references_type&
+    references () const
+    {
+      return *references_;
+    }
+
+  public:
+    reference (path const& file, size_t line, size_t column)
+        : node (file, line, column), references_ (0)
+    {
+    }
+
+    void
+    add_edge_left (references_type& e)
+    {
+      assert (references_ == 0);
+      references_ = &e;
+    }
+
+  private:
+    references_type* references_;
+  };
+
+
+  //
+  //
+  class array;
+
+  class contains: public edge
+  {
+  public:
+    typedef semantics::type type_type;
+    typedef semantics::array array_type;
+
+    type_type&
+    type () const
+    {
+      return *type_;
+    }
+
+    array_type&
+    array () const
+    {
+      return *array_;
+    }
+
+  public:
+    contains ()
+    {
+    }
+
+    void
+    set_left_node (array_type& n)
+    {
+      array_ = &n;
+    }
+
+    void
+    set_right_node (type_type& n)
+    {
+      type_ = &n;
+    }
+
+  protected:
+    type_type* type_;
+    array_type* array_;
+  };
+
+  class array: public type
+  {
+  public:
+    typedef semantics::contains contains_type;
+
+    // Return the number of elements in the array or 0 if it is not
+    // specified (e.g., int[]).
+    //
+    unsigned long long
+    size () const
+    {
+      return size_;
+    }
+
+    virtual type&
+    base_type () const
+    {
+      return contains_->type ();
+    }
+
+    contains_type&
+    contains () const
+    {
+      return *contains_;
+    }
+
+  public:
+    array (path const& file,
+           size_t line,
+           size_t column,
+           unsigned long long size)
+        : node (file, line, column), contains_ (0), size_ (size)
+    {
+    }
+
+    void
+    add_edge_left (contains_type& e)
+    {
+      assert (contains_ == 0);
+      contains_ = &e;
+    }
+
+  private:
+    contains_type* contains_;
+    unsigned long long size_;
+  };
+}
+
+#endif // ODB_SEMANTICS_DERIVED_HXX
diff --git a/odb/semantics/elements.cxx b/odb/semantics/elements.cxx
new file mode 100644
index 0000000..d14835c
--- /dev/null
+++ b/odb/semantics/elements.cxx
@@ -0,0 +1,155 @@
+// file      : odb/semantics/elements.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/elements.hxx>
+
+namespace semantics
+{
+  // access
+  //
+  static char const* access_str[] = {"public", "protected", "private"};
+
+  char const* access::
+  string () const
+  {
+    return access_str[value_];
+  }
+
+  // nameable
+  //
+
+  string nameable::
+  fq_name () const
+  {
+    if (named ().global_scope ())
+      return "";
+    else
+      return scope ().fq_name () + "::" + name ();
+  }
+
+  // scope
+  //
+
+  scope::names_iterator_pair scope::
+  find (string 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;
+    names_map_[e.name ()].push_back (&e);
+  }
+
+  // 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);
+        }
+
+        // declares
+        //
+        {
+          type_info ti (typeid (declares));
+          ti.add_base (typeid (names));
+          insert (ti);
+        }
+
+        // defines
+        //
+        {
+          type_info ti (typeid (defines));
+          ti.add_base (typeid (declares));
+          insert (ti);
+        }
+
+        // typedefs
+        //
+        {
+          type_info ti (typeid (typedefs));
+          ti.add_base (typeid (declares));
+          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 (nameable));
+          insert (ti);
+        }
+
+        // belongs
+        //
+        {
+          type_info ti (typeid (belongs));
+          ti.add_base (typeid (edge));
+          insert (ti);
+        }
+
+        // instance
+        //
+        {
+          type_info ti (typeid (instance));
+          ti.add_base (typeid (node));
+          insert (ti);
+        }
+      }
+    } init_;
+  }
+}
diff --git a/odb/semantics/elements.hxx b/odb/semantics/elements.hxx
new file mode 100644
index 0000000..0b89831
--- /dev/null
+++ b/odb/semantics/elements.hxx
@@ -0,0 +1,550 @@
+// file      : odb/semantics/elements.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#ifndef ODB_SEMANTICS_ELEMENTS_HXX
+#define ODB_SEMANTICS_ELEMENTS_HXX
+
+#include <gcc.hxx> // Keep it first.
+
+#include <map>
+#include <list>
+#include <vector>
+#include <string>
+#include <cstdlib> // std::abort
+#include <cstddef> // std::size_t
+#include <utility> // std::pair
+#include <cassert>
+
+#include <cutl/fs/path.hxx>
+
+#include <cutl/container/graph.hxx>
+#include <cutl/container/pointer-iterator.hxx>
+
+#include <cutl/compiler/context.hxx>
+
+namespace semantics
+{
+  using namespace cutl;
+
+  using std::size_t;
+  using std::string;
+
+  using container::graph;
+  using container::pointer_iterator;
+
+  using compiler::context;
+
+  // GCC parse tree node.
+  //
+  typedef ::tree gcc_tree;
+
+  //
+  //
+  using fs::path;
+  using fs::invalid_path;
+
+  //
+  //
+  class access
+  {
+  public:
+    enum value { public_, protected_, private_ };
+
+    access (value v)
+        : value_ (v)
+    {
+    }
+
+    operator value () const
+    {
+      return value_;
+    }
+
+    char const* string () const;
+
+  private:
+    value value_;
+  };
+
+  //
+  //
+  class node;
+  class edge;
+
+  //
+  //
+  class edge: public context
+  {
+  public:
+    virtual
+    ~edge () {}
+
+  public:
+    template <typename X>
+    bool
+    is_a () const
+    {
+      return dynamic_cast<X const*> (this) != 0;
+    }
+  };
+
+  //
+  //
+  class node: public context
+  {
+  public:
+    virtual
+    ~node () {}
+
+  public:
+    path const&
+    file () const
+    {
+      return file_;
+    }
+
+    size_t
+    line () const
+    {
+      return line_;
+    }
+
+    size_t
+    column () const
+    {
+      return column_;
+    }
+
+  public:
+    template <typename X>
+    bool
+    is_a () const
+    {
+      return dynamic_cast<X const*> (this) != 0;
+    }
+
+  public:
+    node (path const& file, size_t line, size_t column)
+        : file_ (file), line_ (line), column_ (column)
+    {
+    }
+
+    // Sink functions that allow extensions in the form of one-way
+    // edges.
+    //
+    void
+    add_edge_right (edge&)
+    {
+    }
+
+  protected:
+    // For virtual inheritance. Should never be actually called.
+    //
+    node ()
+        : file_ ("")
+    {
+      // GCC plugin machinery #define's abort as a macro.
+      //
+      //std::abort ();
+      abort ();
+    }
+
+  private:
+    path file_;
+    size_t line_;
+    size_t column_;
+  };
+
+  //
+  //
+  class scope;
+  class nameable;
+
+
+  //
+  //
+  class names: public edge
+  {
+  public:
+    typedef semantics::scope scope_type;
+    typedef semantics::access access_type;
+
+    string const&
+    name () const
+    {
+      return name_;
+    }
+
+    scope_type&
+    scope () const
+    {
+      return *scope_;
+    }
+
+    // Return true if the entity that this edge names is a global scope.
+    // In this case calling scope() is undefined behavior.
+    //
+    bool
+    global_scope () const
+    {
+      return scope_ == 0;
+    }
+
+    nameable&
+    named () const
+    {
+      return *named_;
+    }
+
+    access_type
+    access () const
+    {
+      return access_;
+    }
+
+  public:
+    names (string const& name, access_type access = access_type::public_)
+        : name_ (name), access_ (access)
+    {
+    }
+
+    void
+    set_left_node (scope_type& n)
+    {
+      scope_ = &n;
+    }
+
+    void
+    set_right_node (nameable& n)
+    {
+      named_ = &n;
+    }
+
+  protected:
+    scope_type* scope_;
+    nameable* named_;
+    string name_;
+    access_type access_;
+  };
+
+  //
+  // Declarations and definitions.
+  //
+
+  class declares: public names
+  {
+  public:
+    declares (string const& name, access_type access = access_type::public_)
+        : names (name, access)
+    {
+    }
+  };
+
+  class defines: public declares
+  {
+  public:
+    defines (string const& name, access_type access = access_type::public_)
+        : declares (name, access)
+    {
+    }
+  };
+
+  class type;
+  class typedefs: public declares
+  {
+  public:
+    typedef semantics::type type_type;
+
+    type_type&
+    type () const;
+
+  public:
+    typedefs (string const& name, access_type access = access_type::public_)
+        : declares (name, access)
+    {
+    }
+  };
+
+  //
+  //
+  class nameable: public virtual node
+  {
+    typedef std::vector<names*> names_list;
+
+  public:
+    typedef semantics::scope scope_type;
+
+    bool
+    anonymous () const
+    {
+      return defined_ == 0 && named_.empty ();
+    }
+
+    string
+    name () const
+    {
+      return named ().name ();
+    }
+
+    string
+    fq_name () const;
+
+    scope_type&
+    scope () const
+    {
+      return named ().scope ();
+    }
+
+    names&
+    named () const
+    {
+      return defined_ != 0 ? *defined_ : *named_[0];
+    }
+
+  public:
+    nameable ()
+        : defined_ (0)
+    {
+    }
+
+    void
+    add_edge_right (defines& e)
+    {
+      assert (defined_ == 0);
+      defined_ = &e;
+    }
+
+    void
+    add_edge_right (names& e)
+    {
+      named_.push_back (&e);
+    }
+
+    using node::add_edge_right;
+
+  private:
+    defines* defined_;
+    names_list named_;
+  };
+
+
+  //
+  //
+  class scope: public virtual nameable
+  {
+  protected:
+    typedef std::list<names*> names_list;
+    typedef std::map<names*, names_list::iterator> list_iterator_map;
+    typedef std::map<string, names_list> names_map;
+
+  public:
+    typedef pointer_iterator<names_list::iterator> names_iterator;
+    typedef pointer_iterator<names_list::const_iterator> names_const_iterator;
+
+    typedef
+    std::pair<names_const_iterator, names_const_iterator>
+    names_iterator_pair;
+
+  public:
+    bool
+    global_scope () const
+    {
+      return named ().global_scope ();
+    }
+
+    scope&
+    scope_ () const
+    {
+      return nameable::scope ();
+    }
+
+    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 (string const& name) const;
+
+    names_iterator
+    find (names&);
+
+  public:
+    scope (path const& file, size_t line, size_t column)
+        : node (file, line, column)
+    {
+    }
+
+    void
+    add_edge_left (names&);
+
+    using nameable::add_edge_right;
+
+  protected:
+    scope ()
+    {
+    }
+
+  private:
+    names_list names_;
+    list_iterator_map iterator_map_;
+    names_map names_map_;
+  };
+
+  //
+  //
+  class belongs;
+  class qualifies;
+
+  class type: public virtual nameable
+  {
+    typedef std::vector<qualifies*> qualified;
+
+  public:
+    typedef pointer_iterator<qualified::const_iterator> qualified_iterator;
+
+    qualified_iterator
+    qualified_begin () const
+    {
+      return qualified_.begin ();
+    }
+
+    qualified_iterator
+    qualified_end () const
+    {
+      return qualified_.end ();
+    }
+
+  public:
+    type (path const& file, size_t line, size_t column)
+        : node (file, line, column)
+    {
+    }
+
+    void
+    add_edge_right (belongs&)
+    {
+    }
+
+    void
+    add_edge_right (qualifies& e)
+    {
+      qualified_.push_back (&e);
+    }
+
+    using nameable::add_edge_right;
+
+  protected:
+    type ()
+    {
+    }
+
+  private:
+    qualified qualified_;
+  };
+
+  //
+  //
+  class instance;
+
+  class belongs: public edge
+  {
+  public:
+    typedef semantics::type type_type;
+    typedef semantics::instance instance_type;
+
+    type_type&
+    type () const
+    {
+      return *type_;
+    }
+
+    instance_type&
+    instance () const
+    {
+      return *instance_;
+    }
+
+  public:
+    belongs ()
+    {
+    }
+
+    void
+    set_left_node (instance_type& n)
+    {
+      instance_ = &n;
+    }
+
+    void
+    set_right_node (type_type& n)
+    {
+      type_ = &n;
+    }
+
+  private:
+    type_type* type_;
+    instance_type* instance_;
+  };
+
+  //
+  //
+  class instance: public virtual node
+  {
+  public:
+    typedef semantics::type type_type;
+    typedef semantics::belongs belongs_type;
+
+    type_type&
+    type () const
+    {
+      return belongs_->type ();
+    }
+
+    belongs_type&
+    belongs () const
+    {
+      return *belongs_;
+    }
+
+  public:
+    void
+    add_edge_left (belongs_type& e)
+    {
+      belongs_ = &e;
+    }
+
+  protected:
+    instance ()
+    {
+    }
+
+  private:
+    belongs_type* belongs_;
+  };
+}
+
+#include <semantics/elements.ixx>
+
+#endif // ODB_SEMANTICS_ELEMENTS_HXX
diff --git a/odb/semantics/elements.ixx b/odb/semantics/elements.ixx
new file mode 100644
index 0000000..7d92cdd
--- /dev/null
+++ b/odb/semantics/elements.ixx
@@ -0,0 +1,15 @@
+// file      : odb/semantics/elements.ixx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+namespace semantics
+{
+  // typedefs
+  //
+  inline typedefs::type_type& typedefs::
+  type () const
+  {
+    return dynamic_cast<type_type&> (named ());
+  }
+}
diff --git a/odb/semantics/fundamental.cxx b/odb/semantics/fundamental.cxx
new file mode 100644
index 0000000..0edca0c
--- /dev/null
+++ b/odb/semantics/fundamental.cxx
@@ -0,0 +1,168 @@
+// file      : odb/semantics/fundamental.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/fundamental.hxx>
+
+namespace semantics
+{
+  // type info
+  //
+  namespace
+  {
+    struct init
+    {
+      init ()
+      {
+        using compiler::type_info;
+
+        // fund_type
+        //
+        {
+          type_info ti (typeid (fund_type));
+          ti.add_base (typeid (type));
+          insert (ti);
+        }
+
+        // fund_void
+        //
+        {
+          type_info ti (typeid (fund_void));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_bool
+        //
+        {
+          type_info ti (typeid (fund_bool));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_char
+        //
+        {
+          type_info ti (typeid (fund_char));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_wchar
+        //
+        {
+          type_info ti (typeid (fund_wchar));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_signed_char
+        //
+        {
+          type_info ti (typeid (fund_signed_char));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_unsigned_char
+        //
+        {
+          type_info ti (typeid (fund_unsigned_char));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_short
+        //
+        {
+          type_info ti (typeid (fund_short));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_unsigned_short
+        //
+        {
+          type_info ti (typeid (fund_unsigned_short));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_int
+        //
+        {
+          type_info ti (typeid (fund_int));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_unsigned_int
+        //
+        {
+          type_info ti (typeid (fund_unsigned_int));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_long
+        //
+        {
+          type_info ti (typeid (fund_long));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_unsigned_long
+        //
+        {
+          type_info ti (typeid (fund_unsigned_long));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_long_long
+        //
+        {
+          type_info ti (typeid (fund_long_long));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_unsigned_long_long
+        //
+        {
+          type_info ti (typeid (fund_unsigned_long_long));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_float
+        //
+        {
+          type_info ti (typeid (fund_float));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_double
+        //
+        {
+          type_info ti (typeid (fund_double));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+
+        // fund_long_double
+        //
+        {
+          type_info ti (typeid (fund_long_double));
+          ti.add_base (typeid (fund_type));
+          insert (ti);
+        }
+      }
+    } init_;
+  }
+}
diff --git a/odb/semantics/fundamental.hxx b/odb/semantics/fundamental.hxx
new file mode 100644
index 0000000..aa8225a
--- /dev/null
+++ b/odb/semantics/fundamental.hxx
@@ -0,0 +1,113 @@
+// file      : odb/semantics/fundamental.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#ifndef ODB_SEMANTICS_FUNDAMENTAL_HXX
+#define ODB_SEMANTICS_FUNDAMENTAL_HXX
+
+#include <semantics/elements.hxx>
+
+namespace semantics
+{
+  //
+  // Fundamental C++ types.
+  //
+
+  class fund_type: public type {};
+
+  struct fund_void: fund_type
+  {
+    fund_void (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_bool: fund_type
+  {
+    fund_bool (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  //
+  // Integral.
+  //
+
+  struct fund_char: fund_type
+  {
+    fund_char (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_wchar: fund_type
+  {
+    fund_wchar (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_signed_char: fund_type
+  {
+    fund_signed_char (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_unsigned_char: fund_type
+  {
+    fund_unsigned_char (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_short: fund_type
+  {
+    fund_short (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_unsigned_short: fund_type
+  {
+    fund_unsigned_short (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_int: fund_type
+  {
+    fund_int (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_unsigned_int: fund_type
+  {
+    fund_unsigned_int (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_long: fund_type
+  {
+    fund_long (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_unsigned_long: fund_type
+  {
+    fund_unsigned_long (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_long_long: fund_type
+  {
+    fund_long_long (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_unsigned_long_long: fund_type
+  {
+    fund_unsigned_long_long (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  //
+  // Real.
+  //
+
+  struct fund_float: fund_type
+  {
+    fund_float (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_double: fund_type
+  {
+    fund_double (): node (path ("<fundamental>"), 0, 0) {}
+  };
+
+  struct fund_long_double: fund_type
+  {
+    fund_long_double (): node (path ("<fundamental>"), 0, 0) {}
+  };
+}
+
+#endif // ODB_SEMANTICS_FUNDAMENTAL_HXX
diff --git a/odb/semantics/namespace.cxx b/odb/semantics/namespace.cxx
new file mode 100644
index 0000000..72e977f
--- /dev/null
+++ b/odb/semantics/namespace.cxx
@@ -0,0 +1,28 @@
+// file      : odb/semantics/namespace.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/namespace.hxx>
+
+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/odb/semantics/namespace.hxx b/odb/semantics/namespace.hxx
new file mode 100644
index 0000000..b6a673c
--- /dev/null
+++ b/odb/semantics/namespace.hxx
@@ -0,0 +1,31 @@
+// file      : odb/semantics/namespace.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#ifndef ODB_SEMANTICS_NAMESPACE_HXX
+#define ODB_SEMANTICS_NAMESPACE_HXX
+
+#include <semantics/elements.hxx>
+
+namespace semantics
+{
+  class namespace_: public scope
+  {
+  public:
+    namespace_ (path const& file, size_t line, size_t column)
+        : node (file, line, column)
+    {
+    }
+
+    namespace_ ()
+    {
+    }
+
+    // Resolve conflict between scope::scope and nameable::scope.
+    //
+    using nameable::scope;
+  };
+}
+
+#endif // ODB_SEMANTICS_NAMESPACE_HXX
diff --git a/odb/semantics/unit.cxx b/odb/semantics/unit.cxx
new file mode 100644
index 0000000..073b7fd
--- /dev/null
+++ b/odb/semantics/unit.cxx
@@ -0,0 +1,32 @@
+// file      : odb/semantics/unit.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/unit.hxx>
+
+namespace semantics
+{
+  // type info
+  //
+  namespace
+  {
+    struct init
+    {
+      init ()
+      {
+        using compiler::type_info;
+
+        // unit
+        //
+        {
+          type_info ti (typeid (unit));
+          ti.add_base (typeid (namespace_));
+          insert (ti);
+        }
+      }
+    } init_;
+  }
+}
diff --git a/odb/semantics/unit.hxx b/odb/semantics/unit.hxx
new file mode 100644
index 0000000..c208876
--- /dev/null
+++ b/odb/semantics/unit.hxx
@@ -0,0 +1,142 @@
+// file      : odb/semantics/unit.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2; see accompanying LICENSE file
+
+#ifndef ODB_SEMANTICS_UNIT_HXX
+#define ODB_SEMANTICS_UNIT_HXX
+
+#include <map>
+
+#include <semantics/elements.hxx>
+#include <semantics/namespace.hxx>
+
+namespace semantics
+{
+  class unit: public graph<node, edge>, public namespace_
+  {
+  public:
+    unit (path const& file)
+        : node (file, 1, 1), graph_ (*this)
+    {
+      // Use a special edge to get this->name() return the global
+      // namespace name ("").
+      //
+      new_edge<global_names> (*this, *this);
+    }
+
+    // Mapping from GCC tree node to semantic graph node.
+    //
+  public:
+    node*
+    find (gcc_tree key) const
+    {
+      gcc_tree_node_map::const_iterator i (gcc_tree_node_map_.find (key));
+      return i != gcc_tree_node_map_.end () ? i->second : 0;
+    }
+
+    void
+    insert (gcc_tree key, node& value)
+    {
+      gcc_tree_node_map_[key] = &value;
+    }
+
+  public:
+    template <typename T>
+    T&
+    new_node (path const& file, size_t line, size_t column)
+    {
+      return graph_.new_node<T> (file, line, column);
+    }
+
+    template <typename T, typename A0>
+    T&
+    new_node (path const& file, size_t line, size_t column, A0 const& a0)
+    {
+      return graph_.new_node<T> (file, line, column, a0);
+    }
+
+    template <typename T, typename A0, typename A1>
+    T&
+    new_node (path const& file, size_t line, size_t column,
+              A0 const& a0, A1 const& a1)
+    {
+      return graph_.new_node<T> (file, line, column, a0, a1);
+    }
+
+    template <typename T, typename A0, typename A1, typename A2>
+    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<T> (file, line, column, a0, a1, a2);
+    }
+
+    template <typename T, typename A0, typename A1, typename A2, typename A3>
+    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<T> (file, line, column, a0, a1, a2, a3);
+    }
+
+    // For fundamental types.
+    //
+    template <typename T>
+    T&
+    new_fund_node ()
+    {
+      return graph_.new_node<T> ();
+    }
+
+  protected:
+    // Special names edge for the global namespace.
+    //
+    class global_names: public names
+    {
+    public:
+      global_names ()
+          : names ("")
+      {
+        scope_ = 0;
+      }
+
+      void
+      set_left_node (unit&)
+      {
+      }
+
+      void
+      set_right_node (nameable& n)
+      {
+        named_ = &n;
+      }
+
+      void
+      clear_left_node (unit&)
+      {
+      }
+
+      void
+      clear_right_node (nameable& n)
+      {
+        assert (named_ == &n);
+        named_ = 0;
+      }
+    };
+
+  public:
+    void
+    add_edge_left (global_names&)
+    {
+    }
+
+  private:
+    graph<node, edge>& graph_;
+
+    typedef std::map<gcc_tree, node*> gcc_tree_node_map;
+    gcc_tree_node_map gcc_tree_node_map_;
+  };
+}
+
+#endif // ODB_SEMANTICS_UNIT_HXX