regex.h

Go to the documentation of this file.

// Tencent is pleased to support the open source community by making RapidJSON available.
// 
// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
//
// Licensed under the MIT License (the "License"); you may not use this file except
// in compliance with the License. You may obtain a copy of the License at
//
// http://opensource.org/licenses/MIT
//
// Unless required by applicable law or agreed to in writing, software distributed 
// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
// CONDITIONS OF ANY KIND, either express or implied. See the License for the 
// specific language governing permissions and limitations under the License.

#ifndef RAPIDJSON_INTERNAL_REGEX_H_
#define RAPIDJSON_INTERNAL_REGEX_H_

#include "../allocators.h"
#include "../stream.h"
#include "stack.h"

#ifdef __clang__
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(padded)
RAPIDJSON_DIAG_OFF(switch-enum)
RAPIDJSON_DIAG_OFF(implicit-fallthrough)
#endif

#ifdef __GNUC__
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(effc++)
#endif

#ifdef _MSC_VER
RAPIDJSON_DIAG_PUSH
RAPIDJSON_DIAG_OFF(4512) // assignment operator could not be generated
#endif

#ifndef RAPIDJSON_REGEX_VERBOSE
#define RAPIDJSON_REGEX_VERBOSE 0
#endif

RAPIDJSON_NAMESPACE_BEGIN
namespace internal {

// GenericRegex

static const SizeType kRegexInvalidState = ~SizeType(0); 
static const SizeType kRegexInvalidRange = ~SizeType(0);


template <typename Encoding, typename Allocator = CrtAllocator>
class GenericRegex {
public:
 typedef typename Encoding::Ch Ch;

 GenericRegex(const Ch* source, Allocator* allocator = 0) : 
 states_(allocator, 256), ranges_(allocator, 256), root_(kRegexInvalidState), stateCount_(), rangeCount_(), 
 stateSet_(), state0_(allocator, 0), state1_(allocator, 0), anchorBegin_(), anchorEnd_()
 {
 GenericStringStream<Encoding> ss(source);
 DecodedStream<GenericStringStream<Encoding> > ds(ss);
 Parse(ds);
 }

 ~GenericRegex() {
 Allocator::Free(stateSet_);
 }

 bool IsValid() const {
 return root_ != kRegexInvalidState;
 }

 template <typename InputStream>
 bool Match(InputStream& is) const {
 return SearchWithAnchoring(is, true, true);
 }

 bool Match(const Ch* s) const {
 GenericStringStream<Encoding> is(s);
 return Match(is);
 }

 template <typename InputStream>
 bool Search(InputStream& is) const {
 return SearchWithAnchoring(is, anchorBegin_, anchorEnd_);
 }

 bool Search(const Ch* s) const {
 GenericStringStream<Encoding> is(s);
 return Search(is);
 }

private:
 enum Operator {
 kZeroOrOne,
 kZeroOrMore,
 kOneOrMore,
 kConcatenation,
 kAlternation,
 kLeftParenthesis
 };

 static const unsigned kAnyCharacterClass = 0xFFFFFFFF; 
 static const unsigned kRangeCharacterClass = 0xFFFFFFFE;
 static const unsigned kRangeNegationFlag = 0x80000000;

 struct Range {
 unsigned start; // 
 unsigned end;
 SizeType next;
 };

 struct State {
 SizeType out; 
 SizeType out1; 
 SizeType rangeStart;
 unsigned codepoint;
 };

 struct Frag {
 Frag(SizeType s, SizeType o, SizeType m) : start(s), out(o), minIndex(m) {}
 SizeType start;
 SizeType out; 
 SizeType minIndex;
 };

 template <typename SourceStream>
 class DecodedStream {
 public:
 DecodedStream(SourceStream& ss) : ss_(ss), codepoint_() { Decode(); }
 unsigned Peek() { return codepoint_; }
 unsigned Take() {
 unsigned c = codepoint_;
 if (c) // No further decoding when '\0'
 Decode();
 return c;
 }

 private:
 void Decode() {
 if (!Encoding::Decode(ss_, &codepoint_))
 codepoint_ = 0;
 }

 SourceStream& ss_;
 unsigned codepoint_;
 };

 State& GetState(SizeType index) {
 RAPIDJSON_ASSERT(index < stateCount_);
 return states_.template Bottom<State>()[index];
 }

