15#ifndef RAPIDJSON_INTERNAL_REGEX_H_
16#define RAPIDJSON_INTERNAL_REGEX_H_
18#include "../allocators.h"
24RAPIDJSON_DIAG_OFF(padded)
25RAPIDJSON_DIAG_OFF(
switch-
enum)
26RAPIDJSON_DIAG_OFF(implicit-fallthrough)
31RAPIDJSON_DIAG_OFF(effc++)
33RAPIDJSON_DIAG_OFF(implicit-fallthrough)
39RAPIDJSON_DIAG_OFF(4512)
42#ifndef RAPIDJSON_REGEX_VERBOSE
43#define RAPIDJSON_REGEX_VERBOSE 0
46RAPIDJSON_NAMESPACE_BEGIN
52template <
typename SourceStream,
typename Encoding>
55 DecodedStream(SourceStream& ss) : ss_(ss), codepoint_() { Decode(); }
56 unsigned Peek() {
return codepoint_; }
58 unsigned c = codepoint_;
66 if (!Encoding::Decode(ss_, &codepoint_))
77static const SizeType kRegexInvalidState = ~SizeType(0);
78static const SizeType kRegexInvalidRange = ~SizeType(0);
80template <
typename Encoding,
typename Allocator>
81class GenericRegexSearch;
115template <
typename Encoding,
typename Allocator = CrtAllocator>
119 typedef typename Encoding::Ch Ch;
120 template <
typename,
typename>
friend class GenericRegexSearch;
122 GenericRegex(
const Ch* source,
Allocator* allocator = 0) :
123 states_(allocator, 256), ranges_(allocator, 256), root_(kRegexInvalidState), stateCount_(), rangeCount_(),
124 anchorBegin_(), anchorEnd_()
126 GenericStringStream<Encoding> ss(source);
127 DecodedStream<GenericStringStream<Encoding>,
Encoding> ds(ss);
133 bool IsValid()
const {
134 return root_ != kRegexInvalidState;
147 static const unsigned kAnyCharacterClass = 0xFFFFFFFF;
148 static const unsigned kRangeCharacterClass = 0xFFFFFFFE;
149 static const unsigned kRangeNegationFlag = 0x80000000;
165 Frag(SizeType s, SizeType o, SizeType m) : start(s), out(o), minIndex(m) {}
171 State& GetState(SizeType index) {
173 return states_.template Bottom<State>()[index];
176 const State& GetState(SizeType index)
const {
178 return states_.template Bottom<State>()[index];
181 Range& GetRange(SizeType index) {
183 return ranges_.template Bottom<Range>()[index];
186 const Range& GetRange(SizeType index)
const {
188 return ranges_.template Bottom<Range>()[index];
191 template <
typename InputStream>
192 void Parse(DecodedStream<InputStream, Encoding>& ds) {
194 Stack<Allocator> operandStack(&allocator, 256);
195 Stack<Allocator> operatorStack(&allocator, 256);
196 Stack<Allocator> atomCountStack(&allocator, 256);
198 *atomCountStack.template Push<unsigned>() = 0;
201 while (ds.Peek() != 0) {
202 switch (codepoint = ds.Take()) {
212 while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() < kAlternation)
213 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
215 *operatorStack.template Push<Operator>() = kAlternation;
216 *atomCountStack.template Top<unsigned>() = 0;
220 *operatorStack.template Push<Operator>() = kLeftParenthesis;
221 *atomCountStack.template Push<unsigned>() = 0;
225 while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() != kLeftParenthesis)
226 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
228 if (operatorStack.Empty())
230 operatorStack.template Pop<Operator>(1);
231 atomCountStack.template Pop<unsigned>(1);
232 ImplicitConcatenation(atomCountStack, operatorStack);
236 if (!Eval(operandStack, kZeroOrOne))
241 if (!Eval(operandStack, kZeroOrMore))
246 if (!Eval(operandStack, kOneOrMore))
253 if (!ParseUnsigned(ds, &n))
256 if (ds.Peek() ==
',') {
258 if (ds.Peek() ==
'}')
259 m = kInfinityQuantifier;
260 else if (!ParseUnsigned(ds, &m) || m < n)
266 if (!EvalQuantifier(operandStack, n, m) || ds.Peek() !=
'}')
273 PushOperand(operandStack, kAnyCharacterClass);
274 ImplicitConcatenation(atomCountStack, operatorStack);
280 if (!ParseRange(ds, &range))
282 SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, kRangeCharacterClass);
283 GetState(s).rangeStart = range;
284 *operandStack.template Push<Frag>() = Frag(s, s, s);
286 ImplicitConcatenation(atomCountStack, operatorStack);
290 if (!CharacterEscape(ds, &codepoint))
295 PushOperand(operandStack, codepoint);
296 ImplicitConcatenation(atomCountStack, operatorStack);
300 while (!operatorStack.Empty())
301 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
305 if (operandStack.GetSize() ==
sizeof(Frag)) {
306 Frag* e = operandStack.template Pop<Frag>(1);
307 Patch(e->out, NewState(kRegexInvalidState, kRegexInvalidState, 0));
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);
321 SizeType NewState(SizeType out, SizeType out1,
unsigned codepoint) {
322 State* s = states_.template Push<State>();
325 s->codepoint = codepoint;
326 s->rangeStart = kRegexInvalidRange;
327 return stateCount_++;
330 void PushOperand(Stack<Allocator>& operandStack,
unsigned codepoint) {
331 SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, codepoint);
332 *operandStack.template Push<Frag>() = Frag(s, s, s);
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>())++;
341 SizeType Append(SizeType l1, SizeType l2) {
343 while (GetState(l1).out != kRegexInvalidState)
344 l1 = GetState(l1).out;
345 GetState(l1).out = l2;
349 void Patch(SizeType l, SizeType s) {
350 for (SizeType next; l != kRegexInvalidState; l = next) {
351 next = GetState(l).out;
356 bool Eval(Stack<Allocator>& operandStack, Operator op) {
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));
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));
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);
388 if (operandStack.GetSize() >=
sizeof(Frag)) {
389 Frag e = *operandStack.template Pop<Frag>(1);
390 SizeType s = NewState(kRegexInvalidState, e.start, 0);
392 *operandStack.template Push<Frag>() = Frag(s, s, e.minIndex);
399 if (operandStack.GetSize() >=
sizeof(Frag)) {
400 Frag e = *operandStack.template Pop<Frag>(1);
401 SizeType s = NewState(kRegexInvalidState, e.start, 0);
403 *operandStack.template Push<Frag>() = Frag(e.start, s, e.minIndex);
410 bool EvalQuantifier(Stack<Allocator>& operandStack,
unsigned n,
unsigned m) {
417 else if (m == kInfinityQuantifier)
418 Eval(operandStack, kZeroOrMore);
420 Eval(operandStack, kZeroOrOne);
421 for (
unsigned i = 0; i < m - 1; i++)
422 CloneTopOperand(operandStack);
423 for (
unsigned i = 0; i < m - 1; i++)
424 Eval(operandStack, kConcatenation);
429 for (
unsigned i = 0; i < n - 1; i++)
430 CloneTopOperand(operandStack);
432 if (m == kInfinityQuantifier)
433 Eval(operandStack, kOneOrMore);
435 CloneTopOperand(operandStack);
436 Eval(operandStack, kZeroOrOne);
437 for (
unsigned i = n; i < m - 1; i++)
438 CloneTopOperand(operandStack);
439 for (
unsigned i = n; i < m; i++)
440 Eval(operandStack, kConcatenation);
443 for (
unsigned i = 0; i < n - 1; i++)
444 Eval(operandStack, kConcatenation);
449 static SizeType Min(SizeType a, SizeType b) {
return a < b ? a : b; }
451 void CloneTopOperand(Stack<Allocator>& operandStack) {
452 const Frag src = *operandStack.template Top<Frag>();
453 SizeType count = stateCount_ - src.minIndex;
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)
459 if (s[j].out1 != kRegexInvalidState)
462 *operandStack.template Push<Frag>() = Frag(src.start + count, src.out + count, src.minIndex + count);
463 stateCount_ += count;
466 template <
typename InputStream>
467 bool ParseUnsigned(DecodedStream<InputStream, Encoding>& ds,
unsigned* u) {
469 if (ds.Peek() <
'0' || ds.Peek() >
'9')
471 while (ds.Peek() >=
'0' && ds.Peek() <=
'9') {
472 if (r >= 429496729 && ds.Peek() >
'5')
474 r = r * 10 + (ds.Take() -
'0');
480 template <
typename InputStream>
481 bool ParseRange(DecodedStream<InputStream, Encoding>& ds, SizeType* range) {
485 SizeType start = kRegexInvalidRange;
486 SizeType current = kRegexInvalidRange;
488 while ((codepoint = ds.Take()) != 0) {
491 if (codepoint ==
'^') {
499 if (start == kRegexInvalidRange)
504 GetRange(current).next = r;
507 GetRange(start).start |= kRangeNegationFlag;
512 if (ds.Peek() ==
'b') {
516 else if (!CharacterEscape(ds, &codepoint))
523 if (codepoint ==
'-') {
532 if (current != kRegexInvalidRange)
533 GetRange(current).next = r;
534 if (start == kRegexInvalidRange)
543 GetRange(current).end = codepoint;
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_++;
558 template <
typename InputStream>
559 bool CharacterEscape(DecodedStream<InputStream, Encoding>& ds,
unsigned* escapedCodepoint) {
561 switch (codepoint = ds.Take()) {
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;
587 Stack<Allocator> states_;
588 Stack<Allocator> ranges_;
593 static const unsigned kInfinityQuantifier = ~0u;
600template <
typename RegexType,
typename Allocator = CrtAllocator>
601class GenericRegexSearch {
603 typedef typename RegexType::EncodingType
Encoding;
604 typedef typename Encoding::Ch Ch;
606 GenericRegexSearch(
const RegexType& regex,
Allocator* allocator = 0) :
607 regex_(regex), allocator_(allocator), ownAllocator_(0),
608 state0_(allocator, 0), state1_(allocator, 0), stateSet_()
613 stateSet_ =
static_cast<unsigned*
>(allocator_->Malloc(GetStateSetSize()));
614 state0_.template Reserve<SizeType>(regex_.stateCount_);
615 state1_.template Reserve<SizeType>(regex_.stateCount_);
618 ~GenericRegexSearch() {
619 Allocator::Free(stateSet_);
623 template <
typename InputStream>
624 bool Match(InputStream& is) {
625 return SearchWithAnchoring(is,
true,
true);
628 bool Match(
const Ch* s) {
629 GenericStringStream<Encoding> is(s);
633 template <
typename InputStream>
634 bool Search(InputStream& is) {
635 return SearchWithAnchoring(is, regex_.anchorBegin_, regex_.anchorEnd_);
638 bool Search(
const Ch* s) {
639 GenericStringStream<Encoding> is(s);
644 typedef typename RegexType::State State;
645 typedef typename RegexType::Range Range;
647 template <
typename InputStream>
648 bool SearchWithAnchoring(InputStream& is,
bool anchorBegin,
bool anchorEnd) {
649 DecodedStream<InputStream, Encoding> ds(is);
652 Stack<Allocator> *current = &state0_, *next = &state1_;
653 const size_t stateSetSize = GetStateSetSize();
654 std::memset(stateSet_, 0, stateSetSize);
656 bool matched = AddState(*current, regex_.root_);
658 while (!current->Empty() && (codepoint = ds.Take()) != 0) {
659 std::memset(stateSet_, 0, stateSetSize);
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)))
668 matched = AddState(*next, sr.out) || matched;
669 if (!anchorEnd && matched)
673 AddState(*next, regex_.root_);
675 internal::Swap(current, next);
681 size_t GetStateSetSize()
const {
682 return (regex_.stateCount_ + 31) / 32 * 4;
686 bool AddState(Stack<Allocator>& l, SizeType index) {
689 const State& s = regex_.GetState(index);
690 if (s.out1 != kRegexInvalidState) {
691 bool matched = AddState(l, s.out);
692 return AddState(l, s.out1) || matched;
694 else if (!(stateSet_[index >> 5] & (1u << (index & 31)))) {
695 stateSet_[index >> 5] |= (1u << (index & 31));
696 *l.template PushUnsafe<SizeType>() = index;
698 return s.out == kRegexInvalidState;
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)
712 const RegexType& regex_;
715 Stack<Allocator> state0_;
716 Stack<Allocator> state1_;
720typedef GenericRegex<UTF8<> > Regex;
721typedef GenericRegexSearch<Regex> RegexSearch;
724RAPIDJSON_NAMESPACE_END
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