From 4974b4763bd60eb875f93a71dbe2fe82ecfed9fc Mon Sep 17 00:00:00 2001
From: Boris Kolpackov <boris@codesynthesis.com>
Date: Sat, 5 Sep 2009 16:29:23 +0200
Subject: Add semantic graph and traversal mechanism

The parser now builds the semantic graph.
---
 cli/makefile                 |  15 ++
 cli/parser.cxx               | 233 +++++++++++++++++++++++-
 cli/parser.hxx               |  16 +-
 cli/semantics.hxx            |  16 ++
 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 ++++++++++++++++++++++++++++++
 cli/traversal.hxx            |  16 ++
 cli/traversal/class.cxx      |  27 +++
 cli/traversal/class.hxx      |  27 +++
 cli/traversal/elements.cxx   |  15 ++
 cli/traversal/elements.hxx   | 143 +++++++++++++++
 cli/traversal/expression.hxx |  17 ++
 cli/traversal/namespace.cxx  |  27 +++
 cli/traversal/namespace.hxx  |  27 +++
 cli/traversal/option.cxx     |  60 ++++++
 cli/traversal/option.hxx     |  75 ++++++++
 cli/traversal/unit.cxx       |  47 +++++
 cli/traversal/unit.hxx       |  59 ++++++
 28 files changed, 2137 insertions(+), 12 deletions(-)
 create mode 100644 cli/semantics.hxx
 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
 create mode 100644 cli/traversal.hxx
 create mode 100644 cli/traversal/class.cxx
 create mode 100644 cli/traversal/class.hxx
 create mode 100644 cli/traversal/elements.cxx
 create mode 100644 cli/traversal/elements.hxx
 create mode 100644 cli/traversal/expression.hxx
 create mode 100644 cli/traversal/namespace.cxx
 create mode 100644 cli/traversal/namespace.hxx
 create mode 100644 cli/traversal/option.cxx
 create mode 100644 cli/traversal/option.hxx
 create mode 100644 cli/traversal/unit.cxx
 create mode 100644 cli/traversal/unit.hxx

(limited to 'cli')

diff --git a/cli/makefile b/cli/makefile
index e2158d4..76d23d8 100644
--- a/cli/makefile
+++ b/cli/makefile
@@ -7,6 +7,21 @@ include $(dir $(lastword $(MAKEFILE_LIST)))../build/bootstrap.make
 
 cxx_tun := cli.cxx lexer.cxx parser.cxx
 
+cxx_tun +=               \
+semantics/class.cxx      \
+semantics/elements.cxx   \
+semantics/expression.cxx \
+semantics/namespace.cxx  \
+semantics/option.cxx     \
+semantics/unit.cxx
+
+cxx_tun +=               \
+traversal/class.cxx      \
+traversal/elements.cxx   \
+traversal/namespace.cxx  \
+traversal/option.cxx     \
+traversal/unit.cxx
+
 #
 #
 cxx_obj  := $(addprefix $(out_base)/,$(cxx_tun:.cxx=.o))
diff --git a/cli/parser.cxx b/cli/parser.cxx
index 82a68dc..9b9c116 100644
--- a/cli/parser.cxx
+++ b/cli/parser.cxx
@@ -9,7 +9,10 @@
 #include "lexer.hxx"
 #include "parser.hxx"
 
+#include "semantics.hxx"
+
 using namespace std;
+using namespace semantics;
 
 const char* keywords[] =
 {
@@ -120,17 +123,24 @@ recover (token& t)
   }
 }
 
-void parser::
+auto_ptr<cli_unit> parser::
 parse (std::istream& is, std::string const& id)
 {
+  auto_ptr<cli_unit> unit (new cli_unit (id));
+  unit_ = unit.get ();
+
   lexer l (is, id);
   lexer_ = &l;
+
   id_ = &id;
   valid_ = true;
+
   def_unit ();
 
   if (!valid_ || !l.valid ())
     throw invalid_input ();
+
+  return unit;
 }
 
 void parser::
@@ -154,6 +164,9 @@ def_unit ()
     }
   }
 
+  scope* old (scope_);
+  scope_ = unit_;
+
   // decl-seq
   //
   while (t.type () != token::t_eos)