 const State& GetState(SizeType index) const {
 RAPIDJSON_ASSERT(index < stateCount_);
 return states_.template Bottom<State>()[index];
 }

 Range& GetRange(SizeType index) {
 RAPIDJSON_ASSERT(index < rangeCount_);
 return ranges_.template Bottom<Range>()[index];
 }

 const Range& GetRange(SizeType index) const {
 RAPIDJSON_ASSERT(index < rangeCount_);
 return ranges_.template Bottom<Range>()[index];
 }

 template <typename InputStream>
 void Parse(DecodedStream<InputStream>& ds) {
 Allocator allocator;
 Stack<Allocator> operandStack(&allocator, 256); // Frag
 Stack<Allocator> operatorStack(&allocator, 256); // Operator
 Stack<Allocator> atomCountStack(&allocator, 256); // unsigned (Atom per parenthesis)

 *atomCountStack.template Push<unsigned>() = 0;

 unsigned codepoint;
 while (ds.Peek() != 0) {
 switch (codepoint = ds.Take()) {
 case '^':
 anchorBegin_ = true;
 break;

 case '$':
 anchorEnd_ = true;
 break;

 case '|':
 while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() < kAlternation)
 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
 return;
 *operatorStack.template Push<Operator>() = kAlternation;
 *atomCountStack.template Top<unsigned>() = 0;
 break;

 case '(':
 *operatorStack.template Push<Operator>() = kLeftParenthesis;
 *atomCountStack.template Push<unsigned>() = 0;
 break;

 case ')':
 while (!operatorStack.Empty() && *operatorStack.template Top<Operator>() != kLeftParenthesis)
 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
 return;
 if (operatorStack.Empty())
 return;
 operatorStack.template Pop<Operator>(1);
 atomCountStack.template Pop<unsigned>(1);
 ImplicitConcatenation(atomCountStack, operatorStack);
 break;

 case '?':
 if (!Eval(operandStack, kZeroOrOne))
 return;
 break;

 case '*':
 if (!Eval(operandStack, kZeroOrMore))
 return;
 break;

 case '+':
 if (!Eval(operandStack, kOneOrMore))
 return;
 break;

 case '{':
 {
 unsigned n, m;
 if (!ParseUnsigned(ds, &n))
 return;

 if (ds.Peek() == ',') {
 ds.Take();
 if (ds.Peek() == '}')
 m = kInfinityQuantifier;
 else if (!ParseUnsigned(ds, &m) || m < n)
 return;
 }
 else
 m = n;

 if (!EvalQuantifier(operandStack, n, m) || ds.Peek() != '}')
 return;
 ds.Take();
 }
 break;

 case '.':
 PushOperand(operandStack, kAnyCharacterClass);
 ImplicitConcatenation(atomCountStack, operatorStack);
 break;

 case '[':
 {
 SizeType range;
 if (!ParseRange(ds, &range))
 return;
 SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, kRangeCharacterClass);
 GetState(s).rangeStart = range;
 *operandStack.template Push<Frag>() = Frag(s, s, s);
 }
 ImplicitConcatenation(atomCountStack, operatorStack);
 break;

 case '\\': // Escape character
 if (!CharacterEscape(ds, &codepoint))
 return; // Unsupported escape character
 // fall through to default

 default: // Pattern character
 PushOperand(operandStack, codepoint);
 ImplicitConcatenation(atomCountStack, operatorStack);
 }
 }

 while (!operatorStack.Empty())
 if (!Eval(operandStack, *operatorStack.template Pop<Operator>(1)))
 return;

 // Link the operand to matching state.
 if (operandStack.GetSize() == sizeof(Frag)) {
 Frag* e = operandStack.template Pop<Frag>(1);
 Patch(e->out, NewState(kRegexInvalidState, kRegexInvalidState, 0));
 root_ = e->start;

#if RAPIDJSON_REGEX_VERBOSE
 printf("root: %d\n", root_);
 for (SizeType i = 0; i < stateCount_ ; i++) {
 State& s = GetState(i);
 printf("[%2d] out: %2d out1: %2d c: '%c'\n", i, s.out, s.out1, (char)s.codepoint);
 }
 printf("\n");
#endif
 }

