[boost] FSM idea injetion

From: Alexander Nasonov (alnsn-mycop_at_[hidden])
Date: 2004-05-29 16:47:09

Although my idea is supposed to solve multimethod support for dynamic_any it
might be useful in FSM library.
What I'm trying to build in last two weeks is some sort of typelists for
overloaded function set. Each function is identified by overload_id<N>
class with unique N. For example:

struct read_number_transitions
{
    // Signatures has the form NewState (OldState, Char)
    Positive operator()(overload_id<0>, StartState, Plus) const;
    Negative operator()(overload_id<1>, StartState, Minus) const;
    Positive operator()(overload_id<2>, StartState, Digit) const;
    Positive operator()(overload_id<3>, Positive, Digit) const;
    Negative operator()(overload_id<4>, Negative, Digit) const;

    static std::size_t const max_overload_id = 4;
};

This approach has advantage over typelists in some cases because things are
right in their places. In the example, every transition, on one hand, is
represented by a call operator (this is natural, because transition is a
function that takes old state and a char and returns a new state); on the
other hand, argument types and return type (a signature) can be retrieved
from the call operator.
The retrieval is a bit problematic but I'm working on this. The problem is a
lack of typeof in C++. If it were available you could write:

template<int N, class C, class R, class T>
mpl::identity<R(T)> tester(R (C::*)(overload_id<N>, T) const);

typedef typeof(tester<0>(&read_number_transitions::operator()))::type sig0;

Without typeof you know signature R(T) only inside tester<0>. This means in
particular, that, in order to accumulate all signatures you have to call
tester<N> recursively:

call tester<0> => Positive(StartState, Plus)
  call tester<1> => Negative(StartState, Minus)
    call tester<2> => Positive (StartState, Digit)
      call tester<3> => Positive (Positive, Digit)
        call tester<4> => Negative (Negative, Digit)

For other compile-time algorithms we need something similar. Even worse,
often we need chain of algorithms, for example: find a first occurrence of
StartState as a first argument, get a return type from that signature, find
that type among first arguments and so on. We have to go deeper and deeper.
In my stress tests I use 1000 functions. Can you imagine a call stack as
deep as 1000 multiplied by a length of algorithms chain?

Fortunately, sometimes it's possible to make it plain.

1. Predicates have boolean result, therefore, we can use
sizeof/yes_type/no_type to calculate their result:

template<class Predicate, int N, class C, class R, class T>
typename yes_type_if<
    Predicate::template apply<R(T)>::type // mpl::apply style
>::type tester(R (C::*)(overload_id<N>, T) const);

// Example
bool const result = sizeof(
  tester<is_same<Positive(Positive,Digit), _1>, 3>(&read_number_transitions)
) == sizeof(yes_type);

I already implemented several variants of *contains* algorithm. You can take
a look at g++ 3.4.0 performance here:
http://cpp-experiment.sourceforge.net/overloads_contains.png
This is a performance plot (in seconds) of various strategies for *contains*
algorithm which is applied to a function set of length 1000. Worst case
takes 80+ seconds to compile for *one-at-once linear* basic strategy while
optimized strategy completes its job in 12 seconds. It's really fast. I
doubt that typelist of length 1000 can ever exist without compiler panic
;-)

Similar work can be done for find/find_if

// returns bool
contains<read_number_transitions, Negative(Negative,Digit)>::value;

// returns index of Negative(Negative,Digit)
find<read_number_transitions, Negative(Negative,Digit)>::value;

// returns -1 because int isn't even a signature
find_if<read_number_transitions,is_same<int, _1> >::value;

2. Pair comparisons. It's not yet done. The sizeof trick can be modified
slightly:

template<class Predicate, int N, int M,
         class C, class R1, class R2, class T1, class T2>
typename yes_type_if<
    Predicate::template apply<R1(T1), R2(T2)>::type
>::type tester(
            R1 (C::*)(overload_id<N>, T1) const,
            R2 (C::*)(overload_id<M>, T2) const
        );

Suppose, you have this cool type:

typedef is_base_and_derived<
    function_arg<1, _1>, // first argument of signature _1
    function_arg<1, _2>  // first argument of signature _2
> cool;

Then you can check whether a first argument of overload N is a base of a
first argument of overload M:

bool const result = sizeof(
    tester<cool,N,M>(&read_number_transitions, &read_number_transitions)
) == 1;

-- 
Alexander Nasonov