@@ -177,6 +190,8 @@ def_unit ()
       break; // Non-recoverable error.
     }
   }
+
+  scope_ = old;
 }
 
 void parser::
@@ -191,6 +206,12 @@ include_decl ()
     throw error ();
   }
 
+  if (valid_)
+  {
+    cxx_unit& n (unit_->new_node<cxx_unit> (*id_, t.line (), t.column ()));
+    unit_->new_edge<cxx_includes> (*unit_, n, t.literal ());
+  }
+
   t = lexer_->next ();
 
   if (t.punctuation () != token::p_semi)
@@ -237,6 +258,16 @@ namespace_def ()
     throw error ();
   }
 
+  scope* old (scope_);
+
+  if (valid_)
+  {
+    namespace_& n (
+      unit_->new_node<namespace_> (*id_, t.line (), t.column ()));
+    unit_->new_edge<names> (*scope_, n, t.identifier ());
+    scope_ = &n;
+  }
+
   t = lexer_->next ();
 
   if (t.punctuation () != token::p_lcbrace)
@@ -253,6 +284,8 @@ namespace_def ()
   while (decl (t))
     t = lexer_->next ();
 
+  scope_ = old;
+
   if (t.punctuation () != token::p_rcbrace)
   {
     cerr << *id_ << ':' << t.line () << ':' << t.column () << ": error: "
@@ -274,6 +307,15 @@ class_def ()
     throw error ();
   }
 
+  scope* old (scope_);
+
+  if (valid_)
+  {
+    class_& n (unit_->new_node<class_> (*id_, t.line (), t.column ()));
+    unit_->new_edge<names> (*scope_, n, t.identifier ());
+    scope_ = &n;
+  }
+
   t = lexer_->next ();
 
   if (t.punctuation () != token::p_lcbrace)
@@ -303,6 +345,8 @@ class_def ()
     }
   }
 
