Imported Upstream version 3.3.0.2upstream/3.3.0.2

14 files changed, 1213 insertions, 0 deletions

diff --git a/libfrontend-elements/frontend-elements/context.cxx b/libfrontend-elements/frontend-elements/context.cxx
new file mode 100644
index 0000000..295ce74
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/context.cxx
@@ -0,0 +1,11 @@
+// file      : frontend-elements/context.cxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#include <frontend-elements/context.hxx>
+
+namespace FrontendElements
+{
+}
+
diff --git a/libfrontend-elements/frontend-elements/context.hxx b/libfrontend-elements/frontend-elements/context.hxx
new file mode 100644
index 0000000..9a31da2
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/context.hxx
@@ -0,0 +1,133 @@
+// file      : frontend-elements/context.hxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#ifndef FRONTEND_ELEMENTS_CONTEXT_HXX
+#define FRONTEND_ELEMENTS_CONTEXT_HXX
+
+#include <frontend-elements/types.hxx>
+
+#include <cult/containers/any.hxx>
+#include <cult/containers/map.hxx>
+
+namespace FrontendElements
+{
+  class Context: public NonCopyable
+  {
+    typedef
+    Cult::Containers::Map<String, Cult::Containers::Any>
+    Map;
+
+  public:
+    struct NoEntry {};
+    struct Typing {};
+
+    Context ()
+    {
+    }
+
+    Void
+    swap (Context& c)
+    {
+      map_.swap (c.map_);
+    }
+
+    Size
+    count (Char const* key) const
+    {
+      return map_.count (key);
+    }
+
+    template <typename X>
+    X&
+    get (Char const* key)
+    {
+      Map::Iterator i (map_.find (key));
+
+      if (i == map_.end ())
+        throw NoEntry ();
+
+      try
+      {
+        return i->second. template value<X> ();
+      }
+      catch (Cult::Containers::Any::Typing const&)
+      {
+        throw Typing ();
+      }
+    }
+
+    template <typename X>
+    X const&
+    get (Char const* key) const
+    {
+      Map::ConstIterator i (map_.find (key));
+
+      if (i == map_.end ())
+        throw NoEntry ();
+
+      try
+      {
+        return i->second. template value<X> ();
+      }
+      catch (Cult::Containers::Any::Typing const&)
+      {
+        throw Typing ();
+      }
+    }
+
+    template <typename X>
+    X const&
+    get (Char const* key, X const& default_value) const
+    {
+      Map::ConstIterator i (map_.find (key));
+
+      if (i == map_.end ())
+        return default_value;
+
+      try
+      {
+        return i->second. template value<X> ();
+      }
+      catch (Cult::Containers::Any::Typing const&)
+      {
+        throw Typing ();
+      }
+    }
+
+    template <typename X>
+    Void
+    set (Char const* key, X const& value)
+    {
+      try
+      {
+        if (!map_.insert (Map::Pair (key, value)).second)
+        {
+          Map::Iterator i (map_.find (key));
+          i->second.template value <X> () = value;
+        }
+      }
+      catch (Cult::Containers::Any::Typing const&)
+      {
+        throw Typing ();
+      }
+    }
+
+    Void
+    remove (Char const* key)
+    {
+      Map::Iterator i (map_.find (key));
+
+      if (i == map_.end ())
+        throw NoEntry ();
+
+      map_.erase (i);
+    }
+
+  private:
+    Map map_;
+  };
+}
+
+#endif  // FRONTEND_ELEMENTS_CONTEXT_HXX
diff --git a/libfrontend-elements/frontend-elements/diagnostic.cxx b/libfrontend-elements/frontend-elements/diagnostic.cxx
new file mode 100644
index 0000000..c99061f
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/diagnostic.cxx
@@ -0,0 +1,41 @@
+// file      : frontend-elements/diagnostic.cxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#include <frontend-elements/diagnostic.hxx>
+
+#include <iostream>
+
+namespace FrontendElements
+{
+  namespace Diagnostic
+  {
+    using std::cerr;
+    using std::endl;
+
+    Log& Log::
+    operator<< (Record const& r)
+    {
+      cerr << r.file () << ":" << r.line ();
+
+      if (r.char_p ()) cerr << ":" << r.char_ ();
+
+      cerr << ": ";
+
+      r.kind ().print (cerr);
+
+      cerr << ": " << r.text () << endl;
+
+      return *this;
+    }
+
+    Log& Log::
+    instance ()
+    {
+      static Log l;
+      return l;
+    }
+  }
+}
+
diff --git a/libfrontend-elements/frontend-elements/diagnostic.hxx b/libfrontend-elements/frontend-elements/diagnostic.hxx
new file mode 100644
index 0000000..6cc48da
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/diagnostic.hxx
@@ -0,0 +1,364 @@
+// file      : frontend-elements/diagnostic.hxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#ifndef FRONTEND_ELEMENTS_DIAGNOSTIC_HXX
+#define FRONTEND_ELEMENTS_DIAGNOSTIC_HXX
+
+#include <frontend-elements/types.hxx>
+
+#include <ostream>
+#include <sstream>
+
+namespace FrontendElements
+{
+  namespace Diagnostic
+  {
+    struct Kind
+    {
+      virtual
+      ~Kind ()
+      {
+      }
+
+      Kind (String const& id)
+          : id_ (id)
+      {
+      }
+
+      Char const*
+      id () const
+      {
+        return id_.c_str ();
+      }
+
+      virtual std::ostream&
+      print (std::ostream& o) const = 0;
+
+    private:
+      String id_;
+    };
+
+    struct Error: Kind
+    {
+      virtual
+      ~Error ()
+      {
+      }
+
+      Error (String const& id)
+          : Kind (id)
+      {
+      }
+
+      virtual std::ostream&
+      print (std::ostream& o) const
+      {
+        return o << "error " << id ();
+      }
+    };
+
+    struct Warning: Kind
+    {
+      virtual
+      ~Warning ()
+      {
+      }
+
+      Warning (String const& id)
+          : Kind (id)
+      {
+      }
+
+      virtual std::ostream&
+      print (std::ostream& o) const
+      {
+        return o << "warning " << id ();
+      }
+    };
+
+    struct Remark: Kind
+    {
+      virtual
+      ~Remark ()
+      {
+      }
+
+      Remark (String const& id)
+          : Kind (id)
+      {
+      }
+
+      virtual std::ostream&
+      print (std::ostream& o) const
+      {
+        return o << "remark " << id ();
+      }
+    };
+
+    struct Info: Kind
+    {
+      virtual
+      ~Info ()
+      {
+      }
+
+      Info (String const& id)
+          : Kind (id)
+      {
+      }
+
+      virtual std::ostream&
+      print (std::ostream& o) const
+      {
+        return o << "info " << id ();
+      }
+    };
+
+    //
+    //
+    //
+    namespace Bits
+    {
+      class Mediator;
+    }
+
+    class Record: public NonCopyable
+    {
+    public:
+      Record (Kind const& kind,
+              String const& file,
+              UnsignedLong line,
+              UnsignedLong char_)
+          : kind_ (&kind),
+            file_p_ (true),
+            file_ (file),
+            line_p_ (true),
+            line_ (line),
+            char_p_ (true),
+            char__ (char_)
+      {
+      }
+
+      Record (Kind const& kind,
+              String const& file,
+              UnsignedLong line)
+          : kind_ (&kind),
+            file_p_ (true),
+            file_ (file),
+            line_p_ (true),
+            line_ (line),
+            char_p_ (false)
+      {
+      }
+
+    private:
+      Record ()
+          : kind_ (0),
+            file_p_ (false),
+            line_p_ (false),
+            char_p_ (false)
+      {
+      }
+
+
+      Void
+      kind (Kind const& kind)
+      {
+        kind_ = &kind;
+      }
+
+      friend class Bits::Mediator;
+
+      friend Record&
+      operator<< (Bits::Mediator const&, Kind const&);
+
+    public:
+      class Undefined {};
+
+      Kind const&
+      kind () const
+      {
+        return *kind_;
+      }
+
+      Char const*
+      file () const
+      {
+        if (file_p_) return file_.c_str ();
+
+        throw Undefined ();
+      }
+
+      UnsignedLong
+      line () const
+      {
+        if (line_p_) return line_;
+
+        throw Undefined ();
+      }
+
+      Boolean
+      char_p () const
+      {
+        return char_p_;
+      }
+
+      UnsignedLong
+      char_ () const
+      {
+        if (char_p_) return char__;
+
+        throw Undefined ();
+      }
+
+      String
+      text () const
+      {
+        return o_.str ();
+      }
+
+    public:
+      Record&
+      operator<< (Char const* s)
+      {
+        if (!char_p_ && !line_p_ && !file_p_)
+        {
+          file_ = s;
+          file_p_ = true;
+        }
+        else
+          o_ << s;
+
+        return *this;
+      }
+
+      //@@ Make it Int.
+      //
+      Record&
+      operator<< (UnsignedLong l)
+      {
+        if (file_p_ && !char_p_)
+        {
+          if (line_p_)
+          {
+            char__ = l;
+            char_p_ = true;
+          }
+          else
+          {
+            line_ = l;
+            line_p_ = true;
+          }
+        }
+        else
+          o_ << l;
+
+        return *this;
+      }
+
+      template <typename X>
+      Record&
+      operator<< (X const& x)
+      {
+        o_ << x;
+        return *this;
+      }
+
+    private:
+      Kind const* kind_;
+
+      Boolean file_p_;
+      String file_;
+
+      Boolean line_p_;
+      UnsignedLong line_;
+
+      Boolean char_p_;
+      UnsignedLong char__;
+
+      std::ostringstream o_;
+    };
+
+
+    //
+    //
+    //
+    class Log: public NonCopyable
+    {
+    public:
+      virtual
+      ~Log ()
+      {
+      }
+
+    public:
+      virtual Log&
+      operator<< (Record const& r);
+
+    public:
+      static Log&
+      instance ();
+    };
+
+
+    //
+    //
+    //
+    class Stream;
+
+    namespace Bits
+    {
+      class Mediator
+      {
+      public:
+        Mediator (Stream& s)
+            : s_ (s)
+        {
+        }
+
+        ~Mediator ();
+
+        Stream& s_;
+        mutable Record r_;
+      };
+    }
+
+    class Stream: public NonCopyable
+    {
+    public:
+      Stream (Log& l = Log::instance ())
+          : log_ (l)
+      {
+      }
+
+    public:
+      Stream&
+      operator<< (Record const& r)
+      {
+        log_ << r;
+        return *this;
+      }
+
+      friend Record&
+      operator<< (Bits::Mediator const& m, Kind const& k)
+      {
+        Record& r (m.r_);
+
+        r.kind (k);
+
+        return r;
+      }
+
+    private:
+      Log& log_;
+    };
+
+  }
+}
+
+#include <frontend-elements/diagnostic.ixx>
+#include <frontend-elements/diagnostic.txx>
+
+#endif  // FRONTEND_ELEMENTS_DIAGNOSTIC_HXX
diff --git a/libfrontend-elements/frontend-elements/diagnostic.ixx b/libfrontend-elements/frontend-elements/diagnostic.ixx
new file mode 100644
index 0000000..d32325d
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/diagnostic.ixx
@@ -0,0 +1,21 @@
+// file      : frontend-elements/diagnostic.ixx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+namespace FrontendElements
+{
+  namespace Diagnostic
+  {
+    namespace Bits
+    {
+      inline
+      Mediator::
+      ~Mediator ()
+      {
+        s_ << r_;
+      }
+    }
+  }
+}
+
diff --git a/libfrontend-elements/frontend-elements/diagnostic.txx b/libfrontend-elements/frontend-elements/diagnostic.txx
new file mode 100644
index 0000000..b8391f4
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/diagnostic.txx
@@ -0,0 +1,9 @@
+// file      : frontend-elements/diagnostic.txx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+namespace FrontendElements
+{
+}
+
diff --git a/libfrontend-elements/frontend-elements/makefile b/libfrontend-elements/frontend-elements/makefile
new file mode 100644
index 0000000..8ca30b0
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/makefile
@@ -0,0 +1,63 @@
+# file      : frontend-elements/makefile
+# author    : Boris Kolpackov <boris@kolpackov.net>
+# copyright : Copyright (c) 2005-2010 Boris Kolpackov
+# license   : GNU GPL v2; see accompanying LICENSE file
+
+include $(dir $(lastword $(MAKEFILE_LIST)))../build/bootstrap.make
+
+cxx_tun   := context.cxx       \
+             diagnostic.cxx    \
+             token-stream.cxx  \
+             traversal.cxx
+
+cxx_obj   := $(addprefix $(out_base)/,$(cxx_tun:.cxx=.o))
+cxx_od    := $(cxx_obj:.o=.o.d)
+
+frontend_elements.l             := $(out_base)/frontend-elements.l
+frontend_elements.l.cpp-options := $(out_base)/frontend-elements.l.cpp-options
+
+clean     := $(out_base)/.clean
+
+
+# Secure default target.
+#
+$(frontend_elements.l):
+
+
+# Import libcult.
+#
+$(call import,\
+  $(scf_root)/import/libcult/stub.make,\
+  l: cult.l,cpp-options: cult.l.cpp-options)
+
+# Build.
+#
+$(frontend_elements.l): $(cxx_obj) $(cult.l)
+
+$(cxx_obj) $(cxx_od): $(frontend_elements.l.cpp-options)
+
+$(frontend_elements.l.cpp-options): value := -I$(src_root)
+$(frontend_elements.l.cpp-options): $(cult.l.cpp-options)
+
+$(call include-dep,$(cxx_od))
+
+
+# Convenience alias for default target.
+#
+$(out_base)/: $(frontend_elements.l)
+
+
+# Clean.
+#
+$(clean): $(frontend_elements.l).o.clean     \
+  $(frontend_elements.l.cpp-options).clean \
+  $(addsuffix .cxx.clean,$(cxx_obj))           \
+  $(addsuffix .cxx.clean,$(cxx_od))
+
+
+
+# How to.
+#
+$(call include,$(bld_root)/cxx/o-l.make)
+$(call include,$(bld_root)/cxx/cxx-o.make)
+$(call include,$(bld_root)/cxx/cxx-d.make)
diff --git a/libfrontend-elements/frontend-elements/token-stream.cxx b/libfrontend-elements/frontend-elements/token-stream.cxx
new file mode 100644
index 0000000..dab785a
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/token-stream.cxx
@@ -0,0 +1,10 @@
+// file      : frontend-elements/token-stream.cxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#include <frontend-elements/token-stream.hxx>
+
+namespace FrontendElements
+{
+}
diff --git a/libfrontend-elements/frontend-elements/token-stream.hxx b/libfrontend-elements/frontend-elements/token-stream.hxx
new file mode 100644
index 0000000..023842f
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/token-stream.hxx
@@ -0,0 +1,99 @@
+// file      : frontend-elements/token-stream.hxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#ifndef FRONTEND_ELEMENTS_TOKEN_STREAM_HXX
+#define FRONTEND_ELEMENTS_TOKEN_STREAM_HXX
+
+#include <frontend-elements/types.hxx>
+
+#include <string>   // std::char_traits
+#include <istream>
+
+namespace FrontendElements
+{
+  //
+  //
+  template <typename Token>
+  class TokenStream
+  {
+  public:
+    virtual
+    ~TokenStream ()
+    {
+    }
+
+  public:
+    virtual Token
+    next () = 0;
+  };
+
+
+  //
+  //
+  template <>
+  class TokenStream<Char>
+  {
+  public:
+    typedef
+    std::char_traits<FrontendElements::Char>
+    Traits;
+
+    typedef
+    Traits::int_type
+    AsInt;
+
+    typedef
+    Traits::char_type
+    AsChar;
+
+  public:
+    virtual
+    ~TokenStream ()
+    {
+    }
+
+  public:
+    virtual AsInt
+    next () = 0;
+
+    static AsChar
+    to_char (AsInt i)
+    {
+      return Traits::to_char_type (i);
+    }
+
+    static AsInt
+    eos ()
+    {
+      return Traits::eof ();
+    }
+  };
+
+  class InputStreamAdapter: public TokenStream<Char>
+  {
+  public:
+    virtual
+    ~InputStreamAdapter ()
+    {
+    }
+
+    InputStreamAdapter (std::istream& is)
+        : is_ (is)
+    {
+    }
+
+  public:
+    virtual AsInt
+    next ()
+    {
+      return is_.get ();
+    }
+
+  private:
+    std::istream& is_;
+  };
+}
+
+#endif  // FRONTEND_ELEMENTS_TOKEN_STREAM_HXX
diff --git a/libfrontend-elements/frontend-elements/traversal.cxx b/libfrontend-elements/frontend-elements/traversal.cxx
new file mode 100644
index 0000000..079a2a8
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/traversal.cxx
@@ -0,0 +1,10 @@
+// file      : frontend-elements/traversal.cxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#include <frontend-elements/traversal.hxx>
+
+namespace FrontendElements
+{
+}
diff --git a/libfrontend-elements/frontend-elements/traversal.hxx b/libfrontend-elements/frontend-elements/traversal.hxx
new file mode 100644
index 0000000..b320484
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/traversal.hxx
@@ -0,0 +1,293 @@
+// file      : frontend-elements/traversal.hxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#ifndef FRONTEND_ELEMENTS_TRAVERSAL_HXX
+#define FRONTEND_ELEMENTS_TRAVERSAL_HXX
+
+#include <frontend-elements/types.hxx>
+
+#include <cult/containers/map.hxx>
+#include <cult/containers/set.hxx>
+#include <cult/containers/vector.hxx>
+
+#include <cult/rtti/type-info.hxx>
+
+#include <cult/trace/stream.hxx>
+
+//@@ Move to trace next time you are about to uncomment this.
+//
+// #include <iostream>
+// using std::wcerr;
+// using std::endl;
+
+
+namespace FrontendElements
+{
+  namespace Traversal
+  {
+    //
+    //
+    template<typename X>
+    class TraverserBase
+    {
+    protected:
+      virtual
+      ~TraverserBase ();
+
+      virtual Void
+      trampoline (X&) = 0;
+
+      virtual Void
+      trampoline (X const&) = 0;
+
+      template <typename>
+      friend class DispatcherBase;
+    };
+
+
+    //
+    //
+    template <typename X>
+    class DispatcherBase
+    {
+      typedef
+      Cult::RTTI::TypeId
+      TypeId;
+
+      typedef
+      Cult::RTTI::TypeInfo
+      TypeInfo;
+
+    public:
+      virtual
+      ~DispatcherBase ();
+
+      virtual Void
+      dispatch (X&);
+
+      virtual Void
+      dispatch (X const&);
+
+      Void
+      map (TypeId id, TraverserBase<X>& t)
+      {
+        //wcerr << "map for " << id.name () << " to " << &t
+	//      << " in " << &traversal_map_ << endl;
+
+        Traversers& traversers (traversal_map_[id]);
+        traversers.push_back (&t);
+      }
+
+    public:
+      typedef
+      Cult::Containers::Vector<TraverserBase<X>*>
+      Traversers;
+
+      typedef
+      Cult::Containers::Map<TypeId, Traversers>
+      TraversalMap;
+
+      typedef
+      typename TraversalMap::ConstIterator
+      Iterator;
+
+      Iterator
+      begin () const
+      {
+        return traversal_map_.begin ();
+      }
+
+      Iterator
+      end () const
+      {
+        return traversal_map_.end ();
+      }
+
+    protected:
+      static Cult::Trace::Stream tout;
+
+    private:
+      template<typename Y>
+      Void
+      dispatch_ (Y&);
+
+    private:
+
+      struct TypeInfoComparator
+      {
+        Boolean
+        operator () (TypeInfo const& a, TypeInfo const& b) const
+        {
+          return a.type_id () < b.type_id ();
+        }
+      };
+
+      typedef
+      Cult::Containers::Map<TypeInfo, UnsignedLong, TypeInfoComparator>
+      LevelMap;
+
+      typedef
+      Cult::Containers::Set<TypeInfo, TypeInfoComparator>
+      TypeInfoSet;
+
+      static UnsignedLong
+      compute_levels (TypeInfo const& ti, UnsignedLong cur, LevelMap& map);
+
+      static Void
+      flatten_tree (TypeInfo const& ti, TypeInfoSet& set);
+
+    private:
+      TraversalMap traversal_map_;
+    };
+
+
+    //
+    //
+    template <typename X>
+    class Dispatcher: public virtual DispatcherBase<X>
+    {
+    public:
+      Dispatcher ()
+          : merge_ (true)
+      {
+      }
+
+      Void
+      traverser (DispatcherBase<X>& d)
+      {
+        for (typename DispatcherBase<X>::Iterator
+               i (d.begin ()), e (d.end ()); i != e; ++i)
+        {
+          for (typename DispatcherBase<X>::Traversers::ConstIterator
+                 t (i->second.begin ()), e (i->second.end ()); t != e; ++t)
+          {
+            dispatcher_.map (i->first, **t);
+          }
+        }
+      }
+
+    public:
+      virtual Void
+      dispatch (X& x)
+      {
+        merge ();
+        dispatcher_.dispatch (x);
+      }
+
+      virtual Void
+      dispatch (X const& x)
+      {
+        merge ();
+        dispatcher_.dispatch (x);
+      }
+
+      using DispatcherBase<X>::begin;
+      using DispatcherBase<X>::end;
+
+    private:
+      Void
+      merge ()
+      {
+        if (merge_)
+        {
+          for (typename DispatcherBase<X>::Iterator
+                 i (begin ()), e (end ()); i != e; ++i)
+          {
+            for (typename DispatcherBase<X>::Traversers::ConstIterator
+                   t (i->second.begin ()), e (i->second.end ()); t != e; ++t)
+            {
+              dispatcher_.map (i->first, **t);
+            }
+          }
+
+          merge_ = false;
+        }
+      }
+
+    protected:
+      template <typename I, typename Y>
+      Void
+      iterate_and_dispatch (I begin, I end, DispatcherBase<Y>& d)
+      {
+        for (; begin != end; ++begin)
+        {
+          d.dispatch (*begin);
+        }
+      }
+
+      template <typename T, typename A, typename I, typename Y>
+      Void
+      iterate_and_dispatch (I begin,
+                            I end,
+                            DispatcherBase<Y>& d,
+                            T& t,
+                            Void (T::*next)(A&),
+                            A& a)
+      {
+        for (; begin != end;)
+        {
+          d.dispatch (*begin);
+
+          if (++begin != end && next != 0)
+            (t.*next) (a);
+        }
+      }
+
+    private:
+      Boolean merge_;
+      DispatcherBase<X> dispatcher_;
+    };
+
+
+    //
+    //
+    template <typename T, typename X>
+    struct Traverser : TraverserBase<X>, virtual Dispatcher<X>
+    {
+      typedef T Type;
+
+      Traverser ()
+      {
+        map (typeid (Type), *this);
+      }
+
+      virtual Void
+      traverse (Type&)
+      {
+        abort ();
+      }
+
+      virtual Void
+      traverse (Type const&)
+      {
+        abort ();
+      }
+
+    protected:
+      virtual Void
+      trampoline (X& x)
+      {
+        //wcerr << "trampoline for " << &i << " to type "
+        //      << typeid (type).name () << endl;
+
+        traverse (dynamic_cast<Type&> (x));
+      }
+
+      virtual Void
+      trampoline (X const& x)
+      {
+        //wcerr << "trampoline for " << &i << " to type "
+        //      << typeid (Type).name () << endl;
+
+        traverse (dynamic_cast<Type const&> (x));
+      }
+    };
+  }
+}
+
+#include <frontend-elements/traversal.ixx>
+#include <frontend-elements/traversal.txx>
+
+#endif  // FRONTEND_ELEMENTS_TRAVERSAL_HXX
diff --git a/libfrontend-elements/frontend-elements/traversal.ixx b/libfrontend-elements/frontend-elements/traversal.ixx
new file mode 100644
index 0000000..47c7314
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/traversal.ixx
@@ -0,0 +1,8 @@
+// file      : frontend-elements/traversal.ixx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+namespace FrontendElements
+{
+}
diff --git a/libfrontend-elements/frontend-elements/traversal.txx b/libfrontend-elements/frontend-elements/traversal.txx
new file mode 100644
index 0000000..6e6bfa3
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/traversal.txx
@@ -0,0 +1,135 @@
+// file      : frontend-elements/traversal.txx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+namespace FrontendElements
+{
+  namespace Traversal
+  {
+    // TraverserBase
+    //
+
+    template<typename X>
+    TraverserBase<X>::
+    ~TraverserBase ()
+    {
+    }
+
+    // DispatcherBase
+    //
+
+    template <typename X>
+    DispatcherBase<X>::
+    ~DispatcherBase ()
+    {
+    }
+
+    template <typename X>
+    Void DispatcherBase<X>::
+    dispatch (X& x)
+    {
+      dispatch_ (x);
+    }
+
+    template <typename X>
+    void DispatcherBase<X>::
+    dispatch (X const& x)
+    {
+      dispatch_ (x);
+    }
+
+    template <typename X>
+    template <typename Y>
+    void DispatcherBase<X>::
+    dispatch_ (Y& y)
+    {
+      LevelMap levels;
+
+      TypeInfo const& ti (Cult::RTTI::lookup (typeid (y)));
+
+      UnsignedLong max (compute_levels (ti, 0, levels));
+
+      tout << "starting dispatch process for " << ti.type_id ().name ()
+           << " with " << max << " levels";
+
+      for (UnsignedLong l (0); l < max + 1; ++l)
+      {
+        TypeInfoSet dispatched;
+
+        for (typename LevelMap::ConstIterator
+               i (levels.begin ()), e (levels.end ()); i != e; ++i)
+        {
+          if (i->second == l)
+          {
+            typename TraversalMap::ConstIterator v (
+              traversal_map_.find (i->first.type_id ()));
+
+            if (v != traversal_map_.end ())
+            {
+              tout << "dispatching traversers for " << ti.type_id ().name ()
+                   << " as " << i->first.type_id ().name ();
+
+              Traversers const& traversers (v->second);
+
+              for (typename Traversers::ConstIterator
+                     ti (traversers.begin ()), te (traversers.end ()); ti != te; ++ti)
+              {
+                (*ti)->trampoline (y);
+              }
+
+              flatten_tree (i->first, dispatched);
+            }
+          }
+        }
+
+        // Remove traversed types from the level map.
+        //
+        for (typename TypeInfoSet::ConstIterator i (dispatched.begin ());
+             i != dispatched.end (); ++i)
+        {
+          levels.erase (*i);
+        }
+      }
+    }
+
+
+    template <typename X>
+    UnsignedLong DispatcherBase<X>::
+    compute_levels (TypeInfo const& ti, UnsignedLong cur, LevelMap& map)
+    {
+      UnsignedLong ret (cur);
+
+      if (map.find (ti) == map.end () || map[ti] < cur) map[ti] = cur;
+
+      for (TypeInfo::BaseIterator i (ti.begin_base ());
+           i != ti.end_base (); ++i)
+      {
+        UnsignedLong tmp (compute_levels (i->type_info (), cur + 1, map));
+
+        if (tmp > ret)
+          ret = tmp;
+      }
+
+      return ret;
+    }
+
+    template <typename X>
+    Void DispatcherBase<X>::
+    flatten_tree (TypeInfo const& ti, TypeInfoSet& set)
+    {
+      set.insert (ti);
+
+      for (TypeInfo::BaseIterator i = ti.begin_base ();
+           i != ti.end_base (); ++i)
+      {
+        flatten_tree (i->type_info (), set);
+      }
+    }
+
+    template <typename X>
+    Cult::Trace::Stream DispatcherBase<X>::
+    tout ("frontend-elements::traversal", 5);
+  }
+}
+
diff --git a/libfrontend-elements/frontend-elements/types.hxx b/libfrontend-elements/frontend-elements/types.hxx
new file mode 100644
index 0000000..f9a6905
--- /dev/null
+++ b/libfrontend-elements/frontend-elements/types.hxx
@@ -0,0 +1,16 @@
+// file      : frontend-elements/types.hxx
+// author    : Boris Kolpackov <boris@kolpackov.net>
+// copyright : Copyright (c) 2005-2010 Boris Kolpackov
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#ifndef FRONTEND_ELEMENTS_TYPES_HXX
+#define FRONTEND_ELEMENTS_TYPES_HXX
+
+#include <cult/types.hxx>
+
+namespace FrontendElements
+{
+  using namespace Cult::Types;
+}
+
+#endif  // FRONTEND_ELEMENTS_TYPES_HXX