15 #ifndef RAPIDJSON_INTERNAL_REGEX_H_ 16 #define RAPIDJSON_INTERNAL_REGEX_H_ 18 #include "../allocators.h" 19 #include "../stream.h" 24 RAPIDJSON_DIAG_OFF(padded)
25 RAPIDJSON_DIAG_OFF(
switch-
enum)
26 RAPIDJSON_DIAG_OFF(implicit-fallthrough)
27 #elif defined(_MSC_VER) 29 RAPIDJSON_DIAG_OFF(4512)
34 RAPIDJSON_DIAG_OFF(effc++)
36 RAPIDJSON_DIAG_OFF(implicit-fallthrough)
40 #ifndef RAPIDJSON_REGEX_VERBOSE 41 #define RAPIDJSON_REGEX_VERBOSE 0 50 template <
typename SourceStream,
typename Encoding>
54 unsigned Peek() {
return codepoint_; }
56 unsigned c = codepoint_;
64 if (!Encoding::Decode(ss_, &codepoint_))
78 template <
typename Encoding,
typename Allocator>
113 template <
typename Encoding,
typename Allocator = CrtAllocator>
121 states_(allocator, 256), ranges_(allocator, 256), root_(kRegexInvalidState), stateCount_(), rangeCount_(),
122 anchorBegin_(), anchorEnd_()
132 return root_ != kRegexInvalidState;
145 static const unsigned kAnyCharacterClass = 0xFFFFFFFF;
146 static const unsigned kRangeCharacterClass = 0xFFFFFFFE;
147 static const unsigned kRangeNegationFlag = 0x80000000;
171 return states_.template Bottom<State>()[index];
174 const State& GetState(
SizeType index)
const {
176 return states_.template Bottom<State>()[index];
181 return ranges_.template Bottom<Range>()[index];
184 const Range& GetRange(
SizeType index)
const {
186 return ranges_.template Bottom<Range>()[index];
189 template <
typename InputStream>
190 void Parse(DecodedStream<InputStream, Encoding>& ds) {
192 Stack<Allocator> operandStack(&allocator, 256);
193 Stack<Allocator> operatorStack(&allocator, 256);
194 Stack<Allocator> atomCountStack(&allocator, 256);
196 *atomCountStack.template Push<unsigned>() = 0;
199 while (ds.Peek() != 0) {
200 switch (codepoint = ds.Take()) {
210 while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() < kAlternation)
211 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
213 *operatorStack.template Push<Operator>() = kAlternation;
214 *atomCountStack.template Top<unsigned>() = 0;
218 *operatorStack.template Push<Operator>() = kLeftParenthesis;
219 *atomCountStack.template Push<unsigned>() = 0;
223 while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() != kLeftParenthesis)
224 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
226 if (operatorStack.Empty())
228 operatorStack.template Pop<Operator>(1);
229 atomCountStack.template Pop<unsigned>(1);
230 ImplicitConcatenation(atomCountStack, operatorStack);
234 if (!Eval(operandStack, kZeroOrOne))
239 if (!Eval(operandStack, kZeroOrMore))
244 if (!Eval(operandStack, kOneOrMore))
251 if (!ParseUnsigned(ds, &n))
254 if (ds.Peek() ==
',') {
256 if (ds.Peek() ==
'}')
257 m = kInfinityQuantifier;
258 else if (!ParseUnsigned(ds, &m) || m < n)
264 if (!EvalQuantifier(operandStack, n, m) || ds.Peek() !=
'}')
271 PushOperand(operandStack, kAnyCharacterClass);
272 ImplicitConcatenation(atomCountStack, operatorStack);
278 if (!ParseRange(ds, &range))
280 SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, kRangeCharacterClass);
281 GetState(s).rangeStart = range;
282 *operandStack.template Push<Frag>() = Frag(s, s, s);
284 ImplicitConcatenation(atomCountStack, operatorStack);
288 if (!CharacterEscape(ds, &codepoint))
293 PushOperand(operandStack, codepoint);
294 ImplicitConcatenation(atomCountStack, operatorStack);
298 while (!operatorStack.Empty())
299 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
303 if (operandStack.GetSize() ==
sizeof(Frag)) {
304 Frag* e = operandStack.template Pop<Frag>(1);
305 Patch(e->out, NewState(kRegexInvalidState, kRegexInvalidState, 0));
308 #if RAPIDJSON_REGEX_VERBOSE 309 printf(
"root: %d\n", root_);
310 for (
SizeType i = 0; i < stateCount_ ; i++) {
311 State& s = GetState(i);
312 printf(
"[%2d] out: %2d out1: %2d c: '%c'\n", i, s.out, s.out1, (
char)s.codepoint);
320 State* s = states_.template Push<State>();
323 s->codepoint = codepoint;
324 s->rangeStart = kRegexInvalidRange;
325 return stateCount_++;
328 void PushOperand(Stack<Allocator>& operandStack,
unsigned codepoint) {
329 SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, codepoint);
330 *operandStack.template Push<Frag>() = Frag(s, s, s);
333 void ImplicitConcatenation(Stack<Allocator>& atomCountStack, Stack<Allocator>& operatorStack) {
334 if (*atomCountStack.template Top<unsigned>())
335 *operatorStack.template Push<Operator>() = kConcatenation;
336 (*atomCountStack.template Top<unsigned>())++;
341 while (GetState(l1).out != kRegexInvalidState)
342 l1 = GetState(l1).out;
343 GetState(l1).out = l2;
348 for (
SizeType next; l != kRegexInvalidState; l = next) {
349 next = GetState(l).out;
354 bool Eval(Stack<Allocator>& operandStack, Operator op) {
359 Frag e2 = *operandStack.template Pop<Frag>(1);
360 Frag e1 = *operandStack.template Pop<Frag>(1);
361 Patch(e1.out, e2.start);
362 *operandStack.template Push<Frag>() = Frag(e1.start, e2.out, Min(e1.minIndex, e2.minIndex));
367 if (operandStack.GetSize() >=
sizeof(Frag) * 2) {
368 Frag e2 = *operandStack.template Pop<Frag>(1);
369 Frag e1 = *operandStack.template Pop<Frag>(1);
370 SizeType s = NewState(e1.start, e2.start, 0);
371 *operandStack.template Push<Frag>() = Frag(s, Append(e1.out, e2.out), Min(e1.minIndex, e2.minIndex));
377 if (operandStack.GetSize() >=
sizeof(Frag)) {
378 Frag e = *operandStack.template Pop<Frag>(1);
379 SizeType s = NewState(kRegexInvalidState, e.start, 0);
380 *operandStack.template Push<Frag>() = Frag(s, Append(e.out, s), e.minIndex);
386 if (operandStack.GetSize() >=
sizeof(Frag)) {
387 Frag e = *operandStack.template Pop<Frag>(1);
388 SizeType s = NewState(kRegexInvalidState, e.start, 0);
390 *operandStack.template Push<Frag>() = Frag(s, s, e.minIndex);
397 if (operandStack.GetSize() >=
sizeof(Frag)) {
398 Frag e = *operandStack.template Pop<Frag>(1);
399 SizeType s = NewState(kRegexInvalidState, e.start, 0);
401 *operandStack.template Push<Frag>() = Frag(e.start, s, e.minIndex);
408 bool EvalQuantifier(Stack<Allocator>& operandStack,
unsigned n,
unsigned m) {
415 else if (m == kInfinityQuantifier)
416 Eval(operandStack, kZeroOrMore);
418 Eval(operandStack, kZeroOrOne);
419 for (
unsigned i = 0; i < m - 1; i++)
420 CloneTopOperand(operandStack);
421 for (
unsigned i = 0; i < m - 1; i++)
422 Eval(operandStack, kConcatenation);
427 for (
unsigned i = 0; i < n - 1; i++)
428 CloneTopOperand(operandStack);
430 if (m == kInfinityQuantifier)
431 Eval(operandStack, kOneOrMore);
433 CloneTopOperand(operandStack);
434 Eval(operandStack, kZeroOrOne);
435 for (
unsigned i = n; i < m - 1; i++)
436 CloneTopOperand(operandStack);
437 for (
unsigned i = n; i < m; i++)
438 Eval(operandStack, kConcatenation);
441 for (
unsigned i = 0; i < n - 1; i++)
442 Eval(operandStack, kConcatenation);
449 void CloneTopOperand(Stack<Allocator>& operandStack) {
450 const Frag src = *operandStack.template Top<Frag>();
452 State* s = states_.template Push<State>(
count);
453 memcpy(s, &GetState(src.minIndex),
count *
sizeof(State));
455 if (s[j].out != kRegexInvalidState)
457 if (s[j].out1 != kRegexInvalidState)
460 *operandStack.template Push<Frag>() = Frag(src.start +
count, src.out +
count, src.minIndex +
count);
461 stateCount_ +=
count;
464 template <
typename InputStream>
465 bool ParseUnsigned(DecodedStream<InputStream, Encoding>& ds,
unsigned* u) {
467 if (ds.Peek() <
'0' || ds.Peek() >
'9')
469 while (ds.Peek() >=
'0' && ds.Peek() <=
'9') {
470 if (r >= 429496729 && ds.Peek() >
'5')
472 r = r * 10 + (ds.Take() -
'0');
478 template <
typename InputStream>
479 bool ParseRange(DecodedStream<InputStream, Encoding>& ds,
SizeType* range) {
483 SizeType start = kRegexInvalidRange;
484 SizeType current = kRegexInvalidRange;
486 while ((codepoint = ds.Take()) != 0) {
489 if (codepoint ==
'^') {
497 if (start == kRegexInvalidRange)
502 GetRange(current).next = r;
505 GetRange(start).start |= kRangeNegationFlag;
510 if (ds.Peek() ==
'b') {
514 else if (!CharacterEscape(ds, &codepoint))
521 if (codepoint ==
'-') {
530 if (current != kRegexInvalidRange)
531 GetRange(current).next = r;
532 if (start == kRegexInvalidRange)
541 GetRange(current).end = codepoint;
549 SizeType NewRange(
unsigned codepoint) {
550 Range* r = ranges_.template Push<Range>();
551 r->start = r->end = codepoint;
552 r->next = kRegexInvalidRange;
553 return rangeCount_++;
556 template <
typename InputStream>
557 bool CharacterEscape(DecodedStream<InputStream, Encoding>& ds,
unsigned* escapedCodepoint) {
559 switch (codepoint = ds.Take()) {
574 *escapedCodepoint = codepoint;
return true;
575 case 'f': *escapedCodepoint = 0x000C;
return true;
576 case 'n': *escapedCodepoint = 0x000A;
return true;
577 case 'r': *escapedCodepoint = 0x000D;
return true;
578 case 't': *escapedCodepoint = 0x0009;
return true;
579 case 'v': *escapedCodepoint = 0x000B;
return true;
585 Stack<Allocator> states_;
586 Stack<Allocator> ranges_;
591 static const unsigned kInfinityQuantifier = ~0u;
598 template <
typename RegexType,
typename Allocator = CrtAllocator>
599 class GenericRegexSearch {
605 regex_(regex), allocator_(allocator), ownAllocator_(0),
606 state0_(allocator, 0), state1_(allocator, 0), stateSet_()
611 stateSet_ =
static_cast<unsigned*
>(allocator_->Malloc(GetStateSetSize()));
612 state0_.template Reserve<SizeType>(regex_.stateCount_);
613 state1_.template Reserve<SizeType>(regex_.stateCount_);
617 Allocator::Free(stateSet_);
621 template <
typename InputStream>
623 return SearchWithAnchoring(is,
true,
true);
631 template <
typename InputStream>
633 return SearchWithAnchoring(is, regex_.anchorBegin_, regex_.anchorEnd_);
642 typedef typename RegexType::State State;
643 typedef typename RegexType::Range Range;
645 template <
typename InputStream>
646 bool SearchWithAnchoring(InputStream& is,
bool anchorBegin,
bool anchorEnd) {
651 const size_t stateSetSize = GetStateSetSize();
652 std::memset(stateSet_, 0, stateSetSize);
654 bool matched = AddState(*current, regex_.root_);
656 while (!current->
Empty() && (codepoint = ds.Take()) != 0) {
657 std::memset(stateSet_, 0, stateSetSize);
660 for (
const SizeType* s = current->template Bottom<SizeType>(); s != current->template End<SizeType>(); ++s) {
661 const State& sr = regex_.GetState(*s);
662 if (sr.codepoint == codepoint ||
663 sr.codepoint == RegexType::kAnyCharacterClass ||
664 (sr.codepoint == RegexType::kRangeCharacterClass && MatchRange(sr.rangeStart, codepoint)))
666 matched = AddState(*next, sr.out) || matched;
667 if (!anchorEnd && matched)
671 AddState(*next, regex_.root_);
679 size_t GetStateSetSize()
const {
680 return (regex_.stateCount_ + 31) / 32 * 4;
684 bool AddState(Stack<Allocator>& l,
SizeType index) {
687 const State& s = regex_.GetState(index);
688 if (s.out1 != kRegexInvalidState) {
689 bool matched = AddState(l, s.out);
690 return AddState(l, s.out1) || matched;
692 else if (!(stateSet_[index >> 5] & (1u << (index & 31)))) {
693 stateSet_[index >> 5] |= (1u << (index & 31));
694 *l.template PushUnsafe<SizeType>() = index;
696 return s.out == kRegexInvalidState;
699 bool MatchRange(
SizeType rangeIndex,
unsigned codepoint)
const {
700 bool yes = (regex_.GetRange(rangeIndex).start & RegexType::kRangeNegationFlag) == 0;
701 while (rangeIndex != kRegexInvalidRange) {
702 const Range& r = regex_.GetRange(rangeIndex);
703 if (codepoint >= (r.start & ~RegexType::kRangeNegationFlag) && codepoint <= r.end)
710 const RegexType& regex_;
711 Allocator* allocator_;
712 Allocator* ownAllocator_;
713 Stack<Allocator> state0_;
714 Stack<Allocator> state1_;
728 #if defined(__clang__) || defined(_MSC_VER) 732 #endif // RAPIDJSON_INTERNAL_REGEX_H_ GenericRegex(const Ch *source, Allocator *allocator=0)
const CharType(& source)[N]
RAPIDJSON_NAMESPACE_BEGIN typedef unsigned SizeType
Size type (for string lengths, array sizes, etc.)
GenericRegexSearch< Regex > RegexSearch
bool Search(InputStream &is)
RegexType::EncodingType Encoding
#define RAPIDJSON_NAMESPACE_BEGIN
provide custom rapidjson namespace (opening expression)
DecodedStream(SourceStream &ss)
GenericRegex< UTF8<> > Regex
#define RAPIDJSON_NEW(TypeName)
! customization point for global new
mdb_size_t count(MDB_cursor *cur)
bool Match(InputStream &is)
#define RAPIDJSON_NAMESPACE_END
provide custom rapidjson namespace (closing expression)
void Swap(T &a, T &b) RAPIDJSON_NOEXCEPT
Custom swap() to avoid dependency on C++ <algorithm> header.
#define RAPIDJSON_DELETE(x)
! customization point for global delete
A type-unsafe stack for storing different types of data.
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
void * memcpy(void *a, const void *b, size_t c)
Regular expression engine with subset of ECMAscript grammar.
GenericRegexSearch(const RegexType ®ex, Allocator *allocator=0)
#define RAPIDJSON_ASSERT(x)
Assertion.