libstdc++
regex_compiler.tcc
Go to the documentation of this file.
1 // class template regex -*- C++ -*-
2 
3 // Copyright (C) 2013-2021 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_compiler.tcc
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 // FIXME make comments doxygen format.
32 
33 /*
34 // This compiler refers to "Regular Expression Matching Can Be Simple And Fast"
35 // (http://swtch.com/~rsc/regexp/regexp1.html),
36 // but doesn't strictly follow it.
37 //
38 // When compiling, states are *chained* instead of tree- or graph-constructed.
39 // It's more like structured programs: there's if statement and loop statement.
40 //
41 // For alternative structure (say "a|b"), aka "if statement", two branches
42 // should be constructed. However, these two shall merge to an "end_tag" at
43 // the end of this operator:
44 //
45 // branch1
46 // / \
47 // => begin_tag end_tag =>
48 // \ /
49 // branch2
50 //
51 // This is the difference between this implementation and that in Russ's
52 // article.
53 //
54 // That's why we introduced dummy node here ------ "end_tag" is a dummy node.
55 // All dummy nodes will be eliminated at the end of compilation.
56 */
57 
58 namespace std _GLIBCXX_VISIBILITY(default)
59 {
60 _GLIBCXX_BEGIN_NAMESPACE_VERSION
61 
62 namespace __detail
63 {
64  template<typename _TraitsT>
65  _Compiler<_TraitsT>::
66  _Compiler(_IterT __b, _IterT __e,
67  const typename _TraitsT::locale_type& __loc, _FlagT __flags)
68  : _M_flags((__flags
69  & (regex_constants::ECMAScript
70  | regex_constants::basic
71  | regex_constants::extended
72  | regex_constants::grep
73  | regex_constants::egrep
74  | regex_constants::awk))
75  ? __flags
76  : __flags | regex_constants::ECMAScript),
77  _M_scanner(__b, __e, _M_flags, __loc),
78  _M_nfa(make_shared<_RegexT>(__loc, _M_flags)),
79  _M_traits(_M_nfa->_M_traits),
80  _M_ctype(std::use_facet<_CtypeT>(__loc))
81  {
82  _StateSeqT __r(*_M_nfa, _M_nfa->_M_start());
83  __r._M_append(_M_nfa->_M_insert_subexpr_begin());
84  this->_M_disjunction();
85  if (!_M_match_token(_ScannerT::_S_token_eof))
86  __throw_regex_error(regex_constants::error_paren);
87  __r._M_append(_M_pop());
88  __glibcxx_assert(_M_stack.empty());
89  __r._M_append(_M_nfa->_M_insert_subexpr_end());
90  __r._M_append(_M_nfa->_M_insert_accept());
91  _M_nfa->_M_eliminate_dummy();
92  }
93 
94  template<typename _TraitsT>
95  void
96  _Compiler<_TraitsT>::
97  _M_disjunction()
98  {
99  this->_M_alternative();
100  while (_M_match_token(_ScannerT::_S_token_or))
101  {
102  _StateSeqT __alt1 = _M_pop();
103  this->_M_alternative();
104  _StateSeqT __alt2 = _M_pop();
105  auto __end = _M_nfa->_M_insert_dummy();
106  __alt1._M_append(__end);
107  __alt2._M_append(__end);
108  // __alt2 is state._M_next, __alt1 is state._M_alt. The executor
109  // executes _M_alt before _M_next, as well as executing left
110  // alternative before right one.
111  _M_stack.push(_StateSeqT(*_M_nfa,
112  _M_nfa->_M_insert_alt(
113  __alt2._M_start, __alt1._M_start, false),
114  __end));
115  }
116  }
117 
118  template<typename _TraitsT>
119  void
120  _Compiler<_TraitsT>::
121  _M_alternative()
122  {
123  if (this->_M_term())
124  {
125  _StateSeqT __re = _M_pop();
126  this->_M_alternative();
127  __re._M_append(_M_pop());
128  _M_stack.push(__re);
129  }
130  else
131  _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_dummy()));
132  }
133 
134  template<typename _TraitsT>
135  bool
136  _Compiler<_TraitsT>::
137  _M_term()
138  {
139  if (this->_M_assertion())
140  return true;
141  if (this->_M_atom())
142  {
143  while (this->_M_quantifier());
144  return true;
145  }
146  return false;
147  }
148 
149  template<typename _TraitsT>
150  bool
151  _Compiler<_TraitsT>::
152  _M_assertion()
153  {
154  if (_M_match_token(_ScannerT::_S_token_line_begin))
155  _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_begin()));
156  else if (_M_match_token(_ScannerT::_S_token_line_end))
157  _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->_M_insert_line_end()));
158  else if (_M_match_token(_ScannerT::_S_token_word_bound))
159  // _M_value[0] == 'n' means it's negative, say "not word boundary".
160  _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
161  _M_insert_word_bound(_M_value[0] == 'n')));
162  else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
163  {
164  auto __neg = _M_value[0] == 'n';
165  this->_M_disjunction();
166  if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
167  __throw_regex_error(regex_constants::error_paren,
168  "Parenthesis is not closed.");
169  auto __tmp = _M_pop();
170  __tmp._M_append(_M_nfa->_M_insert_accept());
171  _M_stack.push(
172  _StateSeqT(
173  *_M_nfa,
174  _M_nfa->_M_insert_lookahead(__tmp._M_start, __neg)));
175  }
176  else
177  return false;
178  return true;
179  }
180 
181  template<typename _TraitsT>
182  bool
183  _Compiler<_TraitsT>::
184  _M_quantifier()
185  {
186  bool __neg = (_M_flags & regex_constants::ECMAScript);
187  auto __init = [this, &__neg]()
188  {
189  if (_M_stack.empty())
190  __throw_regex_error(regex_constants::error_badrepeat,
191  "Nothing to repeat before a quantifier.");
192  __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
193  };
194  if (_M_match_token(_ScannerT::_S_token_closure0))
195  {
196  __init();
197  auto __e = _M_pop();
198  _StateSeqT __r(*_M_nfa,
199  _M_nfa->_M_insert_repeat(_S_invalid_state_id,
200  __e._M_start, __neg));
201  __e._M_append(__r);
202  _M_stack.push(__r);
203  }
204  else if (_M_match_token(_ScannerT::_S_token_closure1))
205  {
206  __init();
207  auto __e = _M_pop();
208  __e._M_append(_M_nfa->_M_insert_repeat(_S_invalid_state_id,
209  __e._M_start, __neg));
210  _M_stack.push(__e);
211  }
212  else if (_M_match_token(_ScannerT::_S_token_opt))
213  {
214  __init();
215  auto __e = _M_pop();
216  auto __end = _M_nfa->_M_insert_dummy();
217  _StateSeqT __r(*_M_nfa,
218  _M_nfa->_M_insert_repeat(_S_invalid_state_id,
219  __e._M_start, __neg));
220  __e._M_append(__end);
221  __r._M_append(__end);
222  _M_stack.push(__r);
223  }
224  else if (_M_match_token(_ScannerT::_S_token_interval_begin))
225  {
226  if (_M_stack.empty())
227  __throw_regex_error(regex_constants::error_badrepeat,
228  "Nothing to repeat before a quantifier.");
229  if (!_M_match_token(_ScannerT::_S_token_dup_count))
230  __throw_regex_error(regex_constants::error_badbrace,
231  "Unexpected token in brace expression.");
232  _StateSeqT __r(_M_pop());
233  _StateSeqT __e(*_M_nfa, _M_nfa->_M_insert_dummy());
234  long __min_rep = _M_cur_int_value(10);
235  bool __infi = false;
236  long __n = 0;
237 
238  // {3
239  if (_M_match_token(_ScannerT::_S_token_comma))
240  {
241  if (_M_match_token(_ScannerT::_S_token_dup_count)) // {3,7}
242  __n = _M_cur_int_value(10) - __min_rep;
243  else
244  __infi = true;
245  }
246  if (!_M_match_token(_ScannerT::_S_token_interval_end))
247  __throw_regex_error(regex_constants::error_brace,
248  "Unexpected end of brace expression.");
249 
250  __neg = __neg && _M_match_token(_ScannerT::_S_token_opt);
251 
252  for (long __i = 0; __i < __min_rep; ++__i)
253  __e._M_append(__r._M_clone());
254 
255  if (__infi)
256  {
257  auto __tmp = __r._M_clone();
258  _StateSeqT __s(*_M_nfa,
259  _M_nfa->_M_insert_repeat(_S_invalid_state_id,
260  __tmp._M_start, __neg));
261  __tmp._M_append(__s);
262  __e._M_append(__s);
263  }
264  else
265  {
266  if (__n < 0)
267  __throw_regex_error(regex_constants::error_badbrace,
268  "Invalid range in brace expression.");
269  auto __end = _M_nfa->_M_insert_dummy();
270  // _M_alt is the "match more" branch, and _M_next is the
271  // "match less" one. Switch _M_alt and _M_next of all created
272  // nodes. This is a hack but IMO works well.
273  std::stack<_StateIdT> __stack;
274  for (long __i = 0; __i < __n; ++__i)
275  {
276  auto __tmp = __r._M_clone();
277  auto __alt = _M_nfa->_M_insert_repeat(__tmp._M_start,
278  __end, __neg);
279  __stack.push(__alt);
280  __e._M_append(_StateSeqT(*_M_nfa, __alt, __tmp._M_end));
281  }
282  __e._M_append(__end);
283  while (!__stack.empty())
284  {
285  auto& __tmp = (*_M_nfa)[__stack.top()];
286  __stack.pop();
287  std::swap(__tmp._M_next, __tmp._M_alt);
288  }
289  }
290  _M_stack.push(__e);
291  }
292  else
293  return false;
294  return true;
295  }
296 
297 #define __INSERT_REGEX_MATCHER(__func, ...)\
298  do {\
299  if (!(_M_flags & regex_constants::icase))\
300  if (!(_M_flags & regex_constants::collate))\
301  __func<false, false>(__VA_ARGS__);\
302  else\
303  __func<false, true>(__VA_ARGS__);\
304  else\
305  if (!(_M_flags & regex_constants::collate))\
306  __func<true, false>(__VA_ARGS__);\
307  else\
308  __func<true, true>(__VA_ARGS__);\
309  } while (false)
310 
311  template<typename _TraitsT>
312  bool
313  _Compiler<_TraitsT>::
314  _M_atom()
315  {
316  if (_M_match_token(_ScannerT::_S_token_anychar))
317  {
318  if (!(_M_flags & regex_constants::ECMAScript))
319  __INSERT_REGEX_MATCHER(_M_insert_any_matcher_posix);
320  else
321  __INSERT_REGEX_MATCHER(_M_insert_any_matcher_ecma);
322  }
323  else if (_M_try_char())
324  __INSERT_REGEX_MATCHER(_M_insert_char_matcher);
325  else if (_M_match_token(_ScannerT::_S_token_backref))
326  _M_stack.push(_StateSeqT(*_M_nfa, _M_nfa->
327  _M_insert_backref(_M_cur_int_value(10))));
328  else if (_M_match_token(_ScannerT::_S_token_quoted_class))
329  __INSERT_REGEX_MATCHER(_M_insert_character_class_matcher);
330  else if (_M_match_token(_ScannerT::_S_token_subexpr_no_group_begin))
331  {
332  _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_dummy());
333  this->_M_disjunction();
334  if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
335  __throw_regex_error(regex_constants::error_paren,
336  "Parenthesis is not closed.");
337  __r._M_append(_M_pop());
338  _M_stack.push(__r);
339  }
340  else if (_M_match_token(_ScannerT::_S_token_subexpr_begin))
341  {
342  _StateSeqT __r(*_M_nfa, _M_nfa->_M_insert_subexpr_begin());
343  this->_M_disjunction();
344  if (!_M_match_token(_ScannerT::_S_token_subexpr_end))
345  __throw_regex_error(regex_constants::error_paren,
346  "Parenthesis is not closed.");
347  __r._M_append(_M_pop());
348  __r._M_append(_M_nfa->_M_insert_subexpr_end());
349  _M_stack.push(__r);
350  }
351  else if (!_M_bracket_expression())
352  return false;
353  return true;
354  }
355 
356  template<typename _TraitsT>
357  bool
358  _Compiler<_TraitsT>::
359  _M_bracket_expression()
360  {
361  bool __neg =
362  _M_match_token(_ScannerT::_S_token_bracket_neg_begin);
363  if (!(__neg || _M_match_token(_ScannerT::_S_token_bracket_begin)))
364  return false;
365  __INSERT_REGEX_MATCHER(_M_insert_bracket_matcher, __neg);
366  return true;
367  }
368 #undef __INSERT_REGEX_MATCHER
369 
370  template<typename _TraitsT>
371  template<bool __icase, bool __collate>
372  void
373  _Compiler<_TraitsT>::
374  _M_insert_any_matcher_ecma()
375  {
376  _M_stack.push(_StateSeqT(*_M_nfa,
377  _M_nfa->_M_insert_matcher
378  (_AnyMatcher<_TraitsT, true, __icase, __collate>
379  (_M_traits))));
380  }
381 
382  template<typename _TraitsT>
383  template<bool __icase, bool __collate>
384  void
385  _Compiler<_TraitsT>::
386  _M_insert_any_matcher_posix()
387  {
388  _M_stack.push(_StateSeqT(*_M_nfa,
389  _M_nfa->_M_insert_matcher
390  (_AnyMatcher<_TraitsT, false, __icase, __collate>
391  (_M_traits))));
392  }
393 
394  template<typename _TraitsT>
395  template<bool __icase, bool __collate>
396  void
397  _Compiler<_TraitsT>::
398  _M_insert_char_matcher()
399  {
400  _M_stack.push(_StateSeqT(*_M_nfa,
401  _M_nfa->_M_insert_matcher
402  (_CharMatcher<_TraitsT, __icase, __collate>
403  (_M_value[0], _M_traits))));
404  }
405 
406  template<typename _TraitsT>
407  template<bool __icase, bool __collate>
408  void
409  _Compiler<_TraitsT>::
410  _M_insert_character_class_matcher()
411  {
412  __glibcxx_assert(_M_value.size() == 1);
413  _BracketMatcher<__icase, __collate> __matcher
414  (_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
415  __matcher._M_add_character_class(_M_value, false);
416  __matcher._M_ready();
417  _M_stack.push(_StateSeqT(*_M_nfa,
418  _M_nfa->_M_insert_matcher(std::move(__matcher))));
419  }
420 
421  template<typename _TraitsT>
422  template<bool __icase, bool __collate>
423  void
424  _Compiler<_TraitsT>::
425  _M_insert_bracket_matcher(bool __neg)
426  {
427  _BracketMatcher<__icase, __collate> __matcher(__neg, _M_traits);
428  _BracketState __last_char;
429  if (_M_try_char())
430  __last_char.set(_M_value[0]);
431  else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
432  // Dash as first character is a normal character.
433  __last_char.set('-');
434  while (_M_expression_term(__last_char, __matcher))
435  ;
436  if (__last_char._M_is_char())
437  __matcher._M_add_char(__last_char.get());
438  __matcher._M_ready();
439  _M_stack.push(_StateSeqT(
440  *_M_nfa,
441  _M_nfa->_M_insert_matcher(std::move(__matcher))));
442  }
443 
444  template<typename _TraitsT>
445  template<bool __icase, bool __collate>
446  bool
447  _Compiler<_TraitsT>::
448  _M_expression_term(_BracketState& __last_char,
449  _BracketMatcher<__icase, __collate>& __matcher)
450  {
451  if (_M_match_token(_ScannerT::_S_token_bracket_end))
452  return false;
453 
454  // Add any previously cached char into the matcher and update cache.
455  const auto __push_char = [&](_CharT __ch)
456  {
457  if (__last_char._M_is_char())
458  __matcher._M_add_char(__last_char.get());
459  __last_char.set(__ch);
460  };
461  // Add any previously cached char into the matcher and update cache.
462  const auto __push_class = [&]
463  {
464  if (__last_char._M_is_char())
465  __matcher._M_add_char(__last_char.get());
466  // We don't cache anything here, just record that the last thing
467  // processed was a character class (or similar).
468  __last_char.reset(_BracketState::_Type::_Class);
469  };
470 
471  if (_M_match_token(_ScannerT::_S_token_collsymbol))
472  {
473  auto __symbol = __matcher._M_add_collate_element(_M_value);
474  if (__symbol.size() == 1)
475  __push_char(__symbol[0]);
476  else
477  __push_class();
478  }
479  else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
480  {
481  __push_class();
482  __matcher._M_add_equivalence_class(_M_value);
483  }
484  else if (_M_match_token(_ScannerT::_S_token_char_class_name))
485  {
486  __push_class();
487  __matcher._M_add_character_class(_M_value, false);
488  }
489  else if (_M_try_char())
490  __push_char(_M_value[0]);
491  // POSIX doesn't allow '-' as a start-range char (say [a-z--0]),
492  // except when the '-' is the first or last character in the bracket
493  // expression ([--0]). ECMAScript treats all '-' after a range as a
494  // normal character. Also see above, where _M_expression_term gets called.
495  //
496  // As a result, POSIX rejects [-----], but ECMAScript doesn't.
497  // Boost (1.57.0) always uses POSIX style even in its ECMAScript syntax.
498  // Clang (3.5) always uses ECMAScript style even in its POSIX syntax.
499  //
500  // It turns out that no one reads BNFs ;)
501  else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
502  {
503  if (_M_match_token(_ScannerT::_S_token_bracket_end))
504  {
505  // For "-]" the dash is a literal character.
506  __push_char('-');
507  return false;
508  }
509  else if (__last_char._M_is_class())
510  {
511  // "\\w-" is invalid, start of range must be a single char.
512  __throw_regex_error(regex_constants::error_range,
513  "Invalid start of range in bracket expression.");
514  }
515  else if (__last_char._M_is_char())
516  {
517  if (_M_try_char())
518  {
519  // "x-y"
520  __matcher._M_make_range(__last_char.get(), _M_value[0]);
521  __last_char.reset();
522  }
523  else if (_M_match_token(_ScannerT::_S_token_bracket_dash))
524  {
525  // "x--"
526  __matcher._M_make_range(__last_char.get(), '-');
527  __last_char.reset();
528  }
529  else
530  __throw_regex_error(regex_constants::error_range,
531  "Invalid end of range in bracket expression.");
532  }
533  else if (_M_flags & regex_constants::ECMAScript)
534  {
535  // A dash that is not part of an existing range. Might be the
536  // start of a new range, or might just be a literal '-' char.
537  // Only ECMAScript allows that in the middle of a bracket expr.
538  __push_char('-');
539  }
540  else
541  __throw_regex_error(regex_constants::error_range,
542  "Invalid dash in bracket expression.");
543  }
544  else if (_M_match_token(_ScannerT::_S_token_quoted_class))
545  {
546  __push_class();
547  __matcher._M_add_character_class(_M_value,
548  _M_ctype.is(_CtypeT::upper,
549  _M_value[0]));
550  }
551  else
552  __throw_regex_error(regex_constants::error_brack,
553  "Unexpected character in bracket expression.");
554 
555  return true;
556  }
557 
558  template<typename _TraitsT>
559  bool
560  _Compiler<_TraitsT>::
561  _M_try_char()
562  {
563  bool __is_char = false;
564  if (_M_match_token(_ScannerT::_S_token_oct_num))
565  {
566  __is_char = true;
567  _M_value.assign(1, _M_cur_int_value(8));
568  }
569  else if (_M_match_token(_ScannerT::_S_token_hex_num))
570  {
571  __is_char = true;
572  _M_value.assign(1, _M_cur_int_value(16));
573  }
574  else if (_M_match_token(_ScannerT::_S_token_ord_char))
575  __is_char = true;
576  return __is_char;
577  }
578 
579  template<typename _TraitsT>
580  bool
581  _Compiler<_TraitsT>::
582  _M_match_token(_TokenT __token)
583  {
584  if (__token == _M_scanner._M_get_token())
585  {
586  _M_value = _M_scanner._M_get_value();
587  _M_scanner._M_advance();
588  return true;
589  }
590  return false;
591  }
592 
593  template<typename _TraitsT>
594  int
595  _Compiler<_TraitsT>::
596  _M_cur_int_value(int __radix)
597  {
598  long __v = 0;
599  for (typename _StringT::size_type __i = 0;
600  __i < _M_value.length(); ++__i)
601  __v =__v * __radix + _M_traits.value(_M_value[__i], __radix);
602  return __v;
603  }
604 
605  template<typename _TraitsT, bool __icase, bool __collate>
606  bool
607  _BracketMatcher<_TraitsT, __icase, __collate>::
608  _M_apply(_CharT __ch, false_type) const
609  {
610  return [this, __ch]
611  {
612  if (std::binary_search(_M_char_set.begin(), _M_char_set.end(),
613  _M_translator._M_translate(__ch)))
614  return true;
615  auto __s = _M_translator._M_transform(__ch);
616  for (auto& __it : _M_range_set)
617  if (_M_translator._M_match_range(__it.first, __it.second, __s))
618  return true;
619  if (_M_traits.isctype(__ch, _M_class_set))
620  return true;
621  if (std::find(_M_equiv_set.begin(), _M_equiv_set.end(),
622  _M_traits.transform_primary(&__ch, &__ch+1))
623  != _M_equiv_set.end())
624  return true;
625  for (auto& __it : _M_neg_class_set)
626  if (!_M_traits.isctype(__ch, __it))
627  return true;
628  return false;
629  }() ^ _M_is_non_matching;
630  }
631 } // namespace __detail
632 
633 _GLIBCXX_END_NAMESPACE_VERSION
634 } // namespace
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:86
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
const _Facet & use_facet(const locale &__loc)
Return a facet.
ISO C++ entities toplevel namespace is std.
constexpr error_type error_brace(_S_error_brace)
constexpr error_type error_badbrace(_S_error_badbrace)
constexpr error_type error_range(_S_error_range)
constexpr syntax_option_type ECMAScript
constexpr error_type error_badrepeat(_S_error_badrepeat)
constexpr syntax_option_type egrep
constexpr error_type error_paren(_S_error_paren)
constexpr syntax_option_type awk
constexpr syntax_option_type extended
constexpr syntax_option_type basic
constexpr error_type error_brack(_S_error_brack)
constexpr syntax_option_type grep
A standard container giving FILO behavior.
Definition: stl_stack.h:100
void pop()
Removes first element.
Definition: stl_stack.h:272
void push(const value_type &__x)
Add data to the top of the stack.
Definition: stl_stack.h:239
bool empty() const
Definition: stl_stack.h:199
reference top()
Definition: stl_stack.h:212