NCBI C++ ToolKit
regex.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 // Tencent is pleased to support the open source community by making RapidJSON available.
2 //
3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
4 //
5 // Licensed under the MIT License (the "License"); you may not use this file except
6 // in compliance with the License. You may obtain a copy of the License at
7 //
8 // http://opensource.org/licenses/MIT
9 //
10 // Unless required by applicable law or agreed to in writing, software distributed
11 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
12 // CONDITIONS OF ANY KIND, either express or implied. See the License for the
13 // specific language governing permissions and limitations under the License.
14 
15 #ifndef RAPIDJSON_INTERNAL_REGEX_H_
16 #define RAPIDJSON_INTERNAL_REGEX_H_
17 
18 #include "../allocators.h"
19 #include "../stream.h"
20 #include "stack.h"
21 
22 #ifdef __clang__
23 RAPIDJSON_DIAG_PUSH
24 RAPIDJSON_DIAG_OFF(padded)
25 RAPIDJSON_DIAG_OFF(switch-enum)
26 RAPIDJSON_DIAG_OFF(implicit-fallthrough)
27 #endif
28 
29 #ifdef __GNUC__
30 RAPIDJSON_DIAG_PUSH
31 RAPIDJSON_DIAG_OFF(effc++)
32 #endif
33 
34 #ifdef _MSC_VER
35 RAPIDJSON_DIAG_PUSH
36 RAPIDJSON_DIAG_OFF(4512) // assignment operator could not be generated
37 #endif
38 
39 #ifndef RAPIDJSON_REGEX_VERBOSE
40 #define RAPIDJSON_REGEX_VERBOSE 0
41 #endif
42 
44 namespace internal {
45 
46 ///////////////////////////////////////////////////////////////////////////////
47 // DecodedStream
48 
49 template <typename SourceStream, typename Encoding>
51 public:
52  DecodedStream(SourceStream& ss) : ss_(ss), codepoint_() { Decode(); }
53  unsigned Peek() { return codepoint_; }
54  unsigned Take() {
55  unsigned c = codepoint_;
56  if (c) // No further decoding when '\0'
57  Decode();
58  return c;
59  }
60 
61 private:
62  void Decode() {
63  if (!Encoding::Decode(ss_, &codepoint_))
64  codepoint_ = 0;
65  }
66 
67  SourceStream& ss_;
68  unsigned codepoint_;
69 };
70 
71 ///////////////////////////////////////////////////////////////////////////////
72 // GenericRegex
73 
74 static const SizeType kRegexInvalidState = ~SizeType(0); //!< Represents an invalid index in GenericRegex::State::out, out1
76 
77 template <typename Encoding, typename Allocator>
78 class GenericRegexSearch;
79 
80 //! Regular expression engine with subset of ECMAscript grammar.
81 /*!
82  Supported regular expression syntax:
83  - \c ab Concatenation
84  - \c a|b Alternation
85  - \c a? Zero or one
86  - \c a* Zero or more
87  - \c a+ One or more
88  - \c a{3} Exactly 3 times
89  - \c a{3,} At least 3 times
90  - \c a{3,5} 3 to 5 times
91  - \c (ab) Grouping
92  - \c ^a At the beginning
93  - \c a$ At the end
94  - \c . Any character
95  - \c [abc] Character classes
96  - \c [a-c] Character class range
97  - \c [a-z0-9_] Character class combination
98  - \c [^abc] Negated character classes
99  - \c [^a-c] Negated character class range
100  - \c [\b] Backspace (U+0008)
101  - \c \\| \\\\ ... Escape characters
102  - \c \\f Form feed (U+000C)
103  - \c \\n Line feed (U+000A)
104  - \c \\r Carriage return (U+000D)
105  - \c \\t Tab (U+0009)
106  - \c \\v Vertical tab (U+000B)
107 
108  \note This is a Thompson NFA engine, implemented with reference to
109  Cox, Russ. "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby,...).",
110  https://swtch.com/~rsc/regexp/regexp1.html
111 */
112 template <typename Encoding, typename Allocator = CrtAllocator>
114 public:
116  typedef typename Encoding::Ch Ch;
117  template <typename, typename> friend class GenericRegexSearch;
118 
119  GenericRegex(const Ch* source, Allocator* allocator = 0) :
120  states_(allocator, 256), ranges_(allocator, 256), root_(kRegexInvalidState), stateCount_(), rangeCount_(),
121  anchorBegin_(), anchorEnd_()
122  {
125  Parse(ds);
126  }
127 
129 
130  bool IsValid() const {
131  return root_ != kRegexInvalidState;
132  }
133 
134 private:
135  enum Operator {
141  kLeftParenthesis
142  };
143 
144  static const unsigned kAnyCharacterClass = 0xFFFFFFFF; //!< For '.'
145  static const unsigned kRangeCharacterClass = 0xFFFFFFFE;
146  static const unsigned kRangeNegationFlag = 0x80000000;
147 
148  struct Range {
149  unsigned start; //
150  unsigned end;
152  };
153 
154  struct State {
155  SizeType out; //!< Equals to kInvalid for matching state
156  SizeType out1; //!< Equals to non-kInvalid for split
158  unsigned codepoint;
159  };
160 
161  struct Frag {
162  Frag(SizeType s, SizeType o, SizeType m) : start(s), out(o), minIndex(m) {}
164  SizeType out; //!< link-list of all output states
166  };
167 
169  RAPIDJSON_ASSERT(index < stateCount_);
170  return states_.template Bottom<State>()[index];
171  }
172 
173  const State& GetState(SizeType index) const {
174  RAPIDJSON_ASSERT(index < stateCount_);
175  return states_.template Bottom<State>()[index];
176  }
177 
179  RAPIDJSON_ASSERT(index < rangeCount_);
180  return ranges_.template Bottom<Range>()[index];
181  }
182 
183  const Range& GetRange(SizeType index) const {
184  RAPIDJSON_ASSERT(index < rangeCount_);
185  return ranges_.template Bottom<Range>()[index];
186  }
187 
188  template <typename InputStream>
190  Allocator allocator;
191  Stack<Allocator> operandStack(&allocator, 256); // Frag
192  Stack<Allocator> operatorStack(&allocator, 256); // Operator
193  Stack<Allocator> atomCountStack(&allocator, 256); // unsigned (Atom per parenthesis)
194 
195  *atomCountStack.template Push<unsigned>() = 0;
196 
197  unsigned codepoint;
198  while (ds.Peek() != 0) {
199  switch (codepoint = ds.Take()) {
200  case '^':
201  anchorBegin_ = true;
202  break;
203 
204  case '$':
205  anchorEnd_ = true;
206  break;
207 
208  case '|':
209  while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() < kAlternation)
210  if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
211  return;
212  *operatorStack.template Push<Operator>() = kAlternation;
213  *atomCountStack.template Top<unsigned>() = 0;
214  break;
215 
216  case '(':
217  *operatorStack.template Push<Operator>() = kLeftParenthesis;
218  *atomCountStack.template Push<unsigned>() = 0;
219  break;
220 
221  case ')':
222  while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() != kLeftParenthesis)
223  if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
224  return;
225  if (operatorStack.Empty())
226  return;
227  operatorStack.template Pop<Operator>(1);
228  atomCountStack.template Pop<unsigned>(1);
229  ImplicitConcatenation(atomCountStack, operatorStack);
230  break;
231 
232  case '?':
233  if (!Eval(operandStack, kZeroOrOne))
234  return;
235  break;
236 
237  case '*':
238  if (!Eval(operandStack, kZeroOrMore))
239  return;
240  break;
241 
242  case '+':
243  if (!Eval(operandStack, kOneOrMore))
244  return;
245  break;
246 
247  case '{':
248  {
249  unsigned n, m;
250  if (!ParseUnsigned(ds, &n))
251  return;
252 
253  if (ds.Peek() == ',') {
254  ds.Take();
255  if (ds.Peek() == '}')
256  m = kInfinityQuantifier;
257  else if (!ParseUnsigned(ds, &m) || m < n)
258  return;
259  }
260  else
261  m = n;
262 
263  if (!EvalQuantifier(operandStack, n, m) || ds.Peek() != '}')
264  return;
265  ds.Take();
266  }
267  break;
268 
269  case '.':
270  PushOperand(operandStack, kAnyCharacterClass);
271  ImplicitConcatenation(atomCountStack, operatorStack);
272  break;
273 
274  case '[':
275  {
276  SizeType range;
277  if (!ParseRange(ds, &range))
278  return;
279  SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, kRangeCharacterClass);
280  GetState(s).rangeStart = range;
281  *operandStack.template Push<Frag>() = Frag(s, s, s);
282  }
283  ImplicitConcatenation(atomCountStack, operatorStack);
284  break;
285 
286  case '\\': // Escape character
287  if (!CharacterEscape(ds, &codepoint))
288  return; // Unsupported escape character
289  // fall through to default
290 
291  default: // Pattern character
292  PushOperand(operandStack, codepoint);
293  ImplicitConcatenation(atomCountStack, operatorStack);
294  }
295  }
296 
297  while (!operatorStack.Empty())
298  if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
299  return;
300 
301  // Link the operand to matching state.
302  if (operandStack.GetSize() == sizeof(Frag)) {
303  Frag* e = operandStack.template Pop<Frag>(1);
304  Patch(e->out, NewState(kRegexInvalidState, kRegexInvalidState, 0));
305  root_ = e->start;
306 
307 #if RAPIDJSON_REGEX_VERBOSE
308  printf("root: %d\n", root_);
309  for (SizeType i = 0; i < stateCount_ ; i++) {
310  State& s = GetState(i);
311  printf("[%2d] out: %2d out1: %2d c: '%c'\n", i, s.out, s.out1, (char)s.codepoint);
312  }
313  printf("\n");
314 #endif
315  }
316  }
317 
318  SizeType NewState(SizeType out, SizeType out1, unsigned codepoint) {
319  State* s = states_.template Push<State>();
320  s->out = out;
321  s->out1 = out1;
322  s->codepoint = codepoint;
324  return stateCount_++;
325  }
326 
327  void PushOperand(Stack<Allocator>& operandStack, unsigned codepoint) {
328  SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, codepoint);
329  *operandStack.template Push<Frag>() = Frag(s, s, s);
330  }
331 
332  void ImplicitConcatenation(Stack<Allocator>& atomCountStack, Stack<Allocator>& operatorStack) {
333  if (*atomCountStack.template Top<unsigned>())
334  *operatorStack.template Push<Operator>() = kConcatenation;
335  (*atomCountStack.template Top<unsigned>())++;
336  }
337 
339  SizeType old = l1;
340  while (GetState(l1).out != kRegexInvalidState)
341  l1 = GetState(l1).out;
342  GetState(l1).out = l2;
343  return old;
344  }
345 
346  void Patch(SizeType l, SizeType s) {
347  for (SizeType next; l != kRegexInvalidState; l = next) {
348  next = GetState(l).out;
349  GetState(l).out = s;
350  }
351  }
352 
353  bool Eval(Stack<Allocator>& operandStack, Operator op) {
354  switch (op) {
355  case kConcatenation:
356  RAPIDJSON_ASSERT(operandStack.GetSize() >= sizeof(Frag) * 2);
357  {
358  Frag e2 = *operandStack.template Pop<Frag>(1);
359  Frag e1 = *operandStack.template Pop<Frag>(1);
360  Patch(e1.out, e2.start);
361  *operandStack.template Push<Frag>() = Frag(e1.start, e2.out, Min(e1.minIndex, e2.minIndex));
362  }
363  return true;
364 
365  case kAlternation:
366  if (operandStack.GetSize() >= sizeof(Frag) * 2) {
367  Frag e2 = *operandStack.template Pop<Frag>(1);
368  Frag e1 = *operandStack.template Pop<Frag>(1);
369  SizeType s = NewState(e1.start, e2.start, 0);
370  *operandStack.template Push<Frag>() = Frag(s, Append(e1.out, e2.out), Min(e1.minIndex, e2.minIndex));
371  return true;
372  }
373  return false;
374 
375  case kZeroOrOne:
376  if (operandStack.GetSize() >= sizeof(Frag)) {
377  Frag e = *operandStack.template Pop<Frag>(1);
378  SizeType s = NewState(kRegexInvalidState, e.start, 0);
379  *operandStack.template Push<Frag>() = Frag(s, Append(e.out, s), e.minIndex);
380  return true;
381  }
382  return false;
383 
384  case kZeroOrMore:
385  if (operandStack.GetSize() >= sizeof(Frag)) {
386  Frag e = *operandStack.template Pop<Frag>(1);
387  SizeType s = NewState(kRegexInvalidState, e.start, 0);
388  Patch(e.out, s);
389  *operandStack.template Push<Frag>() = Frag(s, s, e.minIndex);
390  return true;
391  }
392  return false;
393 
394  default:
395  RAPIDJSON_ASSERT(op == kOneOrMore);
396  if (operandStack.GetSize() >= sizeof(Frag)) {
397  Frag e = *operandStack.template Pop<Frag>(1);
398  SizeType s = NewState(kRegexInvalidState, e.start, 0);
399  Patch(e.out, s);
400  *operandStack.template Push<Frag>() = Frag(e.start, s, e.minIndex);
401  return true;
402  }
403  return false;
404  }
405  }
406 
407  bool EvalQuantifier(Stack<Allocator>& operandStack, unsigned n, unsigned m) {
408  RAPIDJSON_ASSERT(n <= m);
409  RAPIDJSON_ASSERT(operandStack.GetSize() >= sizeof(Frag));
410 
411  if (n == 0) {
412  if (m == 0) // a{0} not support
413  return false;
414  else if (m == kInfinityQuantifier)
415  Eval(operandStack, kZeroOrMore); // a{0,} -> a*
416  else {
417  Eval(operandStack, kZeroOrOne); // a{0,5} -> a?
418  for (unsigned i = 0; i < m - 1; i++)
419  CloneTopOperand(operandStack); // a{0,5} -> a? a? a? a? a?
420  for (unsigned i = 0; i < m - 1; i++)
421  Eval(operandStack, kConcatenation); // a{0,5} -> a?a?a?a?a?
422  }
423  return true;
424  }
425 
426  for (unsigned i = 0; i < n - 1; i++) // a{3} -> a a a
427  CloneTopOperand(operandStack);
428 
429  if (m == kInfinityQuantifier)
430  Eval(operandStack, kOneOrMore); // a{3,} -> a a a+
431  else if (m > n) {
432  CloneTopOperand(operandStack); // a{3,5} -> a a a a
433  Eval(operandStack, kZeroOrOne); // a{3,5} -> a a a a?
434  for (unsigned i = n; i < m - 1; i++)
435  CloneTopOperand(operandStack); // a{3,5} -> a a a a? a?
436  for (unsigned i = n; i < m; i++)
437  Eval(operandStack, kConcatenation); // a{3,5} -> a a aa?a?
438  }
439 
440  for (unsigned i = 0; i < n - 1; i++)
441  Eval(operandStack, kConcatenation); // a{3} -> aaa, a{3,} -> aaa+, a{3.5} -> aaaa?a?
442 
443  return true;
444  }
445 
446  static SizeType Min(SizeType a, SizeType b) { return a < b ? a : b; }
447 
448  void CloneTopOperand(Stack<Allocator>& operandStack) {
449  const Frag src = *operandStack.template Top<Frag>(); // Copy constructor to prevent invalidation
450  SizeType count = stateCount_ - src.minIndex; // Assumes top operand contains states in [src->minIndex, stateCount_)
451  State* s = states_.template Push<State>(count);
452  memcpy(s, &GetState(src.minIndex), count * sizeof(State));
453  for (SizeType j = 0; j < count; j++) {
454  if (s[j].out != kRegexInvalidState)
455  s[j].out += count;
456  if (s[j].out1 != kRegexInvalidState)
457  s[j].out1 += count;
458  }
459  *operandStack.template Push<Frag>() = Frag(src.start + count, src.out + count, src.minIndex + count);
460  stateCount_ += count;
461  }
462 
463  template <typename InputStream>
465  unsigned r = 0;
466  if (ds.Peek() < '0' || ds.Peek() > '9')
467  return false;
468  while (ds.Peek() >= '0' && ds.Peek() <= '9') {
469  if (r >= 429496729 && ds.Peek() > '5') // 2^32 - 1 = 4294967295
470  return false; // overflow
471  r = r * 10 + (ds.Take() - '0');
472  }
473  *u = r;
474  return true;
475  }
476 
477  template <typename InputStream>
479  bool isBegin = true;
480  bool negate = false;
481  int step = 0;
483  SizeType current = kRegexInvalidRange;
484  unsigned codepoint;
485  while ((codepoint = ds.Take()) != 0) {
486  if (isBegin) {
487  isBegin = false;
488  if (codepoint == '^') {
489  negate = true;
490  continue;
491  }
492  }
493 
494  switch (codepoint) {
495  case ']':
496  if (start == kRegexInvalidRange)
497  return false; // Error: nothing inside []
498  if (step == 2) { // Add trailing '-'
499  SizeType r = NewRange('-');
501  GetRange(current).next = r;
502  }
503  if (negate)
504  GetRange(start).start |= kRangeNegationFlag;
505  *range = start;
506  return true;
507 
508  case '\\':
509  if (ds.Peek() == 'b') {
510  ds.Take();
511  codepoint = 0x0008; // Escape backspace character
512  }
513  else if (!CharacterEscape(ds, &codepoint))
514  return false;
515  // fall through to default
516 
517  default:
518  switch (step) {
519  case 1:
520  if (codepoint == '-') {
521  step++;
522  break;
523  }
524  // fall through to step 0 for other characters
525 
526  case 0:
527  {
528  SizeType r = NewRange(codepoint);
529  if (current != kRegexInvalidRange)
530  GetRange(current).next = r;
531  if (start == kRegexInvalidRange)
532  start = r;
533  current = r;
534  }
535  step = 1;
536  break;
537 
538  default:
539  RAPIDJSON_ASSERT(step == 2);
540  GetRange(current).end = codepoint;
541  step = 0;
542  }
543  }
544  }
545  return false;
546  }
547 
548  SizeType NewRange(unsigned codepoint) {
549  Range* r = ranges_.template Push<Range>();
550  r->start = r->end = codepoint;
551  r->next = kRegexInvalidRange;
552  return rangeCount_++;
553  }
554 
555  template <typename InputStream>
556  bool CharacterEscape(DecodedStream<InputStream, Encoding>& ds, unsigned* escapedCodepoint) {
557  unsigned codepoint;
558  switch (codepoint = ds.Take()) {
559  case '^':
560  case '$':
561  case '|':
562  case '(':
563  case ')':
564  case '?':
565  case '*':
566  case '+':
567  case '.':
568  case '[':
569  case ']':
570  case '{':
571  case '}':
572  case '\\':
573  *escapedCodepoint = codepoint; return true;
574  case 'f': *escapedCodepoint = 0x000C; return true;
575  case 'n': *escapedCodepoint = 0x000A; return true;
576  case 'r': *escapedCodepoint = 0x000D; return true;
577  case 't': *escapedCodepoint = 0x0009; return true;
578  case 'v': *escapedCodepoint = 0x000B; return true;
579  default:
580  return false; // Unsupported escape character
581  }
582  }
583 
589 
590  static const unsigned kInfinityQuantifier = ~0u;
591 
592  // For SearchWithAnchoring()
595 };
596 
597 template <typename RegexType, typename Allocator = CrtAllocator>
599 public:
600  typedef typename RegexType::EncodingType Encoding;
601  typedef typename Encoding::Ch Ch;
602 
603  GenericRegexSearch(const RegexType& regex, Allocator* allocator = 0) :
604  regex_(regex), allocator_(allocator), ownAllocator_(0),
605  state0_(allocator, 0), state1_(allocator, 0), stateSet_()
606  {
607  RAPIDJSON_ASSERT(regex_.IsValid());
608  if (!allocator_)
609  ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator)();
610  stateSet_ = static_cast<unsigned*>(allocator_->Malloc(GetStateSetSize()));
611  state0_.template Reserve<SizeType>(regex_.stateCount_);
612  state1_.template Reserve<SizeType>(regex_.stateCount_);
613  }
614 
616  Allocator::Free(stateSet_);
617  RAPIDJSON_DELETE(ownAllocator_);
618  }
619 
620  template <typename InputStream>
621  bool Match(InputStream& is) {
622  return SearchWithAnchoring(is, true, true);
623  }
624 
625  bool Match(const Ch* s) {
627  return Match(is);
628  }
629 
630  template <typename InputStream>
631  bool Search(InputStream& is) {
632  return SearchWithAnchoring(is, regex_.anchorBegin_, regex_.anchorEnd_);
633  }
634 
635  bool Search(const Ch* s) {
637  return Search(is);
638  }
639 
640 private:
641  typedef typename RegexType::State State;
642  typedef typename RegexType::Range Range;
643 
644  template <typename InputStream>
645  bool SearchWithAnchoring(InputStream& is, bool anchorBegin, bool anchorEnd) {
647 
648  state0_.Clear();
649  Stack<Allocator> *current = &state0_, *next = &state1_;
650  const size_t stateSetSize = GetStateSetSize();
651  std::memset(stateSet_, 0, stateSetSize);
652 
653  bool matched = AddState(*current, regex_.root_);
654  unsigned codepoint;
655  while (!current->Empty() && (codepoint = ds.Take()) != 0) {
656  std::memset(stateSet_, 0, stateSetSize);
657  next->Clear();
658  matched = false;
659  for (const SizeType* s = current->template Bottom<SizeType>(); s != current->template End<SizeType>(); ++s) {
660  const State& sr = regex_.GetState(*s);
661  if (sr.codepoint == codepoint ||
662  sr.codepoint == RegexType::kAnyCharacterClass ||
663  (sr.codepoint == RegexType::kRangeCharacterClass && MatchRange(sr.rangeStart, codepoint)))
664  {
665  matched = AddState(*next, sr.out) || matched;
666  if (!anchorEnd && matched)
667  return true;
668  }
669  if (!anchorBegin)
670  AddState(*next, regex_.root_);
671  }
672  internal::Swap(current, next);
673  }
674 
675  return matched;
676  }
677 
678  size_t GetStateSetSize() const {
679  return (regex_.stateCount_ + 31) / 32 * 4;
680  }
681 
682  // Return whether the added states is a match state
685 
686  const State& s = regex_.GetState(index);
687  if (s.out1 != kRegexInvalidState) { // Split
688  bool matched = AddState(l, s.out);
689  return AddState(l, s.out1) || matched;
690  }
691  else if (!(stateSet_[index >> 5] & (1u << (index & 31)))) {
692  stateSet_[index >> 5] |= (1u << (index & 31));
693  *l.template PushUnsafe<SizeType>() = index;
694  }
695  return s.out == kRegexInvalidState; // by using PushUnsafe() above, we can ensure s is not validated due to reallocation.
696  }
697 
698  bool MatchRange(SizeType rangeIndex, unsigned codepoint) const {
699  bool yes = (regex_.GetRange(rangeIndex).start & RegexType::kRangeNegationFlag) == 0;
700  while (rangeIndex != kRegexInvalidRange) {
701  const Range& r = regex_.GetRange(rangeIndex);
702  if (codepoint >= (r.start & ~RegexType::kRangeNegationFlag) && codepoint <= r.end)
703  return yes;
704  rangeIndex = r.next;
705  }
706  return !yes;
707  }
708 
709  const RegexType& regex_;
715 };
716 
719 
720 } // namespace internal
722 
723 #ifdef __clang__
724 RAPIDJSON_DIAG_POP
725 #endif
726 
727 #ifdef _MSC_VER
728 RAPIDJSON_DIAG_POP
729 #endif
730 
731 #endif // RAPIDJSON_INTERNAL_REGEX_H_
Concept for allocating, resizing and freeing memory block.
Concept for encoding of Unicode characters.
DecodedStream(SourceStream &ss)
Definition: regex.h:52
bool SearchWithAnchoring(InputStream &is, bool anchorBegin, bool anchorEnd)
Definition: regex.h:645
bool Search(InputStream &is)
Definition: regex.h:631
RegexType::EncodingType Encoding
Definition: regex.h:600
bool AddState(Stack< Allocator > &l, SizeType index)
Definition: regex.h:683
bool Match(InputStream &is)
Definition: regex.h:621
GenericRegexSearch(const RegexType &regex, Allocator *allocator=0)
Definition: regex.h:603
bool MatchRange(SizeType rangeIndex, unsigned codepoint) const
Definition: regex.h:698
Regular expression engine with subset of ECMAscript grammar.
Definition: regex.h:113
bool ParseRange(DecodedStream< InputStream, Encoding > &ds, SizeType *range)
Definition: regex.h:478
static SizeType Min(SizeType a, SizeType b)
Definition: regex.h:446
void PushOperand(Stack< Allocator > &operandStack, unsigned codepoint)
Definition: regex.h:327
void CloneTopOperand(Stack< Allocator > &operandStack)
Definition: regex.h:448
void ImplicitConcatenation(Stack< Allocator > &atomCountStack, Stack< Allocator > &operatorStack)
Definition: regex.h:332
bool CharacterEscape(DecodedStream< InputStream, Encoding > &ds, unsigned *escapedCodepoint)
Definition: regex.h:556
bool Eval(Stack< Allocator > &operandStack, Operator op)
Definition: regex.h:353
Range & GetRange(SizeType index)
Definition: regex.h:178
SizeType NewState(SizeType out, SizeType out1, unsigned codepoint)
Definition: regex.h:318
SizeType NewRange(unsigned codepoint)
Definition: regex.h:548
const Range & GetRange(SizeType index) const
Definition: regex.h:183
void Parse(DecodedStream< InputStream, Encoding > &ds)
Definition: regex.h:189
State & GetState(SizeType index)
Definition: regex.h:168
Stack< Allocator > states_
Definition: regex.h:584
void Patch(SizeType l, SizeType s)
Definition: regex.h:346
bool EvalQuantifier(Stack< Allocator > &operandStack, unsigned n, unsigned m)
Definition: regex.h:407
const State & GetState(SizeType index) const
Definition: regex.h:173
bool ParseUnsigned(DecodedStream< InputStream, Encoding > &ds, unsigned *u)
Definition: regex.h:464
Stack< Allocator > ranges_
Definition: regex.h:585
SizeType Append(SizeType l1, SizeType l2)
Definition: regex.h:338
GenericRegex(const Ch *source, Allocator *allocator=0)
Definition: regex.h:119
A type-unsafe stack for storing different types of data.
Definition: stack.h:36
size_t GetSize() const
Definition: stack.h:177
bool Empty() const
Definition: stack.h:176
std::ofstream out("events_result.xml")
main entry point for tests
static DLIST_TYPE *DLIST_NAME() next(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:56
Uint4 uint32_t
#define Free
Definition: ncbimem.hpp:122
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:402
#define RAPIDJSON_NAMESPACE_BEGIN
provide custom rapidjson namespace (opening expression)
Definition: rapidjson.h:116
#define RAPIDJSON_NAMESPACE_END
provide custom rapidjson namespace (closing expression)
Definition: rapidjson.h:119
fallback to Cassandra storage</td > n</tr > n</table > n</td > n< td > yes
int i
yy_size_t n
range(_Ty, _Ty) -> range< _Ty >
static const SizeType kRegexInvalidState
Represents an invalid index in GenericRegex::State::out, out1.
Definition: regex.h:74
static const SizeType kRegexInvalidRange
Definition: regex.h:75
void Swap(T &a, T &b) RAPIDJSON_NOEXCEPT
Custom swap() to avoid dependency on C++ <algorithm> header.
Definition: swap.h:33
GenericRegex< UTF8<> > Regex
Definition: regex.h:717
GenericRegexSearch< Regex > RegexSearch
Definition: regex.h:718
const CharType(& source)[N]
Definition: pointer.h:1149
unsigned SizeType
Size type (for string lengths, array sizes, etc.)
Definition: rapidjson.h:380
unsigned int a
Definition: ncbi_localip.c:102
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
#define RAPIDJSON_DELETE(x)
! customization point for global delete
Definition: rapidjson.h:596
#define RAPIDJSON_NEW(TypeName)
! customization point for global new
Definition: rapidjson.h:592
Read-only string stream.
Definition: stream.h:110
Frag(SizeType s, SizeType o, SizeType m)
Definition: regex.h:162
SizeType out
link-list of all output states
Definition: regex.h:164
SizeType out
Equals to kInvalid for matching state.
Definition: regex.h:155
SizeType out1
Equals to non-kInvalid for split.
Definition: regex.h:156
void Decode(const vector< char > &, CRawScoreVector< Key, Score > &)
Modified on Mon Apr 22 04:05:24 2024 by modify_doxy.py rev. 669887