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