|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74000 - in sandbox/metagraph: . boost/fusion boost/intrusive boost/metagraph/angly boost/metagraph/angly/detail boost/metagraph/fusion_graph boost/metagraph/mpl_graph boost/metagraph/mpl_graph/detail libs/intrusive libs/metagraph/example
From: gordon_at_[hidden]
Date: 2011-08-21 22:12:57
Author: gordon.woodhull
Date: 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
New Revision: 74000
URL: http://svn.boost.org/trac/boost/changeset/74000
Log:
angly parser; remove unneeded deps
Added:
sandbox/metagraph/boost/metagraph/angly/
sandbox/metagraph/boost/metagraph/angly/detail/
sandbox/metagraph/boost/metagraph/angly/detail/apply_seq.hpp (contents, props changed)
sandbox/metagraph/boost/metagraph/angly/dfa.hpp (contents, props changed)
sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp (contents, props changed)
sandbox/metagraph/libs/metagraph/example/angly_graph_dfa.cpp (contents, props changed)
sandbox/metagraph/libs/metagraph/example/angly_graph_parser.cpp (contents, props changed)
Removed:
sandbox/metagraph/boost/fusion/
sandbox/metagraph/boost/intrusive/
sandbox/metagraph/libs/intrusive/
Text files modified:
sandbox/metagraph/boost-build.jam | 87 ++++++++++++++++++++++++++++++++-------
sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp | 15 ++++--
sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp | 2
sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp | 33 ---------------
4 files changed, 82 insertions(+), 55 deletions(-)
Modified: sandbox/metagraph/boost-build.jam
==============================================================================
--- sandbox/metagraph/boost-build.jam (original)
+++ sandbox/metagraph/boost-build.jam 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -1,17 +1,70 @@
-# Copyright (C) 2002-2003 David Abrahams.
-# Copyright (C) 2002-2003 Vladimir Prus.
-# Copyright (C) 2003,2007 Rene Rivera.
-# Use, modification and distribution are subject to the
-# Boost Software License, Version 1.0. (See accompanying file
-# LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-
-# This is the initial file loaded by Boost Jam when run from any Boost library
-# folder. It allows us to choose which Boost Build installation to use for
-# building Boost libraries. Unless explicitly selected using a command-line
-# option, the version included with the Boost library distribution is used (as
-# opposed to any other Boost Build version installed on the user's sytem).
-
-BOOST_ROOT = $(.boost-build-file:D) ;
-BOOST_BUILD = [ MATCH --boost-build=(.*) : $(ARGV) ] ;
-BOOST_BUILD ?= tools/build/v2 ;
-boost-build $(BOOST_BUILD) ;
+# Copyright Rene Rivera 2007.
+#
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+
+# For instructions see Jamfile.v2, or "bjam --help".
+
+local rule if-has-file ( file + : dir * )
+{
+ local result ;
+ if $(dir)
+ {
+ result = [ GLOB $(dir) : $(file) ] ;
+ }
+ return $(result[1]:P) ;
+}
+
+#~ Attempts to find the Boost source tree...
+
+local boost-src = [ if-has-file LICENSE_1_0.txt :
+ [ MATCH --boost=(.*) : $(ARGV) ]
+ $(BOOST)
+ $(.boost-build-file:D)/../boost
+ $(.boost-build-file:D)/../Trunk
+ ] ;
+
+# error handling:
+if ! $(boost-src)
+{
+ ECHO Unable to find the Boost source tree in the locations searched. ;
+ ECHO Try setting the environment variable BOOST to point to your ;
+ ECHO Boost tree, or else invoke bjam with the --boost=path option. ;
+ ECHO The Boost include path will not be automatically set. ;
+ ECHO The paths searched were [ MATCH --boost=(.*) : $(ARGV) ] $(BOOST) $(.boost-build-file:D)/../boost $(.boost-build-file:D)/../Trunk ;
+ ECHO But the file LICENSE_1_0.txt was not found in any of them ;
+}
+
+#~ Attempts to find the Boost.Build files...
+
+local boost-build-src = [ if-has-file bootstrap.jam :
+ [ MATCH --boost-build=(.*) : $(ARGV) ]
+ $(BOOST_BUILD_PATH)
+ $(BOOST_BUILD)
+ $(boost-src)/tools/build/v2
+ ] ;
+
+# error handling:
+if ! $(boost-build-src)
+{
+ ECHO Unable to find the Boost.Build source tree in the locations searched. ;
+ ECHO Try setting the environment variable BOOST_BUILD to point to your ;
+ ECHO Boost.Build tree, or else invoke bjam with the --boost-build=path option. ;
+ ECHO The paths searched were [ MATCH --boost-build=(.*) : $(ARGV) ] $(BOOST_BUILD_PATH) $(BOOST_BUILD) $(boost-src)/tools/build/v2 ;
+ ECHO But bootstrap.jam was not found in any of these ;
+ ECHO More failures will very likely follow... ;
+}
+
+#~ Set some common vars to refer to the Boost sources...
+
+BOOST ?= $(boost-src) ;
+BOOST_ROOT ?= $(boost-src) ;
+
+#~ And load up Boost.Build...
+
+boost-build $(boost-build-src) ;
+
+
+
+
Added: sandbox/metagraph/boost/metagraph/angly/detail/apply_seq.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/angly/detail/apply_seq.hpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -0,0 +1,36 @@
+#ifndef BOOST_METAGRAPH_EXAMPLE_APPLY_SEQ_HPP
+#define BOOST_METAGRAPH_EXAMPLE_APPLY_SEQ_HPP
+
+#include <boost/mpl/empty.hpp>
+#include <boost/mpl/pop_back.hpp>
+#include <boost/mpl/back.hpp>
+#include <boost/mpl/vector.hpp>
+
+// from https://github.com/scientific-coder/Computer-Languages/blob/master/interpreting/apply.hxx
+
+namespace boost {
+namespace metagraph {
+namespace angly {
+namespace detail {
+template<template<typename...> class T, bool empty, typename C, typename... Types> struct apply_seq_helper {
+ typedef typename boost::mpl::pop_back<C>::type rest;
+ typedef typename apply_seq_helper<T, boost::mpl::empty<rest>::value, rest, typename boost::mpl::back<C>::type, Types...>::type type;
+};
+template<template<typename...> class T,typename C, typename... Types> struct apply_seq_helper<T, true, C, Types...> {
+ typedef T<Types...> type;
+};
+
+template<template<typename...> class T,typename C> struct apply_seq : detail::apply_seq_helper<T, boost::mpl::empty<C>::value, C> {};
+
+// for lambdas
+template<template<typename...> class T> struct apply_seq_q {
+ template<typename C>
+ struct apply : apply_seq<T, C>
+ {};
+};
+}
+}
+}
+}
+
+#endif // BOOST_METAGRAPH_EXAMPLE_APPLY_SEQ_HPP
Added: sandbox/metagraph/boost/metagraph/angly/dfa.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/angly/dfa.hpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -0,0 +1,359 @@
+// Copyright 2011 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_METAGRAPH_ANGLY_DFA_HPP
+#define BOOST_METAGRAPH_ANGLY_DFA_HPP
+
+#include <boost/mpl/back.hpp>
+#include <boost/mpl/iter_fold.hpp>
+#include <boost/mpl/push_front.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/find_if.hpp>
+#include <boost/mpl/same_as.hpp>
+#include <boost/mpl/deref.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/pop_front.hpp>
+#include <boost/mpl/front.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/begin.hpp>
+#include <boost/mpl/end.hpp>
+#include <boost/mpl/empty.hpp>
+#include <boost/mpl/protect.hpp>
+#include <boost/mpl/print.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/msm/mpl_graph/mpl_graph.hpp>
+
+namespace boost {
+ namespace metagraph {
+ namespace angly {
+
+ namespace detail {
+
+ // extract a variadic template from its instantiation, stripping its args and returning T<>
+ template<typename T> struct de_arg {
+ // default = didn't work (e.g non-templates, templates with non-type params)
+ typedef void type;
+ };
+
+ template<template<typename...> class Template, typename ...Args>
+ struct de_arg<Template<Args...> > {
+ typedef Template<> type;
+ };
+
+ // convert variadic template arguments to mpl sequence
+ template<typename ...Args> struct variadic_to_mpl;
+
+ template<typename Head, typename ...Args>
+ struct variadic_to_mpl<Head, Args...> :
+ mpl::push_front<typename variadic_to_mpl<Args...>::type, Head> {};
+
+ template<>
+ struct variadic_to_mpl<> :
+ mpl::vector<> {};
+
+ // return the args of a template instantiation as an mpl sequence
+ template<typename T> struct arg_seq;
+
+ template<template<typename...> class Template, typename ...Args>
+ struct arg_seq<Template<Args...> > : variadic_to_mpl<Args...> {};
+
+ }
+
+ /*
+ The DFA operates in stack frames which are produced when recursing
+ into angle brackets.
+
+ Each frame produces some metadata "pre" and "post" semantic actions
+
+ Each semantic action metafunction takes two parameters:
+ * the parent frame metadata
+ * the child frame metadata
+
+ The pre-action only gets invoked when there is a recurse rule. It
+ takes the parent frame's metadata and the start_data of the recurse rule state.
+
+ The post-action gets invoked at the end of every transition. Its
+ first parameter is the current frame data. If there was a recursion,
+ its second parameter is the resulting frame data from the child,
+ otherwise it is the raw value of the item that matched.
+
+ Each semantic action returns the current frame metadata, i.e. pre-
+ returns the resulting child frame data and post- returns the resulting
+ parent frame data.
+
+ It could conceivably input/output a whole stack of current datas
+ (for something akin to inherited attributes)
+ but let's not get too crazy.
+ */
+
+ // derive from these to produce your states & transitions
+ // or provide states & transitions with the same access metafunctions
+ template<typename IsFinish = mpl::false_, typename StartData = void>
+ struct dfa_state {
+ typedef IsFinish is_finish;
+ typedef StartData start_data;
+ };
+
+ template<typename MatchFn, typename RecurseRule = void, typename PostAction = mpl::_1, typename PreAction = mpl::protect<mpl::_2> >
+ struct dfa_transition {
+ typedef typename mpl::lambda<MatchFn>::type match_fn;
+ typedef typename mpl::lambda<PreAction>::type pre_action;
+ typedef typename mpl::lambda<PostAction>::type post_action;
+ typedef RecurseRule recurse_rule;
+ };
+
+ template<typename T> struct get_transition_match_fn {
+ typedef typename T::match_fn type;
+ };
+
+ template<typename T> struct get_transition_pre_action {
+ typedef typename T::pre_action type;
+ };
+
+ template<typename T> struct get_transition_post_action {
+ typedef typename T::post_action type;
+ };
+
+ template<typename T> struct get_transition_recurse_rule {
+ typedef typename T::recurse_rule type;
+ };
+
+ // a match_fn for matching the template
+ template<typename Token> struct match_token
+ {
+ template<typename Item> struct apply;
+ template<typename Item> struct apply<mpl::protect<Item> >
+ : boost::is_same<Token, typename detail::de_arg<Item>::type>
+ {};
+ };
+
+ template<typename Trans, typename Item>
+ struct check_transition_match :
+ mpl::apply<typename get_transition_match_fn<Trans>::type, Item>
+ {};
+
+ template<typename T> struct is_finish_state : T::is_finish
+ {};
+
+ template<typename T> struct get_state_start_data {
+ typedef typename T::start_data type;
+ };
+
+ namespace detail {
+ template<typename DFA, typename State, typename Item, typename PropFn>
+ struct match_item {
+ typedef typename msm::mpl_graph::out_edges<State, DFA>::type edges;
+ typedef typename mpl::find_if<edges,
+ check_transition_match<mpl::apply_wrap1<PropFn,mpl::_1>, mpl::protect<Item> >
+ >::type miter;
+ static_assert(!boost::is_same<miter, typename mpl::end<edges>::type>::value, "no match for input token");
+ typedef typename mpl::deref<miter>::type type;
+ };
+ /* state stack: since we need to avoid recursion, we need to store
+ the entire state of the parser in an explicit stack, where each frame corresponds
+ to a level of angle bracket in the input.
+ each frame contains:
+ - the current state of the DFA
+ - the current and
+ - end iterator of the current input sequence
+ - the semantic action which must be executed upon returning from a frame
+ - the output data
+
+ */
+
+ // the actual format is what's best for printing; this order is convenient for use (?)
+ template<typename Data, typename State, typename CurrIter, typename EndIter, typename Action = mpl::_1>
+ struct create_frame :
+ mpl::vector<State, CurrIter, EndIter, typename mpl::lambda<Action>::type, Data>
+ {};
+
+ template<class T>
+ struct print
+ {
+ typedef T type;
+ unsigned : 80;
+ };
+
+ template<typename Frame>
+ struct get_frame_state : mpl::at_c<Frame,0> {};
+ template<typename Frame>
+ struct get_frame_curr_iter : mpl::at_c<Frame,1> {};
+ template<typename Frame>
+ struct get_frame_end_iter : mpl::at_c<Frame,2> {};
+ template<typename Frame>
+ struct get_frame_action : mpl::at_c<Frame,3> {};
+ template<typename Frame>
+ struct get_frame_data : mpl::at_c<Frame,4> {};
+
+ template<typename Frame, typename Data>
+ struct set_data :
+ create_frame<Data,
+ typename get_frame_state<Frame>::type,
+ typename get_frame_curr_iter<Frame>::type,
+ typename get_frame_end_iter<Frame>::type,
+ typename get_frame_action<Frame>::type>
+ {};
+
+
+ template<typename Stack>
+ struct stack_states :
+ mpl::transform<Stack, get_frame_state<mpl::_1> >
+ {};
+
+ // all these metafunctions return the new state stack
+ template<typename Stack, typename PropFn>
+ struct finish_frame {
+ typedef typename mpl::front<Stack>::type frame;
+
+ static_assert(is_finish_state<typename PropFn::template apply<typename get_frame_state<frame>::type>::type>::value,
+ "must be in finishing state when input ends");
+
+ typedef typename get_frame_data<frame>::type result;
+ typedef typename mpl::pop_front<Stack>::type popt;
+ typedef typename mpl::front<popt>::type frame2;
+ typedef typename mpl::pop_front<popt>::type popt2;
+ typedef typename
+ mpl::push_front<popt2,
+ typename
+ set_data<frame2,
+ typename
+ mpl::apply<typename get_frame_action<frame2>::type,
+ typename get_frame_data<frame2>::type,
+ result>::type>::type>::type type;
+ };
+
+ template<typename DFA, typename Stack, typename Match, typename Item, typename PropFn>
+ struct dfa_follow_no_recurse {
+ typedef typename mpl::front<Stack>::type frame;
+ typedef typename mpl::pop_front<Stack>::type popt;
+ typedef typename
+ mpl::push_front<popt,
+ typename
+ create_frame<typename
+ mpl::apply<typename get_transition_post_action<typename PropFn::template apply<Match>::type>::type,
+ typename get_frame_data<frame>::type,
+ Item>::type,
+ typename msm::mpl_graph::target<Match, DFA>::type,
+ typename mpl::next<typename get_frame_curr_iter<frame>::type>::type,
+ typename get_frame_end_iter<frame>::type>::type>::type type;
+ };
+
+ template<typename DFA, typename Stack, typename RecurseRule, typename Match, typename Item, typename PropFn>
+ struct dfa_follow_recurse {
+ typedef typename mpl::front<Stack>::type frame;
+ typedef typename mpl::pop_front<Stack>::type popt;
+ typedef typename
+ mpl::push_front<popt,
+ typename
+ create_frame<typename get_frame_data<frame>::type,
+ typename msm::mpl_graph::target<Match, DFA>::type,
+ typename mpl::next<typename get_frame_curr_iter<frame>::type>::type,
+ typename get_frame_end_iter<frame>::type,
+ typename get_transition_post_action<typename PropFn::template apply<Match>::type>::type>::type>::type parent;
+
+ typedef typename detail::arg_seq<Item>::type inner_seq;
+ typedef typename
+ mpl::push_front<parent,
+ typename
+ create_frame<typename mpl::apply<typename get_transition_pre_action<typename PropFn::template apply<Match>::type>::type,
+ typename get_frame_data<frame>::type,
+ typename get_state_start_data<typename PropFn::template apply<RecurseRule>::type>::type>::type,
+ RecurseRule,
+ typename mpl::begin<inner_seq>::type,
+ typename mpl::end<inner_seq>::type>::type>::type type;
+ };
+
+
+ template<typename DFA, typename Stack, typename PropFn>
+ struct dfa_follow {
+ typedef typename mpl::front<Stack>::type frame;
+
+ typedef typename get_frame_curr_iter<frame>::type curr_iter;
+ typedef typename mpl::deref<curr_iter>::type item;
+ typedef typename match_item<DFA, typename get_frame_state<frame>::type, item, PropFn>::type match;
+
+ typedef typename get_transition_recurse_rule<typename PropFn::template apply<match>::type>::type recurse_rule;
+ typedef typename mpl::eval_if<
+ typename boost::is_same<void, recurse_rule>::type,
+ dfa_follow_no_recurse<DFA, Stack, match, item, PropFn>,
+ dfa_follow_recurse<DFA, Stack, recurse_rule, match, item, PropFn> >::type type;
+ };
+
+
+ template<typename DFA, typename Stack, typename PropFn>
+ struct dfa_step {
+ typedef typename mpl::front<Stack>::type frame;
+ typedef typename get_frame_curr_iter<frame>::type curr_iter;
+ typedef typename get_frame_end_iter<frame>::type end_iter;
+
+ typedef typename
+ mpl::eval_if<typename boost::is_same<curr_iter, end_iter>::type,
+ finish_frame<Stack, PropFn>,
+ dfa_follow<DFA, Stack, PropFn>
+ >::type type;
+ };
+
+ struct utterly_done_state {};
+ // create a stack with a sentinel end-frame
+ template<typename Data, typename StartState, typename CurrIter, typename EndIter>
+ struct create_stack {
+ typedef mpl::vector<typename
+ create_frame<Data,
+ StartState,
+ CurrIter,
+ EndIter>::type,
+ typename //end-frame
+ create_frame<void,utterly_done_state, void, void, mpl::_2>::type> type;
+ };
+
+ template<typename Stack>
+ struct stack_is_done :
+ boost::is_same<typename get_frame_state<typename mpl::front<Stack>::type>::type, utterly_done_state>
+ {};
+
+ struct dfa_end {};
+
+ template<typename DFA, typename Stack, typename PropFn>
+ struct dfa_iter {
+ //print<typename stack_states<Stack>::type> x;
+ static_assert(!stack_is_done<Stack>::value, "iterate past end of DFA sequence");
+ typedef typename dfa_step<DFA, Stack, PropFn>::type eval;
+
+ typedef typename
+ mpl::if_<typename stack_is_done<eval>::type,
+ dfa_end,
+ dfa_iter<DFA, eval, PropFn> >::type next;
+ typedef typename get_frame_data<typename mpl::front<eval>::type>::type type;
+ };
+
+ } // namespace detail
+
+ // a DFA sequence is a pair of iterators, where an iterator represents the running
+ // state of the DFA and a position in the input. currently only the data manipulated
+ // by the semantic actions is accessible (by dereferencing the iterator); if access
+ // to the state stack is desired, we'll have to talk about the best interface - it's
+ // currently (undocumented ;) in dfa_iter<>::state
+ template<typename DFA, typename StartState, typename Input, typename PropFn>
+ struct dfa_sequence {
+ typedef typename detail::de_arg<Input>::type token;
+ typedef typename detail::arg_seq<Input>::type inner_seq;
+ typedef typename detail::create_stack<typename get_state_start_data<typename PropFn::template apply<StartState>::type>::type, StartState, typename mpl::begin<inner_seq>::type, typename mpl::end<inner_seq>::type>::type stack;
+ typedef detail::dfa_iter<DFA, stack, PropFn> begin;
+ typedef detail::dfa_end end;
+ };
+
+ template<typename DFA, typename StartState, typename Input, typename PropFn = mpl::_1>
+ struct run_dfa :
+ mpl::fold<dfa_sequence<DFA, StartState, Input, typename mpl::lambda<PropFn>::type>,
+ void,
+ mpl::_2 > // not really a fold, just iterate until done and return final data
+ {};
+
+ }
+ }
+} // namespaces
+
+#endif //BOOST_METAGRAPH_ANGLY_DFA_HPP
Added: sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/angly/dfa_lang.hpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -0,0 +1,173 @@
+// Copyright 2011 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/metagraph/angly/dfa.hpp>
+#include <boost/metagraph/angly/detail/apply_seq.hpp>
+
+// pull a DFA language up by its bootstraps
+// by directly building a DFA to parse the language
+
+
+namespace boost {
+namespace metagraph {
+namespace angly {
+
+ template<typename ...>
+ struct dfa {};
+ template<typename ...>
+ struct state {};
+ template<typename ...>
+ struct transition {};
+
+ // parser for descriptions of parsers
+ // dfa<state<name, [is_finish, [data,]] [transition<name, target, [match_fn, [recurse_rule, [post_action, [pre_action]]]]>],
+ // transition<...> ] >,
+ // state<...> >
+ // it's pretty unwieldy to define a parser this way!!
+ // so this parser makes defining new parsers easier
+ struct dfa_states : dfa_state<mpl::true_, mpl::pair<mpl::vector<>, mpl::vector<> > > {};
+ struct state_name : dfa_state<> {};
+ struct state_finish : dfa_state<mpl::true_> {};
+ struct state_data : dfa_state<mpl::true_> {};
+ struct state_transitions : dfa_state<mpl::true_> {};
+ struct transition_name : dfa_state<> {};
+ struct transition_target : dfa_state<> {};
+ struct transition_match : dfa_state<mpl::true_> {};
+ struct transition_recurse : dfa_state<mpl::true_> {};
+ struct transition_post_action : dfa_state<mpl::true_> {};
+ struct transition_pre_action : dfa_state<mpl::true_> {};
+ struct transition_done : dfa_state<mpl::true_> {};
+
+ // there are two horrible thing about building at DFA this way:
+ // - the states, transitions, and graph are all specified separately
+ // - the data-building actions have to work with sequences of sequences, which is tedious
+ // the aim here is to solve problem #1. #2 might be fixed with semantic action edsl?
+
+ // anyway, we have to build
+ // - a sequence of states, each of which contains a sequnce of transitions
+ // - a map from state/transition to data
+ // luckily we can build this all from bottom up. so,
+ // - dfa level returns pair <state sequence, stmap>
+ // - state returns sequence <name, args, transitions, stmap>
+ // - transition returns the sequence of its args
+ // where stmap is sequence of pairs <state/transition name, value>
+
+ // because at_c doesn't work in lambdas (clarity too i guess)
+ template<typename S> struct s_name : mpl::at_c<S, 0> {};
+ template<typename S> struct s_args : mpl::at_c<S, 1> {};
+ template<typename S> struct s_transitions : mpl::at_c<S, 2> {};
+ template<typename S> struct s_stmap : mpl::at_c<S, 3> {};
+
+ template<typename T> struct t_name : mpl::at_c<T, 0> {};
+ template<typename T> struct t_target : mpl::at_c<T, 1> {};
+ template<typename T> struct t_args : mpl::pop_front<typename mpl::pop_front<T>::type> {};
+
+ // types for transitions
+ struct dfa_a_state :
+ dfa_transition<match_token<state<> >,
+ state_name,
+ // rebuild dfa data, pushing state onto both state seq and stmap
+ mpl::pair<mpl::push_back<mpl::first<mpl::_1>,
+ mpl::pair<s_name<mpl::_2>,
+ s_transitions<mpl::_2> > >,
+ mpl::push_back<mpl::copy<s_stmap<mpl::_2>,
+ mpl::back_inserter<mpl::second<mpl::_1> > >,
+ mpl::pair<s_name<mpl::_2>,
+ detail::apply_seq_q<dfa_state>
+ ::apply<s_args<mpl::_2> > > > > > {};
+ struct state_name_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::vector4<mpl::_2, mpl::vector<>, mpl::vector<>, mpl::vector<> > > {};
+ struct state_finish_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::vector4<s_name<mpl::_1>, mpl::vector1<mpl::_2>, mpl::vector<>, mpl::vector<> > > {};
+
+ struct state_data_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::vector4<s_name<mpl::_1>,
+ mpl::push_back<s_args<mpl::_1>, mpl::_2>,
+ mpl::vector<>, mpl::vector<> > > {};
+ struct state_transition :
+ dfa_transition<match_token<transition<> >,
+ transition_name,
+ // rebuild state data, pushing new transition onto transitions and stmap
+ mpl::vector4<s_name<mpl::_1>, s_args<mpl::_1>,
+ mpl::push_back<s_transitions<mpl::_1>,
+ mpl::pair<t_name<mpl::_2>, t_target<mpl::_2> > >,
+ mpl::push_back<s_stmap<mpl::_1>,
+ mpl::pair<t_name<mpl::_2>,
+ detail::apply_seq_q<dfa_transition>
+ ::apply<t_args<mpl::_2> > > > >
+ > {};
+ struct state_name_transition : state_transition {};
+ struct state_finish_transition : state_transition {};
+ struct transition_name_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::vector1<mpl::_2> > {};
+ struct transition_target_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::push_back<mpl::_1,mpl::_2> > {};
+ struct transition_match_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::push_back<mpl::_1,mpl::_2> > {};
+ struct transition_recurse_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::push_back<mpl::_1,mpl::_2> > {};
+ struct transition_post_action_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::push_back<mpl::_1,mpl::lambda<mpl::_2> > > {};
+ struct transition_pre_action_trans :
+ dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::push_back<mpl::_1,mpl::_2> > {};
+
+ typedef boost::msm::mpl_graph::adjacency_list_graph<
+ mpl::vector<mpl::pair<dfa_states,
+ mpl::vector<mpl::pair<dfa_a_state, dfa_states> > >,
+ mpl::pair<state_name,
+ mpl::vector<mpl::pair<state_name_trans, state_finish> > >,
+ mpl::pair<state_finish,
+ mpl::vector<mpl::pair<state_name_transition, state_transitions>,
+ mpl::pair<state_finish_trans, state_data> > >,
+ mpl::pair<state_data,
+ mpl::vector<mpl::pair<state_finish_transition, state_transitions>,
+ mpl::pair<state_data_trans, state_transitions> > >,
+ mpl::pair<state_transitions,
+ mpl::vector<mpl::pair<state_transition, state_transitions> > >,
+ mpl::pair<transition_name,
+ mpl::vector<mpl::pair<transition_name_trans, transition_target> > >,
+ mpl::pair<transition_target,
+ mpl::vector<mpl::pair<transition_target_trans, transition_match> > >,
+ mpl::pair<transition_match,
+ mpl::vector<mpl::pair<transition_match_trans, transition_recurse> > >,
+ mpl::pair<transition_recurse,
+ mpl::vector<mpl::pair<transition_recurse_trans, transition_post_action> > >,
+ mpl::pair<transition_post_action,
+ mpl::vector<mpl::pair<transition_post_action_trans, transition_pre_action> > >,
+ mpl::pair<transition_pre_action,
+ mpl::vector<mpl::pair<transition_pre_action_trans, transition_done> > >
+ > > dfa_dfa;
+
+ template<typename DFADesc>
+ struct create_parser {
+ typedef typename run_dfa<dfa_dfa, dfa_states, DFADesc>::type adjacencies_and_mappings;
+ typedef typename boost::msm::mpl_graph::
+ adjacency_list_graph<typename mpl::first<adjacencies_and_mappings>::type> graph_dfa;
+ typedef typename boost::msm::mpl_graph::mpl_utils::
+ as_map<typename mpl::second<adjacencies_and_mappings>::type>::type graph_st_map;
+
+ typedef mpl::pair<graph_dfa, graph_st_map> type;
+ };
+
+}
+}
+}
Modified: sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp (original)
+++ sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -1,9 +1,12 @@
-// fusion_graph - a heterogeneous typed graph data structure
+// Copyright 2010 Gordon Woodhull. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-// (c) 2008 Gordon Woodhull
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSEmpl::_1_0.txt or copy at
-// http://www.boost.org/LICENSEmpl::_1_0.txt)
+#ifndef BOOST_METAGRAPH_FUSION_GRAPH_HPP_INCLUDED
+#define BOOST_METAGRAPH_FUSION_GRAPH_HPP_INCLUDED
+
+// fusion_graph - simple implementation of a
+// heterogeneous typed graph data structure
#include <boost/metagraph/mpl_graph/mpl_graph.hpp>
@@ -90,3 +93,5 @@
} // fusion_graph
} // metagraoh
} // boost
+
+#endif // BOOST_METAGRAPH_FUSION_GRAPH_HPP_INCLUDED
Modified: sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp (original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -56,6 +56,7 @@
};
};
+// requires IncidenceGraph
// returns pair<VisitorState, ColorState>
template<typename Graph, typename VisitorOps, typename VisitorState,
typename Vertex,
@@ -94,6 +95,7 @@
typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type;
};
+// requires IncidenceGraph, VertexListGraph
template<typename Graph, typename VisitorOps, typename VisitorState,
typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
typename ColorState = create_search_color_map::type>
Modified: sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp (original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -58,47 +58,14 @@
template<typename EST> struct fetch_target :
mpl::back<EST> {};
-//#define MPL_GRAPH_PRODUCE_OUTMAP_AS_MAP
-#ifdef MPL_GRAPH_PRODUCE_OUTMAP_AS_MAP
- // this implementation didn't work on msvc - anyway not sure if it's more efficient
- // to build all maps at once at the expense of lots of map updates, or to use
- // the many pass, easier-to-read filter-and-build algs below.
-// Source->Edge->Target map for out_*, adjacent_vertices
-template<typename ESTSequence>
-struct produce_il_outs_map :
- mpl::fold<ESTSequence,
- mpl::map<>,
- mpl::insert<mpl::_1,
- mpl::pair<fetch_source<mpl::_2>,
- mpl::insert<mpl::if_<mpl::has_key<mpl::_1,fetch_source<mpl::_2> >,
- mpl::at<mpl::_1,fetch_source<mpl::_2> >,
- mpl::map<> >,
- mpl::pair<fetch_edge<mpl::_2>, fetch_target<mpl::_2> > > > > >
-{};
-template<typename Source, typename ESTSequence>
-struct produce_out_map<incidence_list_tag, Source, ESTSequence> :
- mpl::at<typename produce_il_outs_map<ESTSequence>::type, Source>
-{};
-#else // produce out map by filtering est list
// Edge->Target map for an Source for out_*, adjacent_vertices
template<typename Source, typename ESTSequence>
struct produce_out_map<incidence_list_tag, Source, ESTSequence> :
-#ifdef USE_AS_MPL_MAP
- mpl::as_map<
- typename mpl::fold<typename mpl::filter_view<ESTSequence, boost::is_same<fetch_source<mpl::_1>,Source> >::type,
- mpl::vector<>,
- mpl::push_back<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_target<mpl::_2> > > >::type>
-#else
mpl::fold<typename mpl::filter_view<ESTSequence, boost::is_same<fetch_source<mpl::_1>,Source> >::type,
mpl::map<>,
mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_target<mpl::_2> > > >
-#endif
{};
-#endif
-
-/*
-*/
// Edge->Source map for a Target for in_*, degree
template<typename Target, typename ESTSequence>
struct produce_in_map<incidence_list_tag, Target, ESTSequence> :
Added: sandbox/metagraph/libs/metagraph/example/angly_graph_dfa.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/angly_graph_dfa.cpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -0,0 +1,115 @@
+// Copyright 2011 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <boost/msm/mpl_graph/adjacency_list_graph.hpp>
+#include <boost/msm/mpl_graph/depth_first_search.hpp>
+#include <boost/metagraph/angly/dfa.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/identity.hpp>
+
+#include <boost/units/detail/utility.hpp>
+
+namespace mpl = boost::mpl;
+namespace mpl_graph = boost::msm::mpl_graph;
+namespace angly = boost::metagraph::angly;
+template<typename ...>
+struct graph {};
+template<typename ...>
+struct node {};
+template<typename ...>
+struct edge {};
+//bogus
+template<typename ...>
+struct foo {};
+
+// parser for metadata text of adjacency_list format
+// graph< node< node_tag, edge< edge_tag, target_node_tag >, ...> >
+// this an example of a graph language parser, not realistic
+// define types for states
+struct graph_nodes : angly::dfa_state<mpl::true_, mpl::vector<> > {};
+struct node_name : angly::dfa_state<> {};
+struct node_edges : angly::dfa_state<mpl::true_> {};
+struct edge_name : angly::dfa_state<> {};
+struct edge_target : angly::dfa_state<> {};
+struct edge_done : angly::dfa_state<mpl::true_> {};
+// types for transitions
+struct graph_node :
+ angly::dfa_transition<angly::match_token<node<> >,
+ node_name,
+ mpl::push_back<mpl::_1, mpl::_2> > {};
+struct node_name_trans :
+ angly::dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::pair<mpl::_2, mpl::vector<> > > {};
+struct node_edge :
+ angly::dfa_transition<angly::match_token<edge<> >,
+ edge_name,
+ mpl::pair<mpl::first<mpl::_1>, mpl::push_back<mpl::second<mpl::_1>, mpl::_2> > > {};
+struct edge_name_trans :
+ angly::dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::_2> {};
+struct edge_target_trans :
+ angly::dfa_transition<mpl::always<mpl::true_>,
+ void,
+ mpl::pair<mpl::_1, mpl::_2> > {};
+
+typedef mpl_graph::adjacency_list_graph<
+ mpl::vector<mpl::pair<graph_nodes,
+ mpl::vector<mpl::pair<graph_node, graph_nodes> > >,
+ mpl::pair<node_name,
+ mpl::vector<mpl::pair<node_name_trans, node_edges> > >,
+ mpl::pair<node_edges,
+ mpl::vector<mpl::pair<node_edge, node_edges> > >,
+ mpl::pair<edge_name,
+ mpl::vector<mpl::pair<edge_name_trans, edge_target> > >,
+ mpl::pair<edge_target,
+ mpl::vector<mpl::pair<edge_target_trans, edge_done> > >
+ > > graph_dfa;
+
+
+
+typedef graph<node<edge<>,edge<graph<> > >, edge<node<> >, edge<> > nonsense;
+//typedef typename angly::run_dfa<graph_dfa, nonsense, void>::type fail;
+
+struct A {}; struct B {}; struct C {}; struct D {}; struct E {}; struct F {}; struct G {};
+struct t {}; struct u {}; struct v {}; struct w {}; struct x {}; struct y {}; struct z {};
+
+/*
+ A - t > B - v > D - x > F
+ - u > C - w > E - y > F
+ - z > G
+*/
+typedef graph<node<A, edge<t, B>, edge<u, C> >,
+ node<B, edge<v, D> >,
+ node<C, edge<w, E> >,
+ node<D, edge<x, F> >,
+ node<E, edge<y, F>, edge<z, G> > > adjacencies;
+
+typedef typename angly::run_dfa<graph_dfa, graph_nodes, adjacencies>::type graph_data;
+typedef typename mpl_graph::adjacency_list_graph<graph_data> parsed_graph;
+struct preordering_visitor : mpl_graph::dfs_default_visitor_operations {
+ template<typename Node, typename Graph, typename State>
+ struct discover_vertex :
+ mpl::push_back<State, Node>
+ {};
+};
+
+// preordering, default start node (first)
+typedef mpl::first<mpl_graph::
+ depth_first_search<parsed_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ A>::type>::type preorder;
+
+BOOST_MPL_ASSERT(( mpl::equal<preorder, mpl::vector<A,B,D,F,C,E,G> > ));
+
+//boost::metagraph::angly::detail::print<preorder> x;
+
+int main() {
+ return 0;
+}
+
Added: sandbox/metagraph/libs/metagraph/example/angly_graph_parser.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/angly_graph_parser.cpp 2011-08-21 22:12:56 EDT (Sun, 21 Aug 2011)
@@ -0,0 +1,102 @@
+// Copyright 2011 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <boost/msm/mpl_graph/adjacency_list_graph.hpp>
+#include <boost/msm/mpl_graph/depth_first_search.hpp>
+#include <boost/metagraph/angly/dfa_lang.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/mpl/joint_view.hpp>
+
+#include <boost/units/detail/utility.hpp>
+
+namespace mpl = boost::mpl;
+namespace mpl_graph = boost::msm::mpl_graph;
+namespace angly = boost::metagraph::angly;
+
+
+// ****
+// great we have a language for DFAs. now test it by building a DFA for graphs
+
+template<typename ...>
+struct graph {};
+template<typename ...>
+struct node {};
+template<typename ...>
+struct edge {};
+
+struct graph_nodes {}; struct node_name {}; struct node_edges {};
+struct edge_name {}; struct edge_target {}; struct edge_done {};
+struct graph_node {}; struct node_name_trans {}; struct node_edge {};
+struct edge_name_trans {}; struct edge_target_trans {};
+
+typedef angly::dfa<angly::state<graph_nodes, mpl::true_, mpl::vector<>,
+ angly::transition<graph_node, graph_nodes,
+ angly::match_token<node<> >, node_name,
+ mpl::push_back<mpl::_1, mpl::_2> > >,
+ angly::state<node_name,
+ angly::transition<node_name_trans, node_edges,
+ mpl::always<mpl::true_>, void,
+ mpl::pair<mpl::_2, mpl::vector<> > > >,
+ angly::state<node_edges, mpl::true_,
+ angly::transition<node_edge, node_edges,
+ angly::match_token<edge<> >, edge_name,
+ mpl::pair<mpl::first<mpl::_1>,
+ mpl::push_back<mpl::second<mpl::_1>,
+ mpl::_2> > > >,
+ angly::state<edge_name,
+ angly::transition<edge_name_trans, edge_target,
+ mpl::always<mpl::true_>, void, mpl::_2> >,
+ angly::state<edge_target,
+ angly::transition<edge_target_trans, edge_done,
+ mpl::always<mpl::true_>, void,
+ mpl::pair<mpl::_1, mpl::_2> > >,
+ angly::state<edge_done, mpl::true_>
+ > graph_dfa_desc;
+
+typedef typename angly::create_parser<graph_dfa_desc>::type graph_parser;
+
+//boost::metagraph::angly::detail::print<mpl::second<graph_parser_and_stmap>::type> blah_blah;
+
+struct A {}; struct B {}; struct C {}; struct D {}; struct E {}; struct F {}; struct G {};
+struct t {}; struct u {}; struct v {}; struct w {}; struct x {}; struct y {}; struct z {};
+
+/*
+ A - t > B - v > D - x > F
+ - u > C - w > E - y > F
+ - z > G
+*/
+typedef graph<node<A, edge<t, B>, edge<u, C> >,
+ node<B, edge<v, D> >,
+ node<C, edge<w, E> >,
+ node<D, edge<x, F> >,
+ node<E, edge<y, F>, edge<z, G> > > adjacencies;
+
+typedef typename angly::run_dfa<typename mpl::first<graph_parser>::type, graph_nodes, adjacencies, mpl::at<typename mpl::second<graph_parser>::type, mpl::_1> >::type graph_data;
+typedef typename mpl_graph::adjacency_list_graph<graph_data> parsed_graph;
+struct preordering_visitor : mpl_graph::dfs_default_visitor_operations {
+ template<typename Node, typename Graph, typename State>
+ struct discover_vertex :
+ mpl::push_back<State, Node>
+ {};
+};
+
+// preordering, default start node (first)
+typedef mpl::first<mpl_graph::
+ depth_first_search<parsed_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ A>::type>::type preorder;
+
+BOOST_MPL_ASSERT(( mpl::equal<preorder, mpl::vector<A,B,D,F,C,E,G> > ));
+
+//boost::metagraph::angly::detail::print<preorder> x;
+
+
+int main() {
+ return 0;
+}
+
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk