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