Subversion Repositories openrisc

// class template regex -*- C++ -*-

// Copyright (C) 2010, 2011 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/**

 *  @file bits/regex_compiler.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{regex}

 */

namespace std _GLIBCXX_VISIBILITY(default)

{

namespace __regex

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  struct _Scanner_base

  {

    typedef unsigned int _StateT;

    static constexpr _StateT _S_state_at_start    = 1 << 0;

    static constexpr _StateT _S_state_in_brace    = 1 << 2;

    static constexpr _StateT _S_state_in_bracket  = 1 << 3;

    virtual ~_Scanner_base() { };

  };

  //

  // @brief Scans an input range for regex tokens.

  //

  // The %_Scanner class interprets the regular expression pattern in the input

  // range passed to its constructor as a sequence of parse tokens passed to

  // the regular expression compiler.  The sequence of tokens provided depends

  // on the flag settings passed to the constructor:  different regular

  // expression grammars will interpret the same input pattern in

  // syntactically different ways.

  //

  template<typename _InputIterator>

    class _Scanner: public _Scanner_base

    {

    public:

      typedef _InputIterator                                        _IteratorT;

      typedef typename std::iterator_traits<_IteratorT>::value_type _CharT;

      typedef std::basic_string<_CharT>                             _StringT;

      typedef regex_constants::syntax_option_type                   _FlagT;

      typedef const std::ctype<_CharT>                              _CtypeT;

      // Token types returned from the scanner.

      enum _TokenT

      {

        _S_token_anychar,

        _S_token_backref,

        _S_token_bracket_begin,

        _S_token_bracket_end,

        _S_token_inverse_class,

        _S_token_char_class_name,

        _S_token_closure0,

        _S_token_closure1,

        _S_token_collelem_multi,

        _S_token_collelem_single,

        _S_token_collsymbol,

        _S_token_comma,

        _S_token_dash,

        _S_token_dup_count,

        _S_token_eof,

        _S_token_equiv_class_name,

        _S_token_interval_begin,

        _S_token_interval_end,

        _S_token_line_begin,

        _S_token_line_end,

        _S_token_opt,

        _S_token_or,

        _S_token_ord_char,

        _S_token_quoted_char,

        _S_token_subexpr_begin,

        _S_token_subexpr_end,

        _S_token_word_begin,

        _S_token_word_end,

        _S_token_unknown

      };

    public:

      _Scanner(_IteratorT __begin, _IteratorT __end, _FlagT __flags,

               std::locale __loc)

      : _M_current(__begin) , _M_end(__end) , _M_flags(__flags),

        _M_ctype(std::use_facet<_CtypeT>(__loc)), _M_state(_S_state_at_start)

      { _M_advance(); }

      void

      _M_advance();

      _TokenT

      _M_token() const

      { return _M_curToken; }

      const _StringT&

      _M_value() const

      { return _M_curValue; }

#ifdef _GLIBCXX_DEBUG

      std::ostream&

      _M_print(std::ostream&);

#endif

    private:

      void

      _M_eat_escape();

      void

      _M_scan_in_brace();

      void

      _M_scan_in_bracket();

      void

      _M_eat_charclass();

      void

      _M_eat_equivclass();

      void

      _M_eat_collsymbol();

    private:

      _IteratorT  _M_current;

      _IteratorT  _M_end;

      _FlagT      _M_flags;

      _CtypeT&    _M_ctype;

      _TokenT     _M_curToken;

      _StringT    _M_curValue;

      _StateT     _M_state;

    };

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_advance()

