diff options
Diffstat (limited to 'libfrontend-elements/frontend-elements/traversal.hxx')
| -rw-r--r-- | libfrontend-elements/frontend-elements/traversal.hxx | 293 |
1 files changed, 293 insertions, 0 deletions
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 |