 // Preallocate buffer for SearchWithAnchoring()
 RAPIDJSON_ASSERT(stateSet_ == 0);
 if (stateCount_ > 0) {
 stateSet_ = static_cast<unsigned*>(states_.GetAllocator().Malloc(GetStateSetSize()));
 state0_.template Reserve<SizeType>(stateCount_);
 state1_.template Reserve<SizeType>(stateCount_);
 }
 }

 SizeType NewState(SizeType out, SizeType out1, unsigned codepoint) {
 State* s = states_.template Push<State>();
 s->out = out;
 s->out1 = out1;
 s->codepoint = codepoint;
 s->rangeStart = kRegexInvalidRange;
 return stateCount_++;
 }

 void PushOperand(Stack<Allocator>& operandStack, unsigned codepoint) {
 SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, codepoint);
 *operandStack.template Push<Frag>() = Frag(s, s, s);
 }

 void ImplicitConcatenation(Stack<Allocator>& atomCountStack, Stack<Allocator>& operatorStack) {
 if (*atomCountStack.template Top<unsigned>())
 *operatorStack.template Push<Operator>() = kConcatenation;
 (*atomCountStack.template Top<unsigned>())++;
 }

 SizeType Append(SizeType l1, SizeType l2) {
 SizeType old = l1;
 while (GetState(l1).out != kRegexInvalidState)
 l1 = GetState(l1).out;
 GetState(l1).out = l2;
 return old;
 }

 void Patch(SizeType l, SizeType s) {
 for (SizeType next; l != kRegexInvalidState; l = next) {
 next = GetState(l).out;
 GetState(l).out = s;
 }
 }

 bool Eval(Stack<Allocator>& operandStack, Operator op) {
 switch (op) {
 case kConcatenation:
 RAPIDJSON_ASSERT(operandStack.GetSize() >= sizeof(Frag) * 2);
 {
 Frag e2 = *operandStack.template Pop<Frag>(1);
 Frag e1 = *operandStack.template Pop<Frag>(1);
 Patch(e1.out, e2.start);
 *operandStack.template Push<Frag>() = Frag(e1.start, e2.out, Min(e1.minIndex, e2.minIndex));
 }
 return true;

 case kAlternation:
 if (operandStack.GetSize() >= sizeof(Frag) * 2) {
 Frag e2 = *operandStack.template Pop<Frag>(1);
 Frag e1 = *operandStack.template Pop<Frag>(1);
 SizeType s = NewState(e1.start, e2.start, 0);
 *operandStack.template Push<Frag>() = Frag(s, Append(e1.out, e2.out), Min(e1.minIndex, e2.minIndex));
 return true;
 }
 return false;

 case kZeroOrOne:
 if (operandStack.GetSize() >= sizeof(Frag)) {
 Frag e = *operandStack.template Pop<Frag>(1);
 SizeType s = NewState(kRegexInvalidState, e.start, 0);
 *operandStack.template Push<Frag>() = Frag(s, Append(e.out, s), e.minIndex);
 return true;
 }
 return false;

 case kZeroOrMore:
 if (operandStack.GetSize() >= sizeof(Frag)) {
 Frag e = *operandStack.template Pop<Frag>(1);
 SizeType s = NewState(kRegexInvalidState, e.start, 0);
 Patch(e.out, s);
 *operandStack.template Push<Frag>() = Frag(s, s, e.minIndex);
 return true;
 }
 return false;

 default: 
 RAPIDJSON_ASSERT(op == kOneOrMore);
 if (operandStack.GetSize() >= sizeof(Frag)) {
 Frag e = *operandStack.template Pop<Frag>(1);
 SizeType s = NewState(kRegexInvalidState, e.start, 0);
 Patch(e.out, s);
 *operandStack.template Push<Frag>() = Frag(e.start, s, e.minIndex);
 return true;
 }
 return false;
 }
 }

 bool EvalQuantifier(Stack<Allocator>& operandStack, unsigned n, unsigned m) {
 RAPIDJSON_ASSERT(n <= m);
 RAPIDJSON_ASSERT(operandStack.GetSize() >= sizeof(Frag));

 if (n == 0) {
 if (m == 0) // a{0} not support
 return false;
 else if (m == kInfinityQuantifier)
 Eval(operandStack, kZeroOrMore); // a{0,} -> a*
 else {
 Eval(operandStack, kZeroOrOne); // a{0,5} -> a?
 for (unsigned i = 0; i < m - 1; i++)
 CloneTopOperand(operandStack); // a{0,5} -> a? a? a? a? a?
 for (unsigned i = 0; i < m - 1; i++)
 Eval(operandStack, kConcatenation); // a{0,5} -> a?a?a?a?a?
 }
 return true;
 }

 for (unsigned i = 0; i < n - 1; i++) // a{3} -> a a a
 CloneTopOperand(operandStack);

 if (m == kInfinityQuantifier)
 Eval(operandStack, kOneOrMore); // a{3,} -> a a a+
 else if (m > n) {
 CloneTopOperand(operandStack); // a{3,5} -> a a a a
 Eval(operandStack, kZeroOrOne); // a{3,5} -> a a a a?
 for (unsigned i = n; i < m - 1; i++)
 CloneTopOperand(operandStack); // a{3,5} -> a a a a? a?
 for (unsigned i = n; i < m; i++)
 Eval(operandStack, kConcatenation); // a{3,5} -> a a aa?a?
 }

 for (unsigned i = 0; i < n - 1; i++)
 Eval(operandStack, kConcatenation); // a{3} -> aaa, a{3,} -> aaa+, a{3.5} -> aaaa?a?

 return true;
 }

 static SizeType Min(SizeType a, SizeType b) { return a < b ? a : b; }

 void CloneTopOperand(Stack<Allocator>& operandStack) {
 const Frag src = *operandStack.template Top<Frag>(); // Copy constructor to prevent invalidation
 SizeType count = stateCount_ - src.minIndex; // Assumes top operand contains states in [src->minIndex, stateCount_)
 State* s = states_.template Push<State>(count);
 memcpy(s, &GetState(src.minIndex), count * sizeof(State));
 for (SizeType j = 0; j < count; j++) {
 if (s[j].out != kRegexInvalidState)
 s[j].out += count;
 if (s[j].out1 != kRegexInvalidState)
 s[j].out1 += count;
 }
 *operandStack.template Push<Frag>() = Frag(src.start + count, src.out + count, src.minIndex + count);
 stateCount_ += count;
 }

 template <typename InputStream>
 bool ParseUnsigned(DecodedStream<InputStream>& ds, unsigned* u) {
 unsigned r = 0;
 if (ds.Peek() < '0' || ds.Peek() > '9')
 return false;
 while (ds.Peek() >= '0' && ds.Peek() <= '9') {
 if (r >= 429496729 && ds.Peek() > '5') // 2^32 - 1 = 4294967295
 return false; // overflow
 r = r * 10 + (ds.Take() - '0');
 }
 *u = r;
 return true;
 }

 template <typename InputStream>
 bool ParseRange(DecodedStream<InputStream>& ds, SizeType* range) {
 bool isBegin = true;
 bool negate = false;
 int step = 0;
 SizeType start = kRegexInvalidRange;
 SizeType current = kRegexInvalidRange;
 unsigned codepoint;
 while ((codepoint = ds.Take()) != 0) {
 if (isBegin) {
 isBegin = false;
 if (codepoint == '^') {
 negate = true;
 continue;
 }
 }

 switch (codepoint) {
 case ']':
 if (start == kRegexInvalidRange)
 return false; // Error: nothing inside []
 if (step == 2) { // Add trailing '-'
 SizeType r = NewRange('-');
 RAPIDJSON_ASSERT(current != kRegexInvalidRange);
 GetRange(current).next = r;
 }
 if (negate)
 GetRange(start).start |= kRangeNegationFlag;
 *range = start;
 return true;

 case '\\':
 if (ds.Peek() == 'b') {
 ds.Take();
 codepoint = 0x0008; // Escape backspace character
 }
 else if (!CharacterEscape(ds, &codepoint))
 return false;
 // fall through to default

 default:
 switch (step) {
 case 1:
 if (codepoint == '-') {
 step++;
 break;
 }
 // fall through to step 0 for other characters

 case 0:
 {
 SizeType r = NewRange(codepoint);
 if (current != kRegexInvalidRange)
 GetRange(current).next = r;
 if (start == kRegexInvalidRange)
 start = r;
 current = r;
 }
 step = 1;
 break;

 default:
 RAPIDJSON_ASSERT(step == 2);
 GetRange(current).end = codepoint;
 step = 0;
 }
 }
 }
 return false;
 }
 
 SizeType NewRange(unsigned codepoint) {
 Range* r = ranges_.template Push<Range>();
 r->start = r->end = codepoint;
 r->next = kRegexInvalidRange;
 return rangeCount_++;
 }

 template <typename InputStream>
 bool CharacterEscape(DecodedStream<InputStream>& ds, unsigned* escapedCodepoint) {
 unsigned codepoint;
 switch (codepoint = ds.Take()) {
 case '^':
 case '$':
 case '|':
 case '(':
 case ')':
 case '?':
 case '*':
 case '+':
 case '.':
 case '[':
 case ']':
 case '{':
 case '}':
 case '\\':
 *escapedCodepoint = codepoint; return true;
 case 'f': *escapedCodepoint = 0x000C; return true;
 case 'n': *escapedCodepoint = 0x000A; return true;
 case 'r': *escapedCodepoint = 0x000D; return true;
 case 't': *escapedCodepoint = 0x0009; return true;
 case 'v': *escapedCodepoint = 0x000B; return true;
 default:
 return false; // Unsupported escape character
 }
 }

 template <typename InputStream>
 bool SearchWithAnchoring(InputStream& is, bool anchorBegin, bool anchorEnd) const {
 RAPIDJSON_ASSERT(IsValid());
 DecodedStream<InputStream> ds(is);

 state0_.Clear();
 Stack<Allocator> *current = &state0_, *next = &state1_;
 const size_t stateSetSize = GetStateSetSize();
 std::memset(stateSet_, 0, stateSetSize);

 bool matched = AddState(*current, root_);
 unsigned codepoint;
 while (!current->Empty() && (codepoint = ds.Take()) != 0) {
 std::memset(stateSet_, 0, stateSetSize);
 next->Clear();
 matched = false;
 for (const SizeType* s = current->template Bottom<SizeType>(); s != current->template End<SizeType>(); ++s) {
 const State& sr = GetState(*s);
 if (sr.codepoint == codepoint ||
 sr.codepoint == kAnyCharacterClass || 
 (sr.codepoint == kRangeCharacterClass && MatchRange(sr.rangeStart, codepoint)))
 {
 matched = AddState(*next, sr.out) || matched;
 if (!anchorEnd && matched)
 return true;
 }
 if (!anchorBegin)
 AddState(*next, root_);
 }
 internal::Swap(current, next);
 }

 return matched;
 }

 size_t GetStateSetSize() const {
 return (stateCount_ + 31) / 32 * 4;
 }

 // Return whether the added states is a match state
 bool AddState(Stack<Allocator>& l, SizeType index) const {
 RAPIDJSON_ASSERT(index != kRegexInvalidState);

 const State& s = GetState(index);
 if (s.out1 != kRegexInvalidState) { // Split
 bool matched = AddState(l, s.out);
 return AddState(l, s.out1) || matched;
 }
 else if (!(stateSet_[index >> 5] & (1 << (index & 31)))) {
 stateSet_[index >> 5] |= (1 << (index & 31));
 *l.template PushUnsafe<SizeType>() = index;
 }
 return s.out == kRegexInvalidState; // by using PushUnsafe() above, we can ensure s is not validated due to reallocation.
 }

 bool MatchRange(SizeType rangeIndex, unsigned codepoint) const {
 bool yes = (GetRange(rangeIndex).start & kRangeNegationFlag) == 0;
 while (rangeIndex != kRegexInvalidRange) {
 const Range& r = GetRange(rangeIndex);
 if (codepoint >= (r.start & ~kRangeNegationFlag) && codepoint <= r.end)
 return yes;
 rangeIndex = r.next;
 }
 return !yes;
 }

 Stack<Allocator> states_;
 Stack<Allocator> ranges_;
 SizeType root_;
 SizeType stateCount_;
 SizeType rangeCount_;

 static const unsigned kInfinityQuantifier = ~0u;

 // For SearchWithAnchoring()
 uint32_t* stateSet_; // allocated by states_.GetAllocator()
 mutable Stack<Allocator> state0_;
 mutable Stack<Allocator> state1_;
 bool anchorBegin_;
 bool anchorEnd_;
};

typedef GenericRegex<UTF8<> > Regex;

} // namespace internal
RAPIDJSON_NAMESPACE_END

#ifdef __clang__
RAPIDJSON_DIAG_POP
#endif

#ifdef _MSC_VER
RAPIDJSON_DIAG_POP
#endif

#endif // RAPIDJSON_INTERNAL_REGEX_H_