    {

      if (_M_current == _M_end)

        {

          _M_curToken = _S_token_eof;

          return;

        }

      _CharT __c = *_M_current;

      if (_M_state & _S_state_in_bracket)

        {

          _M_scan_in_bracket();

          return;

        }

      if (_M_state & _S_state_in_brace)

        {

          _M_scan_in_brace();

          return;

        }

#if 0

      // TODO: re-enable line anchors when _M_assertion is implemented.

      // See PR libstdc++/47724

      else if (_M_state & _S_state_at_start && __c == _M_ctype.widen('^'))

        {

          _M_curToken = _S_token_line_begin;

          ++_M_current;

          return;

        }

      else if (__c == _M_ctype.widen('$'))

        {

          _M_curToken = _S_token_line_end;

          ++_M_current;

          return;

        }

#endif

      else if (__c == _M_ctype.widen('.'))

        {

          _M_curToken = _S_token_anychar;

          ++_M_current;

          return;

        }

      else if (__c == _M_ctype.widen('*'))

        {

          _M_curToken = _S_token_closure0;

          ++_M_current;

          return;

        }

      else if (__c == _M_ctype.widen('+'))

        {

          _M_curToken = _S_token_closure1;

          ++_M_current;

          return;

        }

      else if (__c == _M_ctype.widen('|'))

        {

          _M_curToken = _S_token_or;

          ++_M_current;

          return;

        }

      else if (__c == _M_ctype.widen('['))

        {

          _M_curToken = _S_token_bracket_begin;

          _M_state |= (_S_state_in_bracket | _S_state_at_start);

          ++_M_current;

          return;

        }

      else if (__c == _M_ctype.widen('\\'))

        {

          _M_eat_escape();

          return;

        }

      else if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))

        {

          if (__c == _M_ctype.widen('('))

            {

              _M_curToken = _S_token_subexpr_begin;

              ++_M_current;

              return;

            }

          else if (__c == _M_ctype.widen(')'))

            {

              _M_curToken = _S_token_subexpr_end;

              ++_M_current;

              return;

            }

          else if (__c == _M_ctype.widen('{'))

            {

              _M_curToken = _S_token_interval_begin;

              _M_state |= _S_state_in_brace;

              ++_M_current;

              return;

            }

        }

      _M_curToken = _S_token_ord_char;

      _M_curValue.assign(1, __c);

      ++_M_current;

    }

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_scan_in_brace()

    {

      if (_M_ctype.is(_CtypeT::digit, *_M_current))

        {

          _M_curToken = _S_token_dup_count;

          _M_curValue.assign(1, *_M_current);

          ++_M_current;

          while (_M_current != _M_end

                 && _M_ctype.is(_CtypeT::digit, *_M_current))

            {

              _M_curValue += *_M_current;

              ++_M_current;

            }

          return;

        }

      else if (*_M_current == _M_ctype.widen(','))

        {

          _M_curToken = _S_token_comma;

          ++_M_current;

          return;

        }

      if (_M_flags & (regex_constants::basic | regex_constants::grep))

        {

          if (*_M_current == _M_ctype.widen('\\'))

            _M_eat_escape();

        }

      else

        {

          if (*_M_current == _M_ctype.widen('}'))

            {

              _M_curToken = _S_token_interval_end;

              _M_state &= ~_S_state_in_brace;

              ++_M_current;

              return;

            }

        }

    }

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_scan_in_bracket()

    {

      if (_M_state & _S_state_at_start && *_M_current == _M_ctype.widen('^'))

        {

          _M_curToken = _S_token_inverse_class;

          _M_state &= ~_S_state_at_start;

          ++_M_current;

          return;

        }

      else if (*_M_current == _M_ctype.widen('['))

        {

          ++_M_current;

          if (_M_current == _M_end)

            {

              _M_curToken = _S_token_eof;

              return;

            }

          if (*_M_current == _M_ctype.widen('.'))

            {

              _M_curToken = _S_token_collsymbol;

              _M_eat_collsymbol();

              return;

            }

          else if (*_M_current == _M_ctype.widen(':'))

            {

              _M_curToken = _S_token_char_class_name;

              _M_eat_charclass();

              return;

            }

          else if (*_M_current == _M_ctype.widen('='))

            {

              _M_curToken = _S_token_equiv_class_name;

              _M_eat_equivclass();

              return;

            }

        }

      else if (*_M_current == _M_ctype.widen('-'))

        {

          _M_curToken = _S_token_dash;

          ++_M_current;

          return;

        }

      else if (*_M_current == _M_ctype.widen(']'))

        {

          if (!(_M_flags & regex_constants::ECMAScript)

              || !(_M_state & _S_state_at_start))

            {

              // special case: only if  _not_ chr first after

              // '[' or '[^' and if not ECMAscript

              _M_curToken = _S_token_bracket_end;

              ++_M_current;

              return;

            }

        }

      _M_curToken = _S_token_collelem_single;

      _M_curValue.assign(1, *_M_current);

      ++_M_current;

    }

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_eat_escape()

    {

      ++_M_current;

      if (_M_current == _M_end)

        {

          _M_curToken = _S_token_eof;

          return;

        }

      _CharT __c = *_M_current;

      ++_M_current;

      if (__c == _M_ctype.widen('('))

        {

          if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))

            {

              _M_curToken = _S_token_ord_char;

              _M_curValue.assign(1, __c);

            }

          else

            _M_curToken = _S_token_subexpr_begin;

        }

      else if (__c == _M_ctype.widen(')'))

        {

          if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))

            {

              _M_curToken = _S_token_ord_char;

              _M_curValue.assign(1, __c);

            }

          else

            _M_curToken = _S_token_subexpr_end;

        }

      else if (__c == _M_ctype.widen('{'))

        {

          if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))

            {

              _M_curToken = _S_token_ord_char;

              _M_curValue.assign(1, __c);

            }

          else

            {

              _M_curToken = _S_token_interval_begin;

              _M_state |= _S_state_in_brace;

            }

        }

      else if (__c == _M_ctype.widen('}'))

        {

          if (!(_M_flags & (regex_constants::basic | regex_constants::grep)))

            {

              _M_curToken = _S_token_ord_char;

              _M_curValue.assign(1, __c);

            }

          else

            {

              if (!(_M_state && _S_state_in_brace))

                __throw_regex_error(regex_constants::error_badbrace);

              _M_state &= ~_S_state_in_brace;

              _M_curToken = _S_token_interval_end;

            }

        }

      else if (__c == _M_ctype.widen('x'))

        {

          ++_M_current;

          if (_M_current == _M_end)

            {

              _M_curToken = _S_token_eof;

              return;

            }

          if (_M_ctype.is(_CtypeT::digit, *_M_current))

            {

              _M_curValue.assign(1, *_M_current);

              ++_M_current;

              if (_M_current == _M_end)

                {

                  _M_curToken = _S_token_eof;

                  return;

                }

              if (_M_ctype.is(_CtypeT::digit, *_M_current))

                {

                  _M_curValue += *_M_current;

                  ++_M_current;

                  return;

                }

            }

        }

      else if (__c == _M_ctype.widen('^')

               || __c == _M_ctype.widen('.')

               || __c == _M_ctype.widen('*')

               || __c == _M_ctype.widen('$')

               || __c == _M_ctype.widen('\\'))

        {

          _M_curToken = _S_token_ord_char;

          _M_curValue.assign(1, __c);

        }

      else if (_M_ctype.is(_CtypeT::digit, __c))

        {

          _M_curToken = _S_token_backref;

          _M_curValue.assign(1, __c);

        }

      else

        __throw_regex_error(regex_constants::error_escape);

    }

  // Eats a character class or throwns an exception.

  // current point to ':' delimiter on entry, char after ']' on return

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_eat_charclass()

    {

      ++_M_current; // skip ':'

      if (_M_current == _M_end)

        __throw_regex_error(regex_constants::error_ctype);

      for (_M_curValue.clear();

           _M_current != _M_end && *_M_current != _M_ctype.widen(':');

           ++_M_current)

        _M_curValue += *_M_current;

      if (_M_current == _M_end)

        __throw_regex_error(regex_constants::error_ctype);

      ++_M_current; // skip ':'

      if (*_M_current != _M_ctype.widen(']'))

        __throw_regex_error(regex_constants::error_ctype);

      ++_M_current; // skip ']'

    }

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_eat_equivclass()

    {

      ++_M_current; // skip '='

      if (_M_current == _M_end)

        __throw_regex_error(regex_constants::error_collate);

      for (_M_curValue.clear();

           _M_current != _M_end && *_M_current != _M_ctype.widen('=');

           ++_M_current)

        _M_curValue += *_M_current;

      if (_M_current == _M_end)

        __throw_regex_error(regex_constants::error_collate);

      ++_M_current; // skip '='

      if (*_M_current != _M_ctype.widen(']'))

        __throw_regex_error(regex_constants::error_collate);

      ++_M_current; // skip ']'

    }

  template<typename _InputIterator>

    void

    _Scanner<_InputIterator>::

    _M_eat_collsymbol()

    {

      ++_M_current; // skip '.'

      if (_M_current == _M_end)

        __throw_regex_error(regex_constants::error_collate);

      for (_M_curValue.clear();

           _M_current != _M_end && *_M_current != _M_ctype.widen('.');

           ++_M_current)

        _M_curValue += *_M_current;

      if (_M_current == _M_end)

        __throw_regex_error(regex_constants::error_collate);

      ++_M_current; // skip '.'

      if (*_M_current != _M_ctype.widen(']'))

        __throw_regex_error(regex_constants::error_collate);

      ++_M_current; // skip ']'

    }

