GenericRegex< Encoding, Allocator >

Regular expression engine with subset of ECMAscript grammar. More...

#include <regex.h>

Collaboration diagram for GenericRegex< Encoding, Allocator >:

Classes
struct	Frag
struct	Range
struct	State

Public Types
typedef Encoding	EncodingType
typedef Encoding::Ch	Ch

Public Member Functions
	GenericRegex (const Ch *source, Allocator *allocator=0)
	~GenericRegex ()
bool	IsValid () const

Private Types
enum	Operator {   kZeroOrOne, kZeroOrMore, kOneOrMore, kConcatenation,   kAlternation, kLeftParenthesis }

Private Member Functions
State &	GetState (SizeType index)
const State &	GetState (SizeType index) const
Range &	GetRange (SizeType index)
const Range &	GetRange (SizeType index) const
template<typename InputStream >
void	Parse (DecodedStream< InputStream, Encoding > &ds)
SizeType	NewState (SizeType out, SizeType out1, unsigned codepoint)
void	PushOperand (Stack< Allocator > &operandStack, unsigned codepoint)
void	ImplicitConcatenation (Stack< Allocator > &atomCountStack, Stack< Allocator > &operatorStack)
SizeType	Append (SizeType l1, SizeType l2)
void	Patch (SizeType l, SizeType s)
bool	Eval (Stack< Allocator > &operandStack, Operator op)
bool	EvalQuantifier (Stack< Allocator > &operandStack, unsigned n, unsigned m)
void	CloneTopOperand (Stack< Allocator > &operandStack)
template<typename InputStream >
bool	ParseUnsigned (DecodedStream< InputStream, Encoding > &ds, unsigned *u)
template<typename InputStream >
bool	ParseRange (DecodedStream< InputStream, Encoding > &ds, SizeType *range)
SizeType	NewRange (unsigned codepoint)
template<typename InputStream >
bool	CharacterEscape (DecodedStream< InputStream, Encoding > &ds, unsigned *escapedCodepoint)

Static Private Member Functions
static SizeType	Min (SizeType a, SizeType b)

Private Attributes
Allocator *	ownAllocator_
Allocator *	allocator_
Stack< Allocator >	states_
Stack< Allocator >	ranges_
SizeType	root_
SizeType	stateCount_
SizeType	rangeCount_
bool	anchorBegin_
bool	anchorEnd_

Static Private Attributes
static const unsigned	kAnyCharacterClass = 0xFFFFFFFF
	For '.'. More...
static const unsigned	kRangeCharacterClass = 0xFFFFFFFE
static const unsigned	kRangeNegationFlag = 0x80000000
static const unsigned	kInfinityQuantifier = ~0u

Friends
template<typename , typename >
class	GenericRegexSearch

Detailed Description

template<typename Encoding, typename Allocator = CrtAllocator>
class internal::GenericRegex< Encoding, Allocator >

Regular expression engine with subset of ECMAscript grammar.

Supported regular expression syntax:

• ab Concatenation
• a|b Alternation
• a? Zero or one
• a* Zero or more
• a+ One or more
• a{3} Exactly 3 times
• a{3,} At least 3 times
• a{3,5} 3 to 5 times
• (ab) Grouping
• ^a At the beginning
• a$ At the end
• . Any character
• [abc] Character classes
• [a-c] Character class range
• [a-z0-9_] Character class combination
• [^abc] Negated character classes
• [^a-c] Negated character class range
• [] Backspace (U+0008)
• \| \\ ... Escape characters
• \f Form feed (U+000C)
• \n Line feed (U+000A)
• \r Carriage return (U+000D)
• \t Tab (U+0009)
• \v Vertical tab (U+000B)

Note

This is a Thompson NFA engine, implemented with reference to Cox, Russ. "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby,...).", https://swtch.com/~rsc/regexp/regexp1.html

Definition at line 114 of file regex.h.

Member Typedef Documentation

Ch

typedef Encoding::Ch Ch

Definition at line 117 of file regex.h.

EncodingType

typedef Encoding EncodingType

Definition at line 116 of file regex.h.

Member Enumeration Documentation

Operator

enum Operator

private

Enumerator
kZeroOrOne
kZeroOrMore
kOneOrMore
kConcatenation
kAlternation
kLeftParenthesis

Definition at line 140 of file regex.h.

                  {
        kZeroOrOne,
        kZeroOrMore,
        kOneOrMore,
        kConcatenation,
        kAlternation,
        kLeftParenthesis
    };

Constructor & Destructor Documentation

GenericRegex()

GenericRegex ( const Ch *  source, Allocator *  allocator = 0  )

inline

Definition at line 120 of file regex.h.

                                                             : 
        ownAllocator_(allocator ? 0 : RAPIDJSON_NEW(Allocator)()), allocator_(allocator ? allocator : ownAllocator_), 
        states_(allocator_, 256), ranges_(allocator_, 256), root_(kRegexInvalidState), stateCount_(), rangeCount_(), 
        anchorBegin_(), anchorEnd_()
    {
        GenericStringStream<Encoding> ss(source);
        DecodedStream<GenericStringStream<Encoding>, Encoding> ds(ss);
        Parse(ds);
    }

~GenericRegex()

~GenericRegex ( )

inline

Definition at line 130 of file regex.h.

    {
        RAPIDJSON_DELETE(ownAllocator_);
    }

Member Function Documentation

Append()

SizeType Append ( SizeType  l1, SizeType  l2  )

inlineprivate

Definition at line 342 of file regex.h.

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

CharacterEscape()

