libstdc++-v3/include/bits/regex_nfa.h

   1 // class template regex -*- C++ -*-
   2
   3 // Copyright (C) 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  *  @file bits/regex_nfa.h
  27  *  This is an internal header file, included by other library headers.
  28  *  Do not attempt to use it directly. @headername{regex}
  29  */
  30
  31 _GLIBCXX_BEGIN_NAMESPACE(std)
  32
  33 namespace __regex
  34 {
  35
  36   // Base class for, um, automata.  Could be an NFA or a DFA.  Your choice.
  37   class _Automaton
  38   {
  39   public:
  40     typedef unsigned int _SizeT;
  41
  42   public:
  43     virtual
  44     ~_Automaton()
  45     { }
  46
  47     virtual _SizeT
  48     _M_sub_count() const = 0;
  49
  50 #ifdef _GLIBCXX_DEBUG
  51     virtual std::ostream&
  52     _M_dot(std::ostream& __ostr) const = 0;
  53 #endif
  54   };
  55
  56   // Generic shred pointer to an automaton.
  57   typedef std::shared_ptr<_Automaton> _AutomatonPtr;
  58
  59   // Operation codes that define the type of transitions within the base NFA
  60   // that represents the regular expression.
  61   enum _Opcode
  62   {
  63       _S_opcode_unknown       =   0,
  64       _S_opcode_alternative   =   1,
  65       _S_opcode_subexpr_begin =   4,
  66       _S_opcode_subexpr_end   =   5,
  67       _S_opcode_match         = 100,
  68       _S_opcode_accept        = 255
  69   };
  70
  71   // Provides a generic facade for a templated match_results.
  72   struct _Results
  73   {
  74     virtual void _M_set_pos(int __i, int __j, const _PatternCursor& __p) = 0;
  75     virtual void _M_set_matched(int __i, bool __is_matched) = 0;
  76   };
  77
  78   // Tags current state (for subexpr begin/end).
  79   typedef std::function<void (const _PatternCursor&, _Results&)> _Tagger;
  80
  81   template<typename _FwdIterT, typename _TraitsT>
  82     struct _StartTagger
  83     : public _Tagger
  84     {
  85       explicit
  86       _StartTagger(int __i)
  87       : _M_index(__i)
  88       { }
  89
  90       void
  91       operator()(const _PatternCursor& __pc, _Results& __r)
  92       { __r._M_set_pos(_M_index, 0, __pc); }
  93
  94       int       _M_index;
  95     };
  96
  97   template<typename _FwdIterT, typename _TraitsT>
  98     struct _EndTagger
  99     : public _Tagger
 100     {
 101       explicit
 102       _EndTagger(int __i)
 103       : _M_index(__i)
 104       { }
 105
 106       void
 107       operator()(const _PatternCursor& __pc, _Results& __r)
 108       { __r._M_set_pos(_M_index, 1, __pc); }
 109
 110       int       _M_index;
 111       _FwdIterT _M_pos;
 112     };
 113   // Indicates if current state matches cursor current.
 114   typedef std::function<bool (const _PatternCursor&)> _Matcher;
 115
 116   // Matches any character
 117   inline bool
 118   _AnyMatcher(const _PatternCursor&)
 119   { return true; }
 120
 121   // Matches a single character
 122   template<typename _InIterT, typename _TraitsT>
 123     struct _CharMatcher
 124     : public _Matcher
 125     {
 126       typedef typename _TraitsT::char_type char_type;
 127
 128       explicit
 129       _CharMatcher(char_type __c, const _TraitsT& __t = _TraitsT())
 130       : _M_traits(__t), _M_c(_M_traits.translate(__c))
 131       { }
 132
 133       bool
 134       operator()(const _PatternCursor& __pc) const
 135       {
 136         typedef const _SpecializedCursor<_InIterT>& _CursorT;
 137         _CursorT __c = static_cast<_CursorT>(__pc);
 138         return _M_traits.translate(__c._M_current()) == _M_c;
 139       }
 140
 141       const _TraitsT& _M_traits;
 142       char_type       _M_c;
 143     };
 144
 145   // Matches a character range (bracket expression)
 146   template<typename _InIterT, typename _TraitsT>
 147     struct _RangeMatcher
 148     : public _Matcher
 149     {
 150       typedef typename _TraitsT::char_type _CharT;
 151       typedef std::basic_string<_CharT>    _StringT;
 152
 153       explicit
 154       _RangeMatcher(bool __is_non_matching, const _TraitsT& __t = _TraitsT())
 155       : _M_traits(__t), _M_is_non_matching(__is_non_matching)
 156       { }
 157
 158       bool
 159       operator()(const _PatternCursor& __pc) const
 160       {
 161         typedef const _SpecializedCursor<_InIterT>& _CursorT;
 162         _CursorT __c = static_cast<_CursorT>(__pc);
 163         return true;
 164       }
 165
 166       void
 167       _M_add_char(_CharT __c)
 168       { }
 169
 170       void
 171       _M_add_collating_element(const _StringT& __s)
 172       { }
 173
 174       void
 175       _M_add_equivalence_class(const _StringT& __s)
 176       { }
 177
 178       void
 179       _M_add_character_class(const _StringT& __s)
 180       { }
 181
 182       void
 183       _M_make_range()
 184       { }
 185
 186       const _TraitsT& _M_traits;
 187       bool            _M_is_non_matching;
 188     };
 189
 190   // Identifies a state in the NFA.
 191   typedef int _StateIdT;
 192
 193   // The special case in which a state identifier is not an index.
 194   static const _StateIdT _S_invalid_state_id  = -1;
 195
 196
 197   // An individual state in an NFA
 198   //
 199   // In this case a "state" is an entry in the NFA definition coupled with its
 200   // outgoing transition(s).  All states have a single outgoing transition,
 201   // except for accepting states (which have no outgoing transitions) and alt
 202   // states, which have two outgoing transitions.
 203   //
 204   struct _State
 205   {
 206     typedef int  _OpcodeT;
 207
 208     _OpcodeT     _M_opcode;    // type of outgoing transition
 209     _StateIdT    _M_next;      // outgoing tranition
 210     _StateIdT    _M_alt;       // for _S_opcode_alternative
 211     unsigned int _M_subexpr;   // for _S_opcode_subexpr_*
 212     _Tagger      _M_tagger;    // for _S_opcode_subexpr_*
 213     _Matcher     _M_matches;   // for _S_opcode_match
 214
 215     explicit _State(_OpcodeT __opcode)
 216     : _M_opcode(__opcode), _M_next(_S_invalid_state_id)
 217     { }
 218
 219     _State(const _Matcher& __m)
 220     : _M_opcode(_S_opcode_match), _M_next(_S_invalid_state_id), _M_matches(__m)
 221     { }
 222
 223     _State(_OpcodeT __opcode, unsigned int __s, const _Tagger& __t)
 224     : _M_opcode(__opcode), _M_next(_S_invalid_state_id), _M_subexpr(__s),
 225       _M_tagger(__t)
 226     { }
 227
 228     _State(_StateIdT __next, _StateIdT __alt)
 229     : _M_opcode(_S_opcode_alternative), _M_next(__next), _M_alt(__alt)
 230     { }
 231
 232 #ifdef _GLIBCXX_DEBUG
 233     std::ostream&
 234     _M_print(std::ostream& ostr) const;
 235
 236     // Prints graphviz dot commands for state.
 237     std::ostream&
 238     _M_dot(std::ostream& __ostr, _StateIdT __id) const;
 239 #endif
 240   };
 241
 242
 243   // The Grep Matcher works on sets of states.  Here are sets of states.
 244   typedef std::set<_StateIdT> _StateSet;
 245
 246  // A collection of all states making up an NFA
 247   //
 248   // An NFA is a 4-tuple M = (K, S, s, F), where
 249   //    K is a finite set of states,
 250   //    S is the alphabet of the NFA,
 251   //    s is the initial state,
 252   //    F is a set of final (accepting) states.
 253   //
 254   // This NFA class is templated on S, a type that will hold values of the
 255   // underlying alphabet (without regard to semantics of that alphabet).  The
 256   // other elements of the tuple are generated during construction of the NFA
 257   // and are available through accessor member functions.
 258   //
 259   class _Nfa
 260   : public _Automaton, public std::vector<_State>
 261   {
 262   public:
 263     typedef _State                              _StateT;
 264     typedef unsigned int                        _SizeT;
 265     typedef regex_constants::syntax_option_type _FlagT;
 266
 267   public:
 268     _Nfa(_FlagT __f)
 269     : _M_flags(__f), _M_start_state(0), _M_subexpr_count(0)
 270     { }
 271
 272     ~_Nfa()
 273     { }
 274
 275     _FlagT
 276     _M_options() const
 277     { return _M_flags; }
 278
 279     _StateIdT
 280     _M_start() const
 281     { return _M_start_state; }
 282
 283     const _StateSet&
 284     _M_final_states() const
 285     { return _M_accepting_states; }
 286
 287     _SizeT
 288     _M_sub_count() const
 289     { return _M_subexpr_count; }
 290
 291     _StateIdT
 292     _M_insert_accept()
 293     {
 294       this->push_back(_StateT(_S_opcode_accept));
 295       _M_accepting_states.insert(this->size()-1);
 296       return this->size()-1;
 297     }
 298
 299     _StateIdT
 300     _M_insert_alt(_StateIdT __next, _StateIdT __alt)
 301     {
 302       this->push_back(_StateT(__next, __alt));
 303       return this->size()-1;
 304     }
 305
 306     _StateIdT
 307     _M_insert_matcher(_Matcher __m)
 308     {
 309       this->push_back(_StateT(__m));
 310       return this->size()-1;
 311     }
 312
 313     _StateIdT
 314     _M_insert_subexpr_begin(const _Tagger& __t)
 315     {
 316       this->push_back(_StateT(_S_opcode_subexpr_begin, _M_subexpr_count++, __t));
 317       return this->size()-1;
 318     }
 319
 320     _StateIdT
 321     _M_insert_subexpr_end(unsigned int __i, const _Tagger& __t)
 322     {
 323       this->push_back(_StateT(_S_opcode_subexpr_end, __i, __t));
 324       return this->size()-1;
 325     }
 326
 327 #ifdef _GLIBCXX_DEBUG
 328     std::ostream&
 329     _M_dot(std::ostream& __ostr) const;
 330 #endif
 331
 332   private:
 333     _FlagT     _M_flags;
 334     _StateIdT  _M_start_state;
 335     _StateSet  _M_accepting_states;
 336     _SizeT     _M_subexpr_count;
 337   };
 338
 339   // Describes a sequence of one or more %_State, its current start and end(s).
 340   //
 341   // This structure contains fragments of an NFA during construction.
 342   class _StateSeq
 343   {
 344   public:
 345     // Constructs a single-node sequence
 346     _StateSeq(_Nfa& __ss, _StateIdT __s, _StateIdT __e = _S_invalid_state_id)
 347     : _M_nfa(__ss), _M_start(__s), _M_end1(__s), _M_end2(__e)
 348     { }
 349     // Constructs a split sequence from two other sequencces
 350     _StateSeq(const _StateSeq& __e1, const _StateSeq& __e2)
 351     : _M_nfa(__e1._M_nfa),
 352       _M_start(_M_nfa._M_insert_alt(__e1._M_start, __e2._M_start)),
 353       _M_end1(__e1._M_end1), _M_end2(__e2._M_end1)
 354     { }
 355
 356     // Constructs a split sequence from a single sequence
 357     _StateSeq(const _StateSeq& __e, _StateIdT __id)
 358     : _M_nfa(__e._M_nfa),
 359       _M_start(_M_nfa._M_insert_alt(__id, __e._M_start)),
 360       _M_end1(__id), _M_end2(__e._M_end1)
 361     { }
 362
 363     // Constructs a copy of a %_StateSeq
 364     _StateSeq(const _StateSeq& __rhs)
 365     : _M_nfa(__rhs._M_nfa), _M_start(__rhs._M_start),
 366       _M_end1(__rhs._M_end1), _M_end2(__rhs._M_end2)
 367     { }
 368
 369
 370     _StateSeq& operator=(const _StateSeq& __rhs);
 371
 372     _StateIdT
 373     _M_front() const
 374     { return _M_start; }
 375
 376     // Extends a sequence by one.
 377     void
 378     _M_push_back(_StateIdT __id);
 379
 380     // Extends and maybe joins a sequence.
 381     void
 382     _M_append(_StateIdT __id);
 383
 384     void
 385     _M_append(_StateSeq& __rhs);
 386
 387     // Clones an entire sequence.
 388     _StateIdT
 389     _M_clone();
 390
 391   private:
 392     _Nfa&     _M_nfa;
 393     _StateIdT _M_start;
 394     _StateIdT _M_end1;
 395     _StateIdT _M_end2;
 396
 397   };
 398
 399 } // namespace __regex
 400
 401 _GLIBCXX_END_NAMESPACE
 402
 403 #include <bits/regex_nfa.tcc>
 404