Implement semantic graph traversal mechanism

18 files changed, 1095 insertions, 0 deletions

diff --git a/odb/traversal/class-template.cxx b/odb/traversal/class-template.cxx
new file mode 100644
index 0000000..457e69a
--- /dev/null
+++ b/odb/traversal/class-template.cxx
@@ -0,0 +1,64 @@
+// file      : odb/traversal/class-template.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 <traversal/class-template.hxx>
+
+namespace traversal
+{
+  //
+  //
+  void class_template::
+  traverse (type& c)
+  {
+    inherits (c);
+    names (c);
+  }
+
+  void class_template::
+  inherits (type& c)
+  {
+    inherits (c, *this);
+  }
+
+  void class_template::
+  inherits (type& c, edge_dispatcher& d)
+  {
+    iterate_and_dispatch (c.inherits_begin (), c.inherits_end (), d);
+  }
+
+  //
+  //
+  void class_instantiation::
+  traverse (type& c)
+  {
+    instantiates (c);
+    inherits (c);
+    names (c);
+  }
+
+  void class_instantiation::
+  instantiates (type& c)
+  {
+    instantiates (c, *this);
+  }
+
+  void class_instantiation::
+  instantiates (type& c, edge_dispatcher& d)
+  {
+    d.dispatch (c.instantiates ());
+  }
+
+  void class_instantiation::
+  inherits (type& c)
+  {
+    inherits (c, *this);
+  }
+
+  void class_instantiation::
+  inherits (type& c, edge_dispatcher& d)
+  {
+    iterate_and_dispatch (c.inherits_begin (), c.inherits_end (), d);
+  }
+}
diff --git a/odb/traversal/class-template.hxx b/odb/traversal/class-template.hxx
new file mode 100644
index 0000000..a5fd798
--- /dev/null
+++ b/odb/traversal/class-template.hxx
@@ -0,0 +1,46 @@
+// file      : odb/traversal/class-template.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_TRAVERSAL_CLASS_TEMPLATE_HXX
+#define ODB_TRAVERSAL_CLASS_TEMPLATE_HXX
+
+#include <traversal/elements.hxx>
+#include <traversal/class.hxx>
+#include <semantics/class-template.hxx>
+
+namespace traversal
+{
+  struct class_template: scope_template<semantics::class_template>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    inherits (type&);
+
+    virtual void
+    inherits (type&, edge_dispatcher&);
+  };
+
+  struct class_instantiation: scope_template<semantics::class_instantiation>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    instantiates (type&);
+
+    virtual void
+    instantiates (type&, edge_dispatcher&);
+
+    virtual void
+    inherits (type&);
+
+    virtual void
+    inherits (type&, edge_dispatcher&);
+  };
+}
+
+#endif // ODB_TRAVERSAL_CLASS_TEMPLATE_HXX
diff --git a/odb/traversal/class.cxx b/odb/traversal/class.cxx
new file mode 100644
index 0000000..752bd10
--- /dev/null
+++ b/odb/traversal/class.cxx
@@ -0,0 +1,36 @@
+// file      : odb/traversal/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 <traversal/class.hxx>
+
+namespace traversal
+{
+  void inherits::
+  traverse (type& i)
+  {
+    dispatch (i.base ());
+  }
+
+  //
+  //
+  void class_::
+  traverse (type& c)
+  {
+    inherits (c);
+    names (c);
+  }
+
+  void class_::
+  inherits (type& c)
+  {
+    inherits (c, *this);
+  }
+
+  void class_::
+  inherits (type& c, edge_dispatcher& d)
+  {
+    iterate_and_dispatch (c.inherits_begin (), c.inherits_end (), d);
+  }
+}
diff --git a/odb/traversal/class.hxx b/odb/traversal/class.hxx
new file mode 100644
index 0000000..d871832
--- /dev/null
+++ b/odb/traversal/class.hxx
@@ -0,0 +1,42 @@
+// file      : odb/traversal/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_TRAVERSAL_CLASS_HXX
+#define ODB_TRAVERSAL_CLASS_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/class.hxx>
+
+namespace traversal
+{
+  struct inherits: edge<semantics::inherits>
+  {
+    inherits ()
+    {
+    }
+
+    inherits (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct class_: scope_template<semantics::class_>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    inherits (type&);
+
+    virtual void
+    inherits (type&, edge_dispatcher&);
+  };
+}
+
+#endif // ODB_TRAVERSAL_CLASS_HXX
diff --git a/odb/traversal/derived.cxx b/odb/traversal/derived.cxx
new file mode 100644
index 0000000..ed75835
--- /dev/null
+++ b/odb/traversal/derived.cxx
@@ -0,0 +1,113 @@
+// file      : odb/traversal/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 <traversal/derived.hxx>
+
+namespace traversal
+{
+  void qualifies::
+  traverse (type& e)
+  {
+    dispatch (e.type ());
+  }
+
+  void points::
+  traverse (type& e)
+  {
+    dispatch (e.type ());
+  }
+
+  void references::
+  traverse (type& e)
+  {
+    dispatch (e.type ());
+  }
+
+  void contains::
+  traverse (type& e)
+  {
+    dispatch (e.type ());
+  }
+
+  //
+  //
+  void qualifier::
+  traverse (type& q)
+  {
+    qualifies (q);
+  }
+
+  void qualifier::
+  qualifies (type& q)
+  {
+    qualifies (q, *this);
+  }
+
+  void qualifier::
+  qualifies (type& q, edge_dispatcher& d)
+  {
+    d.dispatch (q.qualifies ());
+  }
+
+  //
+  //
+  void pointer::
+  traverse (type& p)
+  {
+    points (p);
+  }
+
+  void pointer::
+  points (type& p)
+  {
+    points (p, *this);
+  }
+
+  void pointer::
+  points (type& p, edge_dispatcher& d)
+  {
+    d.dispatch (p.points ());
+  }
+
+  //
+  //
+  void reference::
+  traverse (type& r)
+  {
+    references (r);
+  }
+
+  void reference::
+  references (type& r)
+  {
+    references (r, *this);
+  }
+
+  void reference::
+  references (type& r, edge_dispatcher& d)
+  {
+    d.dispatch (r.references ());
+  }
+
+  //
+  //
+  void array::
+  traverse (type& a)
+  {
+    contains (a);
+  }
+
+  void array::
+  contains (type& a)
+  {
+    contains (a, *this);
+  }
+
+  void array::
+  contains (type& a, edge_dispatcher& d)
+  {
+    d.dispatch (a.contains ());
+  }
+}
diff --git a/odb/traversal/derived.hxx b/odb/traversal/derived.hxx
new file mode 100644
index 0000000..5af31af
--- /dev/null
+++ b/odb/traversal/derived.hxx
@@ -0,0 +1,132 @@
+// file      : odb/traversal/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_TRAVERSAL_DERIVED_HXX
+#define ODB_TRAVERSAL_DERIVED_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/derived.hxx>
+
+namespace traversal
+{
+  //
+  // Edges.
+  //
+  struct qualifies: edge<semantics::qualifies>
+  {
+    qualifies ()
+    {
+    }
+
+    qualifies (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct points: edge<semantics::points>
+  {
+    points ()
+    {
+    }
+
+    points (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct references: edge<semantics::references>
+  {
+    references ()
+    {
+    }
+
+    references (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct contains: edge<semantics::contains>
+  {
+    contains ()
+    {
+    }
+
+    contains (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+
+  //
+  // Nodes.
+  //
+  struct derived_type: node<semantics::derived_type> {};
+
+  struct qualifier: node<semantics::qualifier>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    qualifies (type&);
+
+    virtual void
+    qualifies (type&, edge_dispatcher&);
+  };
+
+  struct pointer: node<semantics::pointer>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    points (type&);
+
+    virtual void
+    points (type&, edge_dispatcher&);
+  };
+
+  struct reference: node<semantics::reference>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    references (type&);
+
+    virtual void
+    references (type&, edge_dispatcher&);
+  };
+
+  struct array: node<semantics::array>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    contains (type&);
+
+    virtual void
+    contains (type&, edge_dispatcher&);
+  };
+}
+
+#endif // ODB_TRAVERSAL_DERIVED_HXX
diff --git a/odb/traversal/elements.cxx b/odb/traversal/elements.cxx
new file mode 100644
index 0000000..62f3eab
--- /dev/null
+++ b/odb/traversal/elements.cxx
@@ -0,0 +1,79 @@
+// file      : odb/traversal/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 <traversal/elements.hxx>
+
+namespace traversal
+{
+  void names::
+  traverse (type& e)
+  {
+    dispatch (e.named ());
+  }
+
+  void declares::
+  traverse (type& e)
+  {
+    dispatch (e.named ());
+  }
+
+  void defines::
+  traverse (type& e)
+  {
+    dispatch (e.named ());
+  }
+
+  void typedefs::
+  traverse (type& e)
+  {
+    dispatch (e.named ());
+  }
+
+  void belongs::
+  traverse (type& e)
+  {
+    dispatch (e.type ());
+  }
+
+  // instance
+  //
+  void instance::
+  traverse (type& i)
+  {
+    belongs (i);
+  }
+
+  void instance::
+  belongs (type& i)
+  {
+    belongs (i, *this);
+  }
+
+  void instance::
+  belongs (type& i, edge_dispatcher& d)
+  {
+    d.dispatch (i.belongs ());
+  }
+
+  // data_member
+  //
+  void data_member::
+  traverse (type& m)
+  {
+    belongs (m);
+  }
+
+  void data_member::
+  belongs (type& m)
+  {
+    belongs (m, *this);
+  }
+
+  void data_member::
+  belongs (type& m, edge_dispatcher& d)
+  {
+    d.dispatch (m.belongs ());
+  }
+}
diff --git a/odb/traversal/elements.hxx b/odb/traversal/elements.hxx
new file mode 100644
index 0000000..be21b63
--- /dev/null
+++ b/odb/traversal/elements.hxx
@@ -0,0 +1,241 @@
+// file      : odb/traversal/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_TRAVERSAL_ELEMENTS_HXX
+#define ODB_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&);
+  };
+
+  struct declares: edge<semantics::declares>
+  {
+    declares ()
+    {
+    }
+
+    declares (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct defines: edge<semantics::defines>
+  {
+    defines ()
+    {
+    }
+
+    defines (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct typedefs: edge<semantics::typedefs>
+  {
+    typedefs ()
+    {
+    }
+
+    typedefs (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct belongs: edge<semantics::belongs>
+  {
+    belongs ()
+    {
+    }
+
+    belongs (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);
+    }
+  };
+
+  struct scope: scope_template<semantics::scope> {};
+
+  //
+  //
+  struct type: node<semantics::type> {};
+
+  //
+  //
+  struct instance: node<semantics::instance>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    belongs (type&);
+
+    virtual void
+    belongs (type&, edge_dispatcher&);
+  };
+
+  //
+  //
+  struct data_member: node<semantics::data_member>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    belongs (type&);
+
+    virtual void
+    belongs (type&, edge_dispatcher&);
+  };
+
+  //
+  //
+  struct unsupported_type: node<semantics::unsupported_type> {};
+}
+
+#endif // ODB_TRAVERSAL_ELEMENTS_HXX
diff --git a/odb/traversal/enum.cxx b/odb/traversal/enum.cxx
new file mode 100644
index 0000000..ae04531
--- /dev/null
+++ b/odb/traversal/enum.cxx
@@ -0,0 +1,35 @@
+// file      : odb/traversal/enum.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 <traversal/enum.hxx>
+
+namespace traversal
+{
+  void enumerates::
+  traverse (type& e)
+  {
+    dispatch (e.enumerator ());
+  }
+
+  //
+  //
+  void enum_::
+  traverse (type& e)
+  {
+    enumerates (e);
+  }
+
+  void enum_::
+  enumerates (type& e)
+  {
+    enumerates (e, *this);
+  }
+
+  void enum_::
+  enumerates (type& e, edge_dispatcher& d)
+  {
+    iterate_and_dispatch (e.enumerates_begin (), e.enumerates_end (), d);
+  }
+}
diff --git a/odb/traversal/enum.hxx b/odb/traversal/enum.hxx
new file mode 100644
index 0000000..ee4d8c3
--- /dev/null
+++ b/odb/traversal/enum.hxx
@@ -0,0 +1,44 @@
+// file      : odb/traversal/enum.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_TRAVERSAL_ENUM_HXX
+#define ODB_TRAVERSAL_ENUM_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/enum.hxx>
+
+namespace traversal
+{
+  struct enumerates: edge<semantics::enumerates>
+  {
+    enumerates ()
+    {
+    }
+
+    enumerates (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct enumerator: node<semantics::enumerator> {};
+
+  struct enum_: node<semantics::enum_>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    enumerates (type&);
+
+    virtual void
+    enumerates (type&, edge_dispatcher&);
+  };
+}
+
+#endif // ODB_TRAVERSAL_ENUM_HXX
diff --git a/odb/traversal/fundamental.hxx b/odb/traversal/fundamental.hxx
new file mode 100644
index 0000000..e34fb02
--- /dev/null
+++ b/odb/traversal/fundamental.hxx
@@ -0,0 +1,41 @@
+// file      : odb/traversal/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_TRAVERSAL_FUNDAMENTAL_HXX
+#define ODB_TRAVERSAL_FUNDAMENTAL_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/fundamental.hxx>
+
+namespace traversal
+{
+  struct fund_type: node<semantics::fund_type> {};
+
+  struct fund_void: node<semantics::fund_void> {};
+  struct fund_bool: node<semantics::fund_bool> {};
+
+  // Integral.
+  //
+  struct fund_char: node<semantics::fund_char> {};
+  struct fund_wchar: node<semantics::fund_wchar> {};
+  struct fund_signed_char: node<semantics::fund_signed_char> {};
+  struct fund_unsigned_char: node<semantics::fund_unsigned_char> {};
+  struct fund_short: node<semantics::fund_short> {};
+  struct fund_unsigned_short: node<semantics::fund_unsigned_short> {};
+  struct fund_int: node<semantics::fund_int> {};
+  struct fund_unsigned_int: node<semantics::fund_unsigned_int> {};
+  struct fund_long: node<semantics::fund_long> {};
+  struct fund_unsigned_long: node<semantics::fund_unsigned_long> {};
+  struct fund_long_long: node<semantics::fund_long_long> {};
+  struct fund_unsigned_long_long: node<semantics::fund_unsigned_long_long> {};
+
+  // Real.
+  //
+  struct fund_float: node<semantics::fund_float> {};
+  struct fund_double: node<semantics::fund_double> {};
+  struct fund_long_double: node<semantics::fund_long_double> {};
+}
+
+#endif // ODB_TRAVERSAL_FUNDAMENTAL_HXX
diff --git a/odb/traversal/namespace.hxx b/odb/traversal/namespace.hxx
new file mode 100644
index 0000000..c1c129d
--- /dev/null
+++ b/odb/traversal/namespace.hxx
@@ -0,0 +1,17 @@
+// file      : odb/traversal/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_TRAVERSAL_NAMESPACE_HXX
+#define ODB_TRAVERSAL_NAMESPACE_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/namespace.hxx>
+
+namespace traversal
+{
+  struct namespace_: scope_template<semantics::namespace_> {};
+}
+
+#endif // ODB_TRAVERSAL_NAMESPACE_HXX
diff --git a/odb/traversal/template.cxx b/odb/traversal/template.cxx
new file mode 100644
index 0000000..352a605
--- /dev/null
+++ b/odb/traversal/template.cxx
@@ -0,0 +1,55 @@
+// file      : odb/traversal/template.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 <traversal/template.hxx>
+
+namespace traversal
+{
+  void instantiates::
+  traverse (type& i)
+  {
+    dispatch (i.template_ ());
+  }
+
+  //
+  //
+  void instantiation::
+  traverse (type& i)
+  {
+    instantiates (i);
+  }
+
+  void instantiation::
+  instantiates (type& i)
+  {
+    instantiates (i, *this);
+  }
+
+  void instantiation::
+  instantiates (type& i, edge_dispatcher& d)
+  {
+    d.dispatch (i.instantiates ());
+  }
+
+  //
+  //
+  void type_instantiation::
+  traverse (type& i)
+  {
+    instantiates (i);
+  }
+
+  void type_instantiation::
+  instantiates (type& i)
+  {
+    instantiates (i, *this);
+  }
+
+  void type_instantiation::
+  instantiates (type& i, edge_dispatcher& d)
+  {
+    d.dispatch (i.instantiates ());
+  }
+}
diff --git a/odb/traversal/template.hxx b/odb/traversal/template.hxx
new file mode 100644
index 0000000..0ff8237
--- /dev/null
+++ b/odb/traversal/template.hxx
@@ -0,0 +1,58 @@
+// file      : odb/traversal/template.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_TRAVERSAL_TEMPLATE_HXX
+#define ODB_TRAVERSAL_TEMPLATE_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/template.hxx>
+
+namespace traversal
+{
+  struct instantiates: edge<semantics::instantiates>
+  {
+    instantiates ()
+    {
+    }
+
+    instantiates (node_dispatcher& n)
+    {
+      node_traverser (n);
+    }
+
+    virtual void
+    traverse (type&);
+  };
+
+  struct template_: node<semantics::template_> {};
+
+  struct instantiation: node<semantics::instantiation>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    instantiates (type&);
+
+    virtual void
+    instantiates (type&, edge_dispatcher&);
+  };
+
+  struct type_template: node<semantics::type_template> {};
+
+  struct type_instantiation: node<semantics::type_instantiation>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    instantiates (type&);
+
+    virtual void
+    instantiates (type&, edge_dispatcher&);
+  };
+}
+
+#endif // ODB_TRAVERSAL_TEMPLATE_HXX
diff --git a/odb/traversal/union-template.cxx b/odb/traversal/union-template.cxx
new file mode 100644
index 0000000..e4f7cdf
--- /dev/null
+++ b/odb/traversal/union-template.cxx
@@ -0,0 +1,28 @@
+// file      : odb/traversal/union-template.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 <traversal/union-template.hxx>
+
+namespace traversal
+{
+  void union_instantiation::
+  traverse (type& u)
+  {
+    instantiates (u);
+    names (u);
+  }
+
+  void union_instantiation::
+  instantiates (type& u)
+  {
+    instantiates (u, *this);
+  }
+
+  void union_instantiation::
+  instantiates (type& u, edge_dispatcher& d)
+  {
+    d.dispatch (u.instantiates ());
+  }
+}
diff --git a/odb/traversal/union-template.hxx b/odb/traversal/union-template.hxx
new file mode 100644
index 0000000..4a7a0d7
--- /dev/null
+++ b/odb/traversal/union-template.hxx
@@ -0,0 +1,30 @@
+// file      : odb/traversal/union-template.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_TRAVERSAL_UNION_TEMPLATE_HXX
+#define ODB_TRAVERSAL_UNION_TEMPLATE_HXX
+
+#include <traversal/elements.hxx>
+#include <traversal/union.hxx>
+#include <semantics/union-template.hxx>
+
+namespace traversal
+{
+  struct union_template: scope_template<semantics::union_template> {};
+
+  struct union_instantiation: scope_template<semantics::union_instantiation>
+  {
+    virtual void
+    traverse (type&);
+
+    virtual void
+    instantiates (type&);
+
+    virtual void
+    instantiates (type&, edge_dispatcher&);
+  };
+}
+
+#endif // ODB_TRAVERSAL_UNION_TEMPLATE_HXX
diff --git a/odb/traversal/union.hxx b/odb/traversal/union.hxx
new file mode 100644
index 0000000..bd828ff
--- /dev/null
+++ b/odb/traversal/union.hxx
@@ -0,0 +1,17 @@
+// file      : odb/traversal/union.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_TRAVERSAL_UNION_HXX
+#define ODB_TRAVERSAL_UNION_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/union.hxx>
+
+namespace traversal
+{
+  struct union_: scope_template<semantics::union_> {};
+}
+
+#endif // ODB_TRAVERSAL_UNION_HXX
diff --git a/odb/traversal/unit.hxx b/odb/traversal/unit.hxx
new file mode 100644
index 0000000..f15c5fd
--- /dev/null
+++ b/odb/traversal/unit.hxx
@@ -0,0 +1,17 @@
+// file      : odb/traversal/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_TRAVERSAL_UNIT_HXX
+#define ODB_TRAVERSAL_UNIT_HXX
+
+#include <traversal/elements.hxx>
+#include <semantics/unit.hxx>
+
+namespace traversal
+{
+  struct unit: scope_template<semantics::unit> {};
+}
+
+#endif // ODB_TRAVERSAL_UNIT_HXX