bool CharacterEscape ( DecodedStream< InputStream, Encoding > &  ds, unsigned *  escapedCodepoint  )

inlineprivate

Definition at line 563 of file regex.h.

                                                                                               {
        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
        }
    }

Here is the call graph for this function:

CloneTopOperand()

void CloneTopOperand ( Stack< Allocator > &  operandStack )

inlineprivate

Definition at line 455 of file regex.h.

                                                         {
        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;
    }

Eval()

bool Eval ( Stack< Allocator > &  operandStack, Operator  op  )

inlineprivate

Definition at line 357 of file regex.h.

                                                           {
        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;

            case 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;

            default: 
                // syntax error (e.g. unclosed kLeftParenthesis)
                return false;
        }
    }

Here is the call graph for this function:

EvalQuantifier()

bool EvalQuantifier ( Stack< Allocator > &  operandStack, unsigned  n, unsigned  m  )

inlineprivate

Definition at line 414 of file regex.h.

                                                                                {
        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;
    }

Here is the call graph for this function:

GetRange() [1/2]

Range& GetRange ( SizeType  index )

inlineprivate

Definition at line 183 of file regex.h.

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

GetRange() [2/2]

const Range& GetRange ( SizeType  index ) const

inlineprivate

Definition at line 188 of file regex.h.

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

GetState() [1/2]

State& GetState ( SizeType  index )

inlineprivate

Definition at line 173 of file regex.h.

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

GetState() [2/2]

const State& GetState ( SizeType  index ) const

inlineprivate

Definition at line 178 of file regex.h.

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

ImplicitConcatenation()

void ImplicitConcatenation ( Stack< Allocator > &  atomCountStack, Stack< Allocator > &  operatorStack  )

inlineprivate

Definition at line 336 of file regex.h.

                                                                                                  {
        if (*atomCountStack.template Top<unsigned>())
            *operatorStack.template Push<Operator>() = kConcatenation;
        (*atomCountStack.template Top<unsigned>())++;
    }

IsValid()

bool IsValid ( ) const

inline

Definition at line 135 of file regex.h.

                         {
        return root_ != kRegexInvalidState;
    }

Here is the caller graph for this function:

Min()

static SizeType Min ( SizeType  a, SizeType  b  )

inlinestaticprivate

Definition at line 453 of file regex.h.

{ return a < b ? a : b; }

NewRange()

SizeType NewRange ( unsigned  codepoint )

inlineprivate

Definition at line 555 of file regex.h.

                                          {
        Range* r = ranges_.template Push<Range>();
        r->start = r->end = codepoint;
        r->next = kRegexInvalidRange;
        return rangeCount_++;
    }

NewState()

SizeType NewState ( SizeType  out, SizeType  out1, unsigned  codepoint  )

inlineprivate

Definition at line 322 of file regex.h.

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

Parse()

void Parse ( DecodedStream< InputStream, Encoding > &  ds )

inlineprivate

Definition at line 194 of file regex.h.

                                                         {
        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
        }
    }

Here is the call graph for this function:

ParseRange()

bool ParseRange ( DecodedStream< InputStream, Encoding > &  ds, SizeType *  range  )

inlineprivate

Definition at line 485 of file regex.h.

                                                                               {
        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;
    }

Here is the call graph for this function:

ParseUnsigned()

bool ParseUnsigned ( DecodedStream< InputStream, Encoding > &  ds, unsigned *  u  )

inlineprivate

Definition at line 471 of file regex.h.

                                                                              {
        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;
    }

Here is the call graph for this function:

Patch()

void Patch ( SizeType  l, SizeType  s  )

inlineprivate

Definition at line 350 of file regex.h.

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

PushOperand()

void PushOperand ( Stack< Allocator > &  operandStack, unsigned  codepoint  )

inlineprivate

Definition at line 331 of file regex.h.

                                                                         {
        SizeType s = NewState(kRegexInvalidState, kRegexInvalidState, codepoint);
        *operandStack.template Push<Frag>() = Frag(s, s, s);
    }

Friends And Related Function Documentation

GenericRegexSearch

friend class GenericRegexSearch

friend

Definition at line 118 of file regex.h.

Member Data Documentation

allocator_

Allocator* allocator_

private

Definition at line 592 of file regex.h.

anchorBegin_

bool anchorBegin_

private

Definition at line 602 of file regex.h.

anchorEnd_

bool anchorEnd_

private

Definition at line 603 of file regex.h.

kAnyCharacterClass

const unsigned kAnyCharacterClass = 0xFFFFFFFF

staticprivate

For '.'.

Definition at line 149 of file regex.h.

kInfinityQuantifier

const unsigned kInfinityQuantifier = ~0u

staticprivate

Definition at line 599 of file regex.h.

kRangeCharacterClass

const unsigned kRangeCharacterClass = 0xFFFFFFFE

staticprivate

Definition at line 150 of file regex.h.

kRangeNegationFlag

const unsigned kRangeNegationFlag = 0x80000000

staticprivate

Definition at line 151 of file regex.h.

ownAllocator_

Allocator* ownAllocator_

private

Definition at line 591 of file regex.h.

rangeCount_

SizeType rangeCount_

private

Definition at line 597 of file regex.h.

ranges_

Stack<Allocator> ranges_

private

Definition at line 594 of file regex.h.

root_

SizeType root_

private

Definition at line 595 of file regex.h.

stateCount_

SizeType stateCount_

private

Definition at line 596 of file regex.h.

states_

Stack<Allocator> states_

private

Definition at line 593 of file regex.h.

---

The documentation for this class was generated from the following file:

• rapidjson/internal/regex.h