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