OSDN Git Service

2011-03-14 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / regex_nfa.h
1 // class template regex -*- C++ -*-
2
3 // Copyright (C) 2010, 2011 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 namespace std _GLIBCXX_VISIBILITY(default)
32 {
33 namespace __regex
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36
37   // Base class for, um, automata.  Could be an NFA or a DFA.  Your choice.
38   class _Automaton
39   {
40   public:
41     typedef unsigned int _SizeT;
42
43   public:
44     virtual
45     ~_Automaton() { }
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 shared 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     {
84       explicit
85       _StartTagger(int __i)
86       : _M_index(__i)
87       { }
88
89       void
90       operator()(const _PatternCursor& __pc, _Results& __r)
91       { __r._M_set_pos(_M_index, 0, __pc); }
92
93       int       _M_index;
94     };
95
96   template<typename _FwdIterT, typename _TraitsT>
97     struct _EndTagger
98     {
99       explicit
100       _EndTagger(int __i)
101       : _M_index(__i)
102       { }
103
104       void
105       operator()(const _PatternCursor& __pc, _Results& __r)
106       { __r._M_set_pos(_M_index, 1, __pc); }
107
108       int       _M_index;
109       _FwdIterT _M_pos;
110     };
111   // Indicates if current state matches cursor current.
112   typedef std::function<bool (const _PatternCursor&)> _Matcher;
113
114   // Matches any character
115   inline bool
116   _AnyMatcher(const _PatternCursor&)
117   { return true; }
118
119   // Matches a single character
120   template<typename _InIterT, typename _TraitsT>
121     struct _CharMatcher
122     {
123       typedef typename _TraitsT::char_type char_type;
124
125       explicit
126       _CharMatcher(char_type __c, const _TraitsT& __t = _TraitsT())
127       : _M_traits(__t), _M_c(_M_traits.translate(__c))
128       { }
129
130       bool
131       operator()(const _PatternCursor& __pc) const
132       {
133         typedef const _SpecializedCursor<_InIterT>& _CursorT;
134         _CursorT __c = static_cast<_CursorT>(__pc);
135         return _M_traits.translate(__c._M_current()) == _M_c;
136       }
137
138       const _TraitsT& _M_traits;
139       char_type       _M_c;
140     };
141
142   // Matches a character range (bracket expression)
143   template<typename _InIterT, typename _TraitsT>
144     struct _RangeMatcher
145     {
146       typedef typename _TraitsT::char_type _CharT;
147       typedef std::basic_string<_CharT>    _StringT;
148
149       explicit
150       _RangeMatcher(bool __is_non_matching, const _TraitsT& __t = _TraitsT())
151       : _M_traits(__t), _M_is_non_matching(__is_non_matching)
152       { }
153
154       bool
155       operator()(const _PatternCursor& __pc) const
156       {
157         typedef const _SpecializedCursor<_InIterT>& _CursorT;
158         _CursorT __c = static_cast<_CursorT>(__pc);
159         return true;
160       }
161
162       void
163       _M_add_char(_CharT __c)
164       { }
165
166       void
167       _M_add_collating_element(const _StringT& __s)
168       { }
169
170       void
171       _M_add_equivalence_class(const _StringT& __s)
172       { }
173
174       void
175       _M_add_character_class(const _StringT& __s)
176       { }
177
178       void
179       _M_make_range()
180       { }
181
182       const _TraitsT& _M_traits;
183       bool            _M_is_non_matching;
184     };
185
186   // Identifies a state in the NFA.
187   typedef int _StateIdT;
188
189   // The special case in which a state identifier is not an index.
190   static const _StateIdT _S_invalid_state_id  = -1;
191
192
193   // An individual state in an NFA
194   //
195   // In this case a "state" is an entry in the NFA definition coupled with its
196   // outgoing transition(s).  All states have a single outgoing transition,
197   // except for accepting states (which have no outgoing transitions) and alt
198   // states, which have two outgoing transitions.
199   //
200   struct _State
201   {
202     typedef int  _OpcodeT;
203
204     _OpcodeT     _M_opcode;    // type of outgoing transition
205     _StateIdT    _M_next;      // outgoing transition
206     _StateIdT    _M_alt;       // for _S_opcode_alternative
207     unsigned int _M_subexpr;   // for _S_opcode_subexpr_*
208     _Tagger      _M_tagger;    // for _S_opcode_subexpr_*
209     _Matcher     _M_matches;   // for _S_opcode_match
210
211     explicit _State(_OpcodeT __opcode)
212     : _M_opcode(__opcode), _M_next(_S_invalid_state_id)
213     { }
214
215     _State(const _Matcher& __m)
216     : _M_opcode(_S_opcode_match), _M_next(_S_invalid_state_id), _M_matches(__m)
217     { }
218
219     _State(_OpcodeT __opcode, unsigned int __s, const _Tagger& __t)
220     : _M_opcode(__opcode), _M_next(_S_invalid_state_id), _M_subexpr(__s),
221       _M_tagger(__t)
222     { }
223
224     _State(_StateIdT __next, _StateIdT __alt)
225     : _M_opcode(_S_opcode_alternative), _M_next(__next), _M_alt(__alt)
226     { }
227
228 #ifdef _GLIBCXX_DEBUG
229     std::ostream&
230     _M_print(std::ostream& ostr) const;
231
232     // Prints graphviz dot commands for state.
233     std::ostream&
234     _M_dot(std::ostream& __ostr, _StateIdT __id) const;
235 #endif
236   };
237
238   
239   // The Grep Matcher works on sets of states.  Here are sets of states.
240   typedef std::set<_StateIdT> _StateSet;
241
242  // A collection of all states making up an NFA
243   //
244   // An NFA is a 4-tuple M = (K, S, s, F), where
245   //    K is a finite set of states,
246   //    S is the alphabet of the NFA,
247   //    s is the initial state,
248   //    F is a set of final (accepting) states.
249   //
250   // This NFA class is templated on S, a type that will hold values of the
251   // underlying alphabet (without regard to semantics of that alphabet).  The
252   // other elements of the tuple are generated during construction of the NFA
253   // and are available through accessor member functions.
254   //
255   class _Nfa
256   : public _Automaton, public std::vector<_State>
257   {
258   public:
259     typedef _State                              _StateT;
260     typedef unsigned int                        _SizeT;
261     typedef regex_constants::syntax_option_type _FlagT;
262
263   public:
264     _Nfa(_FlagT __f)
265     : _M_flags(__f), _M_start_state(0), _M_subexpr_count(0)
266     { }
267
268     ~_Nfa()
269     { }
270
271     _FlagT
272     _M_options() const
273     { return _M_flags; }
274
275     _StateIdT
276     _M_start() const
277     { return _M_start_state; }
278
279     const _StateSet&
280     _M_final_states() const
281     { return _M_accepting_states; }
282
283     _SizeT
284     _M_sub_count() const
285     { return _M_subexpr_count; }
286
287     _StateIdT
288     _M_insert_accept()
289     {
290       this->push_back(_StateT(_S_opcode_accept));
291       _M_accepting_states.insert(this->size()-1);
292       return this->size()-1;
293     }
294
295     _StateIdT
296     _M_insert_alt(_StateIdT __next, _StateIdT __alt)
297     {
298       this->push_back(_StateT(__next, __alt));
299       return this->size()-1;
300     }
301
302     _StateIdT
303     _M_insert_matcher(_Matcher __m)
304     {
305       this->push_back(_StateT(__m));
306       return this->size()-1;
307     }
308
309     _StateIdT
310     _M_insert_subexpr_begin(const _Tagger& __t)
311     {
312       this->push_back(_StateT(_S_opcode_subexpr_begin, _M_subexpr_count++, __t));
313       return this->size()-1;
314     }
315
316     _StateIdT 
317     _M_insert_subexpr_end(unsigned int __i, const _Tagger& __t)
318     {
319       this->push_back(_StateT(_S_opcode_subexpr_end, __i, __t));
320       return this->size()-1;
321     }
322
323 #ifdef _GLIBCXX_DEBUG
324     std::ostream&
325     _M_dot(std::ostream& __ostr) const;
326 #endif
327
328   private:
329     _FlagT     _M_flags;
330     _StateIdT  _M_start_state;
331     _StateSet  _M_accepting_states;
332     _SizeT     _M_subexpr_count;
333   };
334
335   // Describes a sequence of one or more %_State, its current start and end(s).
336   //
337   // This structure contains fragments of an NFA during construction.
338   class _StateSeq
339   {
340   public:
341     // Constructs a single-node sequence
342     _StateSeq(_Nfa& __ss, _StateIdT __s, _StateIdT __e = _S_invalid_state_id)
343     : _M_nfa(__ss), _M_start(__s), _M_end1(__s), _M_end2(__e)
344     { }
345     // Constructs a split sequence from two other sequencces
346     _StateSeq(const _StateSeq& __e1, const _StateSeq& __e2)
347     : _M_nfa(__e1._M_nfa),
348       _M_start(_M_nfa._M_insert_alt(__e1._M_start, __e2._M_start)),
349       _M_end1(__e1._M_end1), _M_end2(__e2._M_end1)
350     { }
351
352     // Constructs a split sequence from a single sequence
353     _StateSeq(const _StateSeq& __e, _StateIdT __id)
354     : _M_nfa(__e._M_nfa),
355       _M_start(_M_nfa._M_insert_alt(__id, __e._M_start)),
356       _M_end1(__id), _M_end2(__e._M_end1)
357     { }
358
359     // Constructs a copy of a %_StateSeq
360     _StateSeq(const _StateSeq& __rhs)
361     : _M_nfa(__rhs._M_nfa), _M_start(__rhs._M_start),
362       _M_end1(__rhs._M_end1), _M_end2(__rhs._M_end2)
363     { }
364
365
366     _StateSeq& operator=(const _StateSeq& __rhs);
367
368     _StateIdT
369     _M_front() const
370     { return _M_start; }
371
372     // Extends a sequence by one.
373     void
374     _M_push_back(_StateIdT __id);
375
376     // Extends and maybe joins a sequence.
377     void
378     _M_append(_StateIdT __id);
379
380     void
381     _M_append(_StateSeq& __rhs);
382
383     // Clones an entire sequence.
384     _StateIdT
385     _M_clone();
386
387   private:
388     _Nfa&     _M_nfa;
389     _StateIdT _M_start;
390     _StateIdT _M_end1;
391     _StateIdT _M_end2;
392
393   };
394
395 _GLIBCXX_END_NAMESPACE_VERSION
396 } // namespace __regex
397 } // namespace std
398
399 #include <bits/regex_nfa.tcc>
400