Re: [boost] [metaparse] Practical usefulness

Subject: Re: [boost] [metaparse] Practical usefulness
From: Abel Sinkovics (abel_at_[hidden])
Date: 2015-06-03 16:45:42

Hi Phil,

On 2015-06-03 17:39, Phil Endecott wrote:
> Abel Sinkovics wrote:
>> This approach to write a type-safe printf displays the characters
>> one-by-one on an output stream. The printf library in Mpllibs does the
>> validation at compile-time and calls the "unsafe" printf at runtime (and
>> has therefore no runtime overhead).
> Well that's assuming that printf() is efficient at runtime.
> I would like to hope that
>
>    string s = "hello" + t + "world";
>
> would be more efficient than
>
>    string s = wrapper_around_printf_returning_string("hello%sworld",t.c_str());
>
> If it isn't, we're in trouble :-)
Given that the format string is known at compile-time, it should be 
possible to generate "optimal" code for it using a metaprogram. But that 
is significantly more complicated than what safe_printf currently offers.

> This reminds me of a discussion on this list back in 2008 where
> I was investigating fast ways of checking whether a character is in
> a compile-time set of characters:
>
>    http://article.gmane.org/gmane.comp.lib.boost.devel/171117
>
> In effect, I implement a template like
>
>    is_any_of<'a','e','i','o','u'>(c)
>
> or better
>
>    is_any_of<"aeiou">(c)
>
> to compute
>
>    return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
>
> In that thread, I demonstrated that this was faster than looping
> over the characters at run-time:
>
>    bool is_any_of(const char* chars, char c) { return strchr(chars,c); }
>
> The challenge is to instead convert it to something that does
> O(log N) comparisons, rather than O(N) i.e.
>
>    if (c < 'i') return is_any_of<'a','e'>(c);
>    else return is_any_of<'i','o','u'>(c);
>
>
> Does this have any relevance to Metaparse?  I'm not sure.  I think
> the hard part of this is the "meta code generation", not the "meta
> parsing".  I mention it because of the string-to-char-pack stuff.
Your input in this case is very simple: a list of characters, which is 
the input of the parsers, so "parsing" can't really add anything to it. 
Metaparse provides tools for implementing the "meta code generation" 
(transform, the fold parsers), but you still have to write it yourself 
(so the "how to do it" part is still on you).

BOOST_MP_STRING could help you here making the interface more compact: 
is_any_of<BOOST_MP_STRING("aeiou")>(c) or if you wrap it with a custom 
macro IS_ANY_OF("aeiou")(c). I see Metaparse as a tool for improving the 
interface of the libraries.

I couldn't get to the responses following your link, so I don't know if 
you have already investigated this, but if your goal is to implement it 
for one-byte characters, then you might be able to try an O(1) solution. 
Something like:

-------
template <char X, char... Cs> struct has;

template <char X> struct has<X> : std::false_type {};
template <char X, char... Cs> struct has<X, X, Cs...> : std::true_type {};

template <char X, char C, char... Cs>
struct has<X, C, Cs...> : has<C, Cs...> {};

template <char... Cs>
bool is_any_of(char c)
{
   switch (c)
   {
   case 0: return has<0, Cs...>::type::value;
   case 1: return has<1, Cs...>::type::value;
   // ...
   case 'a': return has<'a', Cs...>::type::value;
   // ...
   }
}
-----

Of course this needs to be refined (eg. is char signed...?) but I hope 
you get the idea.

Regards,
   Ábel