#ifdef _GLIBCXX_DEBUG

  template<typename _InputIterator>

    std::ostream&

    _Scanner<_InputIterator>::

    _M_print(std::ostream& ostr)

    {

      switch (_M_curToken)

      {

        case _S_token_anychar:

          ostr << "any-character\n";

          break;

        case _S_token_backref:

          ostr << "backref\n";

          break;

        case _S_token_bracket_begin:

          ostr << "bracket-begin\n";

          break;

        case _S_token_bracket_end:

          ostr << "bracket-end\n";

          break;

        case _S_token_char_class_name:

          ostr << "char-class-name \"" << _M_curValue << "\"\n";

          break;

        case _S_token_closure0:

          ostr << "closure0\n";

          break;

        case _S_token_closure1:

          ostr << "closure1\n";

          break;

        case _S_token_collelem_multi:

          ostr << "coll-elem-multi \"" << _M_curValue << "\"\n";

          break;

        case _S_token_collelem_single:

          ostr << "coll-elem-single \"" << _M_curValue << "\"\n";

          break;

        case _S_token_collsymbol:

          ostr << "collsymbol \"" << _M_curValue << "\"\n";

          break;

        case _S_token_comma:

          ostr << "comma\n";

          break;

        case _S_token_dash:

          ostr << "dash\n";

          break;

        case _S_token_dup_count:

          ostr << "dup count: " << _M_curValue << "\n";

          break;

        case _S_token_eof:

          ostr << "EOF\n";

          break;

        case _S_token_equiv_class_name:

          ostr << "equiv-class-name \"" << _M_curValue << "\"\n";

          break;

        case _S_token_interval_begin:

          ostr << "interval begin\n";

          break;

        case _S_token_interval_end:

          ostr << "interval end\n";

          break;

        case _S_token_line_begin:

          ostr << "line begin\n";

          break;

        case _S_token_line_end:

          ostr << "line end\n";

          break;

        case _S_token_opt:

          ostr << "opt\n";

          break;

        case _S_token_or:

          ostr << "or\n";

          break;

        case _S_token_ord_char:

          ostr << "ordinary character: \"" << _M_value() << "\"\n";

          break;

        case _S_token_quoted_char:

          ostr << "quoted char\n";

          break;

        case _S_token_subexpr_begin:

          ostr << "subexpr begin\n";

          break;

        case _S_token_subexpr_end:

          ostr << "subexpr end\n";

          break;

        case _S_token_word_begin:

          ostr << "word begin\n";

          break;

        case _S_token_word_end:

          ostr << "word end\n";

          break;

        case _S_token_unknown:

          ostr << "-- unknown token --\n";

          break;

      }

      return ostr;

    }

