Regex refactoring

[Jonathan Wakely <jwakely dot gcc at gmail dot com>]

I have a few ideas to simplify the regex code and slightly improve
run-time performance of compiling regexes.

1) According to my reading of the regex traits requirements in
[re.req] this should hold in basic_regex:

      static_assert(is_same<_Ch_type, typename _Rx_traits::char_type>::value,
            "regex traits class must have the same char_type");

If that's true, then we can simplify many of the class templates such
as _Compiler, _State and _NFA which currently have these template
parameters:

  template<typename _CharT, typename _Traits>
    class _NFA

This can be simplified to:

  template<typename _Traits>
    class _NFA

and then in the few places where the character type is needed it can
be obtained from typename _Traits::char_type.  (For the user-facing
std::basic_regex template it makes to specify both the char type and
traits type separately, since it allows the traits type to be
defaulted so users only need to say basic_regex<char>, but for the
library's own internal types we don't need a separate template
parameter for the char type.)

2) We should be using std::move() when inserting _State and _Matcher
objects into the _NFA, otherwise we make a copy of a std::function<>
which does memory allocation.  We should also make
_Compiler::_M_get_nfa() non-const and move the _M_nfa member into the
return value to avoid more copies of all the NFA's states and their
matchers.

3) I plan to move members of _State and _NFA that do not depend on
template parameters into new non-template base classes. This means
that different specializations like _NFA<traits1> and _NFA<traits2>
will share more code, reducing executable size.  I don't know if this
will help with the compilation speed, but I don't think it can hurt.

4) The name std::__detail::_State is a bit too generic, maybe we
should rename it to __detail::_ReState or something like that.

I'm working on patches to do all of the above, so if anyone can see
any problems with these ideas let me know before I waste more time on
it :-)

Other ideas:

The most common instantiations of _Compiler will probably use const
char*, std::string::iterator and std::string::const_iterator. It would
be good if they could all share code, since they all operate on the
same underlying character type, but I don't know if that's possible.

When we're happy that the regex code is stable and in the right form
we should consider having explicit instantiations of basic_regex<char>
exported from the library, and the instantiations of _NFA, _State,
_Compiler etc. that it needs.  I do think the code is pretty stable
and works well, but we might not want to tie ourselves down to exports
for GCC 4.9, so maybe for the next release.