+  scope_ = old;
+
   if (t.punctuation () != token::p_rcbrace)
   {
     cerr << *id_ << ':' << t.line () << ':' << t.column () << ": error: "
@@ -323,23 +367,46 @@ class_def ()
 bool parser::
 option_def (token& t)
 {
+  size_t l (t.line ()), c (t.column ());
+
   // type-spec
   //
   // These two functions set t to the next token if they return
   // true.
   //
-  if (!qualified_name (t) && !fundamental_type (t))
+  string type_name;
+
+  if (!qualified_name (t, type_name) && !fundamental_type (t, type_name))
     return false;
 
+  option* o (0);
+
+  if (valid_)
+  {
+    o = &unit_->new_node<option> (*id_, l, c);
+    type& t (unit_->new_type (*id_, l, c, type_name));
+    unit_->new_edge<belongs> (*o, t);
+  }
+
   // option-name-seq
   //
+  names::name_list nl;
   while (true)
   {
     switch (t.type ())
     {
     case token::t_identifier:
+      {
+        if (valid_)
+          nl.push_back (t.identifier ());
+
+        break;
+      }
     case token::t_string_lit:
       {
+        if (valid_)
+          nl.push_back (t.literal ());
+
         break;
       }
     default:
@@ -358,28 +425,70 @@ option_def (token& t)
       break;
   }
 
+  if (valid_)
+    unit_->new_edge<names> (*scope_, *o, nl);
+
   // initializer
   //
+  std::string ev;
+  expression::expression_type et;
+
   if (t.punctuation () == token::p_eq)
   {
-    t = lexer_->next ();
-
     // assignment initiaizer
     //
-    if (qualified_name (t))
+    t = lexer_->next ();
+
+    l = t.line ();
+    c = t.column ();
+
+    if (qualified_name (t, ev))
     {
+      et = expression::identifier;
     }
     else
     {
       switch (t.type ())
       {
       case token::t_string_lit:
+        {
+          ev = t.literal ();
+          et = expression::string_lit;
+          t = lexer_->next ();
+          break;
+        }
       case token::t_char_lit:
+        {
+          ev = t.literal ();
+          et = expression::char_lit;
+          t = lexer_->next ();
+          break;
+        }
       case token::t_bool_lit:
+        {
+          ev = t.literal ();
+          et = expression::bool_lit;
+          t = lexer_->next ();
+          break;
+        }
       case token::t_int_lit:
+        {
+          ev = t.literal ();
+          et = expression::int_lit;
+          t = lexer_->next ();
+          break;
+        }
       case token::t_float_lit:
+        {
+          ev = t.literal ();
+          et = expression::float_lit;
+          t = lexer_->next ();
+          break;
+        }
       case token::t_call_expr:
         {
+          ev = t.expression ();
+          et = expression::call_expr;
           t = lexer_->next ();
           break;
         }
@@ -396,9 +505,20 @@ option_def (token& t)
   {
     // c-tor initializer
     //
+    l = t.line ();
+    c = t.column ();
+
+    ev = t.expression ();
+    et = expression::call_expr;
     t = lexer_->next ();
   }
 
+  if (valid_ && !ev.empty ())
+  {
+    expression& e (unit_->new_node<expression> (*id_, l, c, et, ev));
+    unit_->new_edge<initialized> (*o, e);
+  }
+
   if (t.punctuation () != token::p_semi)
   {
     cerr << *id_ << ':' << t.line () << ':' << t.column () << ": error: "
@@ -410,13 +530,18 @@ option_def (token& t)
 }
 
 bool parser::
-qualified_name (token& t)
+qualified_name (token& t, string& r)
 {
   if (t.type () != token::t_identifier && t.punctuation () != token::p_dcolon)
     return false;
 
+  r.clear ();
+
   if (t.punctuation () == token::p_dcolon)
+  {
+    r += "::";
     t = lexer_->next ();
+  }
 
   while (true)
   {
@@ -427,17 +552,22 @@ qualified_name (token& t)
       throw error ();
     }
 
+    r += t.identifier ();
     t = lexer_->next ();
 
     if (t.type () == token::t_template_expr)
     {
       // Template-id.
       //
+      r += t.expression ();
       t = lexer_->next ();
     }
 
     if (t.punctuation () == token::p_dcolon)
+    {
+      r += "::";
       t = lexer_->next ();
+    }
     else
       break;
   }
@@ -446,21 +576,26 @@ qualified_name (token& t)
 }
 
 bool parser::
-fundamental_type (token& t)
+fundamental_type (token& t, string& r)
 {
+  r.clear ();
+
   switch (t.keyword ())
   {
   case token::k_signed:
   case token::k_unsigned:
     {
+      r = t.keyword () == token::k_signed ? "signed" : "unsigned";
       switch ((t = lexer_->next ()).keyword ())
       {
       case token::k_short:
         {
+          r += " short";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_int:
             {
+              r += " int";
               t = lexer_->next ();
             }
           default:
@@ -470,19 +605,23 @@ fundamental_type (token& t)
         }
       case token::k_long:
         {
+          r += " long";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_int:
             {
+              r += " int";
               t = lexer_->next ();
               break;
             }
           case token::k_long:
             {
+              r += " long";
               switch ((t = lexer_->next ()).keyword ())
               {
               case token::k_int:
                 {
+                  r += " int";
                   t = lexer_->next ();
                 }
               default:
@@ -497,19 +636,23 @@ fundamental_type (token& t)
         }
       case token::k_int:
         {
+          r += " int";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_short:
             {
+              r += " short";
               t = lexer_->next ();
               break;
             }
           case token::k_long:
             {
+              r += " long";
               switch ((t = lexer_->next ()).keyword ())
               {
               case token::k_long:
                 {
+                  r += " long";
                   t = lexer_->next ();
                 }
               default:
@@ -524,6 +667,7 @@ fundamental_type (token& t)
         }
       case token::k_char:
         {
+          r += " char";
           t = lexer_->next ();
           break;
         }
@@ -536,16 +680,19 @@ fundamental_type (token& t)
   case token::k_long:
     {
       bool l (t.keyword () == token::k_long);
+      r = l ? "long" : "short";
 
       switch ((t = lexer_->next ()).keyword ())
       {
       case token::k_signed:
       case token::k_unsigned:
         {
+          r += t.keyword () == token::k_signed ? " signed" : " unsigned";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_int:
             {
+              r += " int";
               t = lexer_->next ();
             }
           default:
@@ -555,15 +702,18 @@ fundamental_type (token& t)
         }
       case token::k_long:
         {
+          r += " long";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_signed:
           case token::k_unsigned:
             {
+              r += t.keyword () == token::k_signed ? " signed" : " unsigned";
               switch ((t = lexer_->next ()).keyword ())
               {
               case token::k_int:
                 {
+                  r += " int";
                   t = lexer_->next ();
                 }
               default:
@@ -573,12 +723,20 @@ fundamental_type (token& t)
             }
           case token::k_int:
             {
+              r += " int";
               switch ((t = lexer_->next ()).keyword ())
               {
               case token::k_signed:
+                {
+                  r += " signed";
+                  t = lexer_->next ();
+                  break;
+                }
               case token::k_unsigned:
                 {
+                  r += " unsigned";
                   t = lexer_->next ();
+                  break;
                 }
               default:
                 break;
@@ -592,12 +750,20 @@ fundamental_type (token& t)
         }
       case token::k_int:
         {
+          r += " int";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_signed:
+            {
+              r += " signed";
+              t = lexer_->next ();
+              break;
+            }
           case token::k_unsigned:
             {
+              r += " unsigned";
               t = lexer_->next ();
+              break;
             }
           default:
             break;
@@ -607,8 +773,10 @@ fundamental_type (token& t)
       case token::k_double:
         {
           if (l)
+          {
+            r += " double";
             t = lexer_->next ();
-
+          }
           break;
         }
       default:
@@ -618,24 +786,29 @@ fundamental_type (token& t)
     }
   case token::k_int:
     {
+      r = "int";
       switch ((t = lexer_->next ()).keyword ())
       {
       case token::k_signed:
       case token::k_unsigned:
         {
+          r += t.keyword () == token::k_signed ? " signed" : " unsigned";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_short:
             {
+              r += " short";
               t = lexer_->next ();
               break;
             }
           case token::k_long:
             {
+              r += " long";
               switch ((t = lexer_->next ()).keyword ())
               {
               case token::k_long:
                 {
+                  r += " long";
                   t = lexer_->next ();
                 }
               default:
@@ -649,12 +822,20 @@ fundamental_type (token& t)
         }
       case token::k_short:
         {
+          r += " short";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_signed:
+            {
+              r += " signed";
+              t = lexer_->next ();
+              break;
+            }
           case token::k_unsigned:
             {
+              r += " unsigned";
               t = lexer_->next ();
+              break;
             }
           default:
             break;
@@ -663,22 +844,37 @@ fundamental_type (token& t)
         }
       case token::k_long:
         {
+          r += " long";
           switch ((t = lexer_->next ()).keyword ())
           {
           case token::k_signed:
+            {
+              r += " signed";
+              t = lexer_->next ();
+              break;
+            }
           case token::k_unsigned:
             {
+              r += " unsigned";
               t = lexer_->next ();
               break;
             }
           case token::k_long:
             {
+              r += " long";
               switch ((t = lexer_->next ()).keyword ())
               {
               case token::k_signed:
+                {
+                  r += " signed";
+                  t = lexer_->next ();
+                  break;
+                }
               case token::k_unsigned:
                 {
+                  r += " unsigned";
                   t = lexer_->next ();
+                  break;
                 }
               default:
                 break;
@@ -697,12 +893,20 @@ fundamental_type (token& t)
     }
   case token::k_char:
     {
+      r = "char";
       switch ((t = lexer_->next ()).keyword ())
       {
       case token::k_signed:
+        {
+          r += " signed";
+          t = lexer_->next ();
+          break;
+        }
       case token::k_unsigned:
         {
+          r += " unsigned";
           t = lexer_->next ();
+          break;
         }
       default:
         break;
@@ -710,18 +914,31 @@ fundamental_type (token& t)
       break;
     }
   case token::k_bool:
+    {
+      r = "bool";
+      t = lexer_->next ();
+      break;
+    }
   case token::k_wchar:
+    {
+      r = "wchar_t";
+      t = lexer_->next ();
+      break;
+    }
   case token::k_float:
     {
+      r = "float";
       t = lexer_->next ();
       break;
     }
   case token::k_double:
     {
+      r = "double";
       switch ((t = lexer_->next ()).keyword ())
       {
       case token::k_long:
         {
+          r += " long";
           t = lexer_->next ();
         }
       default:
diff --git a/cli/parser.hxx b/cli/parser.hxx
index f09816f..458efbc 100644
--- a/cli/parser.hxx
+++ b/cli/parser.hxx
@@ -7,8 +7,12 @@
 #define CLI_PARSER_HXX
 
 #include <string>
+#include <memory> // std::auto_ptr
 #include <istream>
 
+#include <semantics/elements.hxx>
+#include <semantics/unit.hxx>
+
 class token;
 class lexer;
 
@@ -17,7 +21,7 @@ class parser
 public:
   struct invalid_input {};
 
-  void
+  std::auto_ptr<semantics::cli_unit>
   parse (std::istream& is, std::string const& id);
 
 private:
@@ -42,10 +46,10 @@ private:
   option_def (token&);
 
   bool
-  qualified_name (token&);
+  qualified_name (token&, std::string& name);
 
   bool
-  fundamental_type (token&);
+  fundamental_type (token&, std::string& name);
 
 private:
   void
@@ -53,8 +57,12 @@ private:
 
 private:
   bool valid_;
-  lexer* lexer_;
   std::string const* id_;
+
+  lexer* lexer_;
+
+  semantics::cli_unit* unit_;
+  semantics::scope* scope_;
 };
 
 #endif // CLI_PARSER_HXX
diff --git a/cli/semantics.hxx b/cli/semantics.hxx
new file mode 100644
index 0000000..4508ab2
--- /dev/null
+++ b/cli/semantics.hxx
@@ -0,0 +1,16 @@
+// file      : cli/semantics.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_SEMANTICS_HXX
+#define CLI_SEMANTICS_HXX
+
+#include <semantics/class.hxx>
+#include <semantics/elements.hxx>
+#include <semantics/expression.hxx>
+#include <semantics/namespace.hxx>
+#include <semantics/option.hxx>
+#include <semantics/unit.hxx>
+
+#endif // CLI_SEMANTICS_HXX
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 <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; 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;
+
+        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 <boris@codesynthesis.com>
+// 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 <semantics/elements.hxx>
+
+namespace semantics
+{
+  class class_: public scope
+  {
+  protected:
+    friend class graph<node, edge>;
+
+    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 <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/elements.hxx>
+
+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 <boris@codesynthesis.com>
+// 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 <map>
+#include <list>
+#include <vector>
+#include <string>
+#include <cstddef> // std::size_t
+#include <cstdlib> // std::abort
+#include <utility> // std::pair
+#include <cassert>
+
+#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;
+
+
+  //
+  //
+  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 <typename X>
+    bool
+    is_a () const
+    {
+      return dynamic_cast<X const*> (this) != 0;
+    }
+
+  protected:
+    friend class graph<node, edge>;
+
+  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 <typename X>
+    bool
+    is_a () const
+    {
+      return dynamic_cast<X const*> (this) != 0;
+    }
+
+  protected:
+    friend class graph<node, edge>;
+
+    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_type> 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<node, edge>;
+
+    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<node, edge>;
+
+    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*> names_list;
+    typedef std::map<names*, names_list::iterator> list_iterator_map;
+    typedef std::map<name_type, 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:
+    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<node, edge>;
+
+    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<node, edge>;
+
+    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 <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/expression.hxx>
+
+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 <boris@codesynthesis.com>
+// 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 <string>
+#include <semantics/elements.hxx>
+
+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<node, edge>;
+
+    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 <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; 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/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 <boris@codesynthesis.com>
+// 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 <semantics/elements.hxx>
+
+namespace semantics
+{
+  class namespace_: public scope
+  {
+  protected:
+    friend class graph<node, edge>;
+
+    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 <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <cutl/compiler/type-info.hxx>
+
+#include <semantics/option.hxx>
+
+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 <boris@codesynthesis.com>
+// 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 <semantics/elements.hxx>
+
+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<node, edge>;
+
+    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<node, edge>;
+
+    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<node, edge>;
+
+    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 <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; 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;
+
+        // 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 <boris@codesynthesis.com>
+// 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 <map>
+#include <vector>
+
+#include <semantics/elements.hxx>
+#include <semantics/namespace.hxx>
+
+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<node, edge>;
+
+    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<node, edge>;
+
+    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<node, edge>;
+
+    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<node, edge>;
+
+    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<node, edge>, public namespace_
+  {
+    typedef std::vector<includes*> includes_list;
+
+  public:
+    typedef
+    pointer_iterator<includes_list::const_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<global_names> (*this, *this);
+    }
+
+  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);
+    }
+
+  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<type> (file, l, c, name));
+    }
+
+  protected:
+    // Special names edge for the global namespace.
+    //
+    class global_names: public names
+    {
+    protected:
+      friend class graph<node, edge>;
+
+      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<node, edge>;
+
+    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<node, edge>&
+    graph ()
+    {
+      return *this;
+    }
+
+  private:
+    typedef std::map<string, type*> type_map;
+
+  private:
+    includes_list includes_;
+    type_map types_;
+  };
+}
+
+#endif // CLI_SEMANTICS_UNIT_HXX
diff --git a/cli/traversal.hxx b/cli/traversal.hxx
new file mode 100644
index 0000000..5aae8d4
--- /dev/null
+++ b/cli/traversal.hxx
@@ -0,0 +1,16 @@
+// file      : cli/traversal.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_HXX
+#define CLI_TRAVERSAL_HXX
+
+#include <traversal/class.hxx>
+#include <traversal/elements.hxx>
+#include <traversal/expression.hxx>
+#include <traversal/namespace.hxx>
+#include <traversal/option.hxx>
+#include <traversal/unit.hxx>
+
+#endif // CLI_TRAVERSAL_HXX
diff --git a/cli/traversal/class.cxx b/cli/traversal/class.cxx
new file mode 100644
index 0000000..54af3e1
--- /dev/null
+++ b/cli/traversal/class.cxx
@@ -0,0 +1,27 @@
+// file      : cli/traversal/class.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <traversal/class.hxx>
+
+namespace traversal
+{
+  void class_::
+  traverse (type& c)
+  {
+    pre (c);
+    names (c);
+    post (c);
+  }
+
+  void class_::
+  pre (type&)
+  {
+  }
+
+  void class_::
+  post (type&)
+  {
+  }
+}
diff --git a/cli/traversal/class.hxx b/cli/traversal/class.hxx
new file mode 100644
index 0000000..d4610d9
--- /dev/null
+++ b/cli/traversal/class.hxx
@@ -0,0 +1,27 @@
+// file      : cli/traversal/class.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_CLASS_HXX
+#define CLI_TRAVERSAL_CLASS_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/class.hxx>
+
+namespace traversal
+{
+  struct class_: scope_template<semantics::class_>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    pre (type&);
+
+    virtual void
+    post (type&);
+  };
+}
+
+#endif // CLI_TRAVERSAL_CLASS_HXX
diff --git a/cli/traversal/elements.cxx b/cli/traversal/elements.cxx
new file mode 100644
index 0000000..acabc3c
--- /dev/null
+++ b/cli/traversal/elements.cxx
@@ -0,0 +1,15 @@
+// file      : cli/traversal/elements.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <traversal/elements.hxx>
+
+namespace traversal
+{
+  void names::
+  traverse (type& e)
+  {
+    dispatch (e.named ());
+  }
+}
diff --git a/cli/traversal/elements.hxx b/cli/traversal/elements.hxx
new file mode 100644
index 0000000..ac57af4
--- /dev/null
+++ b/cli/traversal/elements.hxx
@@ -0,0 +1,143 @@
+// file      : cli/traversal/elements.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_ELEMENTS_HXX
+#define CLI_TRAVERSAL_ELEMENTS_HXX
+
+#include <cutl/compiler/traversal.hxx>
+
+#include <semantics/elements.hxx>
+
+namespace traversal
+{
+  using namespace cutl;
+
+  //
+  //
+  typedef compiler::dispatcher<semantics::node> node_dispatcher;
+  typedef compiler::dispatcher<semantics::edge> edge_dispatcher;
+
+  //
+  //
+  struct node_base: node_dispatcher, edge_dispatcher
+  {
+    void
+    edge_traverser (edge_dispatcher& d)
+    {
+      edge_dispatcher::traverser (d);
+    }
+
+    edge_dispatcher&
+    edge_traverser ()
+    {
+      return *this;
+    }
+
+    using node_dispatcher::dispatch;
+    using edge_dispatcher::dispatch;
+
+    using edge_dispatcher::iterate_and_dispatch;
+  };
+
+  struct edge_base: edge_dispatcher, node_dispatcher
+  {
+    void
+    node_traverser (node_dispatcher& d)
+    {
+      node_dispatcher::traverser (d);
+    }
+
+    node_dispatcher&
+    node_traverser ()
+    {
+      return *this;
+    }
+
+    using edge_dispatcher::dispatch;
+    using node_dispatcher::dispatch;
+
+    using node_dispatcher::iterate_and_dispatch;
+  };
+
+  inline edge_base&
+  operator>> (node_base& n, edge_base& e)
+  {
+    n.edge_traverser (e);
+    return e;
+  }
+
+  inline node_base&
+  operator>> (edge_base& e, node_base& n)
+  {
+    e.node_traverser (n);
+    return n;
+  }
+
+  //
+  //
+  template <typename X>
+  struct node: compiler::traverser_impl<X, semantics::node>,
+               virtual node_base
+  {
+  };
+
+  template <typename X>
+  struct edge: compiler::traverser_impl<X, semantics::edge>,
+               virtual edge_base
+  {
+  };
+
+  // Edges
+  //
+
+  struct names: edge<semantics::names>
+  {
+    names ()
+    {
+    }
+
+    names (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  // Nodes
+  //
+
+  struct nameable: node<semantics::nameable> {};
+
+  template <typename T>
+  struct scope_template: node<T>
+  {
+  public:
+    virtual void
+    traverse (T& s)
+    {
+      names (s);
+    }
+
+    virtual void
+    names (T& s)
+    {
+      names (s, *this);
+    }
+
+    virtual void
+    names (T& s, edge_dispatcher& d)
+    {
+      iterate_and_dispatch (s.names_begin (), s.names_end (), d);
+    }
+  };
+
+  typedef scope_template<semantics::scope> scope;
+
+  struct type: node<semantics::type> {};
+}
+
+#endif // CLI_TRAVERSAL_ELEMENTS_HXX
diff --git a/cli/traversal/expression.hxx b/cli/traversal/expression.hxx
new file mode 100644
index 0000000..71d9f6e
--- /dev/null
+++ b/cli/traversal/expression.hxx
@@ -0,0 +1,17 @@
+// file      : cli/traversal/expression.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_EXPRESSION_HXX
+#define CLI_TRAVERSAL_EXPRESSION_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/expression.hxx>
+
+namespace traversal
+{
+  struct expression: node<semantics::expression> {};
+}
+
+#endif // CLI_TRAVERSAL_EXPRESSION_HXX
diff --git a/cli/traversal/namespace.cxx b/cli/traversal/namespace.cxx
new file mode 100644
index 0000000..47547db
--- /dev/null
+++ b/cli/traversal/namespace.cxx
@@ -0,0 +1,27 @@
+// file      : cli/traversal/namespace.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <traversal/namespace.hxx>
+
+namespace traversal
+{
+  void namespace_::
+  traverse (type& n)
+  {
+    pre (n);
+    names (n);
+    post (n);
+  }
+
+  void namespace_::
+  pre (type&)
+  {
+  }
+
+  void namespace_::
+  post (type&)
+  {
+  }
+}
diff --git a/cli/traversal/namespace.hxx b/cli/traversal/namespace.hxx
new file mode 100644
index 0000000..5903582
--- /dev/null
+++ b/cli/traversal/namespace.hxx
@@ -0,0 +1,27 @@
+// file      : cli/traversal/namespace.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_NAMESPACE_HXX
+#define CLI_TRAVERSAL_NAMESPACE_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/namespace.hxx>
+
+namespace traversal
+{
+  struct namespace_: scope_template<semantics::namespace_>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    pre (type&);
+
+    virtual void
+    post (type&);
+  };
+}
+
+#endif // CLI_TRAVERSAL_NAMESPACE_HXX
diff --git a/cli/traversal/option.cxx b/cli/traversal/option.cxx
new file mode 100644
index 0000000..64e728c
--- /dev/null
+++ b/cli/traversal/option.cxx
@@ -0,0 +1,60 @@
+// file      : cli/traversal/option.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <traversal/option.hxx>
+#include <traversal/expression.hxx>
+
+namespace traversal
+{
+  // belongs
+  //
+  void belongs::
+  traverse (type& e)
+  {
+    dispatch (e.type ());
+  }
+
+  // initialized
+  //
+  void initialized::
+  traverse (type& e)
+  {
+    dispatch (e.expression ());
+  }
+
+  // option
+  //
+  void option::
+  traverse (type& o)
+  {
+    pre (o);
+    belongs (o);
+    if (o.initialized_p ())
+      initialized (o);
+    post (o);
+  }
+
+  void option::
+  pre (type&)
+  {
+  }
+
+  void option::
+  belongs (type& o)
+  {
+    belongs (o, edge_traverser ());
+  }
+
+  void option::
+  initialized (type& o)
+  {
+    initialized (o, edge_traverser ());
+  }
+
+  void option::
+  post (type&)
+  {
+  }
+}
diff --git a/cli/traversal/option.hxx b/cli/traversal/option.hxx
new file mode 100644
index 0000000..4ff2a58
--- /dev/null
+++ b/cli/traversal/option.hxx
@@ -0,0 +1,75 @@
+// file      : cli/traversal/option.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_OPTION_HXX
+#define CLI_TRAVERSAL_OPTION_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/option.hxx>
+
+namespace traversal
+{
+  struct belongs: edge<semantics::belongs>
+  {
+    belongs ()
+    {
+    }
+
+    belongs (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct initialized: edge<semantics::initialized>
+  {
+    initialized ()
+    {
+    }
+
+    initialized (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct option: node<semantics::option>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    pre (type&);
+
+    virtual void
+    belongs (type&);
+
+    virtual void
+    initialized (type&);
+
+    virtual void
+    post (type&);
+
+    void
+    belongs (type& o, edge_dispatcher& d)
+    {
+      d.dispatch (o.belongs ());
+    }
+
+    void
+    initialized (type& o, edge_dispatcher& d)
+    {
+      d.dispatch (o.initialized ());
+    }
+  };
+}
+
+#endif // CLI_TRAVERSAL_OPTION_HXX
diff --git a/cli/traversal/unit.cxx b/cli/traversal/unit.cxx
new file mode 100644
index 0000000..32b2e0d
--- /dev/null
+++ b/cli/traversal/unit.cxx
@@ -0,0 +1,47 @@
+// file      : cli/traversal/unit.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#include <traversal/unit.hxx>
+
+namespace traversal
+{
+  // cxx_includes
+  //
+  void cxx_includes::
+  traverse (type& e)
+  {
+    dispatch (e.includee ());
+  }
+
+  // cli_includes
+  //
+  void cli_includes::
+  traverse (type& e)
+  {
+    dispatch (e.includee ());
+  }
+
+  // cli_unit
+  //
+  void cli_unit::
+  traverse (type& u)
+  {
+    pre (u);
+    iterate_and_dispatch (
+      u.includes_begin (), u.includes_end (), edge_traverser ());
+    names (u);
+    post (u);
+  }
+
+  void cli_unit::
+  pre (type&)
+  {
+  }
+
+  void cli_unit::
+  post (type&)
+  {
+  }
+}
diff --git a/cli/traversal/unit.hxx b/cli/traversal/unit.hxx
new file mode 100644
index 0000000..25ec556
--- /dev/null
+++ b/cli/traversal/unit.hxx
@@ -0,0 +1,59 @@
+// file      : cli/traversal/unit.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2009 Code Synthesis Tools CC
+// license   : MIT; see accompanying LICENSE file
+
+#ifndef CLI_TRAVERSAL_UNIT_HXX
+#define CLI_TRAVERSAL_UNIT_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/unit.hxx>
+
+namespace traversal
+{
+  struct cxx_includes: edge<semantics::cxx_includes>
+  {
+    cxx_includes ()
+    {
+    }
+
+    cxx_includes (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct cli_includes: edge<semantics::cli_includes>
+  {
+    cli_includes ()
+    {
+    }
+
+    cli_includes (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct cxx_unit: node<semantics::cxx_unit> {};
+
+  struct cli_unit: scope_template<semantics::cli_unit>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    pre (type&);
+
+    virtual void
+    post (type&);
+  };
+}
+
+#endif // CLI_TRAVERSAL_UNIT_HXX
-- 
cgit v1.1