#endif

  // Builds an NFA from an input iterator interval.

  template<typename _InIter, typename _TraitsT>

    class _Compiler

    {

    public:

      typedef _InIter                                            _IterT;

      typedef typename std::iterator_traits<_InIter>::value_type _CharT;

      typedef std::basic_string<_CharT>                          _StringT;

      typedef regex_constants::syntax_option_type                _FlagT;

    public:

      _Compiler(const _InIter& __b, const _InIter& __e,

                _TraitsT& __traits, _FlagT __flags);

      const _Nfa&

      _M_nfa() const

      { return _M_state_store; }

    private:

      typedef _Scanner<_InIter>                              _ScannerT;

      typedef typename _ScannerT::_TokenT                    _TokenT;

      typedef std::stack<_StateSeq, std::vector<_StateSeq> > _StackT;

      typedef _RangeMatcher<_InIter, _TraitsT>               _RMatcherT;

      // accepts a specific token or returns false.

      bool

      _M_match_token(_TokenT __token);

      void

      _M_disjunction();

      bool

      _M_alternative();

      bool

      _M_term();

      bool

      _M_assertion();

      bool

      _M_quantifier();

      bool

      _M_atom();

      bool

      _M_bracket_expression();

      bool

      _M_bracket_list(_RMatcherT& __matcher);

      bool

      _M_follow_list(_RMatcherT& __matcher);

      bool

      _M_follow_list2(_RMatcherT& __matcher);

      bool

      _M_expression_term(_RMatcherT& __matcher);

      bool

      _M_range_expression(_RMatcherT& __matcher);