dart::RegExpQuantifier Class Reference

#include <regexp_ast.h>

Inheritance diagram for dart::RegExpQuantifier:

Public Types
enum	QuantifierType { GREEDY , NON_GREEDY , POSSESSIVE }

Public Member Functions
	RegExpQuantifier (intptr_t min, intptr_t max, QuantifierType type, RegExpTree *body)
virtual void *	Accept (RegExpVisitor *visitor, void *data)
virtual RegExpNode *	ToNode (RegExpCompiler *compiler, RegExpNode *on_success)
virtual RegExpQuantifier *	AsQuantifier ()
virtual Interval	CaptureRegisters () const
virtual bool	IsQuantifier () const
virtual intptr_t	min_match () const
virtual intptr_t	max_match () const
intptr_t	min () const
intptr_t	max () const
bool	is_possessive () const
bool	is_non_greedy () const
bool	is_greedy () const
RegExpTree *	body () const
Public Member Functions inherited from dart::RegExpTree
virtual	~RegExpTree ()
virtual void *	Accept (RegExpVisitor *visitor, void *data)=0
virtual RegExpNode *	ToNode (RegExpCompiler *compiler, RegExpNode *on_success)=0
virtual bool	IsTextElement () const
virtual bool	IsAnchoredAtStart () const
virtual bool	IsAnchoredAtEnd () const
virtual intptr_t	min_match () const =0
virtual intptr_t	max_match () const =0
virtual Interval	CaptureRegisters () const
virtual void	AppendToText (RegExpText *text)
void	Print ()
Public Member Functions inherited from dart::ZoneAllocated
	ZoneAllocated ()
void *	operator new (size_t size)
void *	operator new (size_t size, Zone *zone)
void	operator delete (void *pointer)

Static Public Member Functions
static RegExpNode *	ToNode (intptr_t min, intptr_t max, bool is_greedy, RegExpTree *body, RegExpCompiler *compiler, RegExpNode *on_success, bool not_at_start=false)

Additional Inherited Members
Static Public Attributes inherited from dart::RegExpTree
static constexpr intptr_t	kInfinity = kMaxInt32

Detailed Description

Definition at line 263 of file regexp_ast.h.

Member Enumeration Documentation

QuantifierType

enum dart::RegExpQuantifier::QuantifierType

Enumerator
GREEDY
NON_GREEDY
POSSESSIVE

Definition at line 265 of file regexp_ast.h.

{ GREEDY, NON_GREEDY, POSSESSIVE };

Constructor & Destructor Documentation

RegExpQuantifier()

dart::RegExpQuantifier::RegExpQuantifier ( intptr_t  min, intptr_t  max, QuantifierType  type, RegExpTree *  body  )

inline

Definition at line 266 of file regexp_ast.h.

      : body_(body),
        min_(min),
        max_(max),
        min_match_(min * body->min_match()),
        quantifier_type_(type) {
    if (max > 0 && body->max_match() > kInfinity / max) {
      max_match_ = kInfinity;
    } else {
      max_match_ = max * body->max_match();
    }
  }

Member Function Documentation

Accept()

virtual void * dart::RegExpQuantifier::Accept ( RegExpVisitor *  visitor, void *  data  )

virtual

Implements dart::RegExpTree.

AsQuantifier()

virtual RegExpQuantifier * dart::RegExpQuantifier::AsQuantifier ( )

virtual

body()

RegExpTree * dart::RegExpQuantifier::body ( ) const

inline

Definition at line 300 of file regexp_ast.h.

{ return body_; }

CaptureRegisters()

Interval dart::RegExpQuantifier::CaptureRegisters ( ) const

virtual

Reimplemented from dart::RegExpTree.

Definition at line 63 of file regexp_ast.cc.

                                                  {
  return body()->CaptureRegisters();
}

is_greedy()

bool dart::RegExpQuantifier::is_greedy ( ) const

inline

Definition at line 299 of file regexp_ast.h.

{ return quantifier_type_ == GREEDY; }

is_non_greedy()

bool dart::RegExpQuantifier::is_non_greedy ( ) const

inline

Definition at line 298 of file regexp_ast.h.

{ return quantifier_type_ == NON_GREEDY; }

is_possessive()

bool dart::RegExpQuantifier::is_possessive ( ) const

inline

Definition at line 297 of file regexp_ast.h.

{ return quantifier_type_ == POSSESSIVE; }

IsQuantifier()

virtual bool dart::RegExpQuantifier::IsQuantifier ( ) const

virtual

max()

intptr_t dart::RegExpQuantifier::max ( ) const

inline

Definition at line 296 of file regexp_ast.h.

{ return max_; }

max_match()

virtual intptr_t dart::RegExpQuantifier::max_match ( ) const

inlinevirtual

Implements dart::RegExpTree.

Definition at line 294 of file regexp_ast.h.

{ return max_match_; }

min()

intptr_t dart::RegExpQuantifier::min ( ) const

inline

Definition at line 295 of file regexp_ast.h.

{ return min_; }

min_match()

virtual intptr_t dart::RegExpQuantifier::min_match ( ) const

inlinevirtual

Implements dart::RegExpTree.

Definition at line 293 of file regexp_ast.h.

{ return min_match_; }

ToNode() [1/2]

RegExpNode * dart::RegExpQuantifier::ToNode ( intptr_t  min, intptr_t  max, bool  is_greedy, RegExpTree *  body, RegExpCompiler *  compiler, RegExpNode *  on_success, bool  not_at_start = false  )

static

Definition at line 4258 of file regexp.cc.

                                                        {
  // x{f, t} becomes this:
  //
  //             (r++)<-.
  //               |     `
  //               |     (x)
  //               v     ^
  //      (r=0)-->(?)---/ [if r < t]
  //               |
  //   [if r >= f] \----> ...
  //
 
  // 15.10.2.5 RepeatMatcher algorithm.
  // The parser has already eliminated the case where max is 0.  In the case
  // where max_match is zero the parser has removed the quantifier if min was
  // > 0 and removed the atom if min was 0.  See AddQuantifierToAtom.
 
  // If we know that we cannot match zero length then things are a little
  // simpler since we don't need to make the special zero length match check
  // from step 2.1.  If the min and max are small we can unroll a little in
  // this case.
  // Unroll (foo)+ and (foo){3,}
  const intptr_t kMaxUnrolledMinMatches = 3;
  // Unroll (foo)? and (foo){x,3}
  const intptr_t kMaxUnrolledMaxMatches = 3;
  if (max == 0) return on_success;  // This can happen due to recursion.
  bool body_can_be_empty = (body->min_match() == 0);
  intptr_t body_start_reg = RegExpCompiler::kNoRegister;
  Interval capture_registers = body->CaptureRegisters();
  bool needs_capture_clearing = !capture_registers.is_empty();
  Zone* zone = compiler->zone();
 
  if (body_can_be_empty) {
    body_start_reg = compiler->AllocateRegister();
  } else if (kRegexpOptimization && !needs_capture_clearing) {
    // Only unroll if there are no captures and the body can't be
    // empty.
    {
      RegExpExpansionLimiter limiter(compiler, min + ((max != min) ? 1 : 0));
      if (min > 0 && min <= kMaxUnrolledMinMatches && limiter.ok_to_expand()) {
        intptr_t new_max = (max == kInfinity) ? max : max - min;
        // Recurse once to get the loop or optional matches after the fixed
        // ones.
        RegExpNode* answer =
            ToNode(0, new_max, is_greedy, body, compiler, on_success, true);
        // Unroll the forced matches from 0 to min.  This can cause chains of
        // TextNodes (which the parser does not generate).  These should be
        // combined if it turns out they hinder good code generation.
        for (intptr_t i = 0; i < min; i++) {
          answer = body->ToNode(compiler, answer);
        }
        return answer;
      }
    }
    if (max <= kMaxUnrolledMaxMatches && min == 0) {
      ASSERT(max > 0);  // Due to the 'if' above.
      RegExpExpansionLimiter limiter(compiler, max);
      if (limiter.ok_to_expand()) {
        // Unroll the optional matches up to max.
        RegExpNode* answer = on_success;
        for (intptr_t i = 0; i < max; i++) {
          ChoiceNode* alternation = new (zone) ChoiceNode(2, zone);
          if (is_greedy) {
            alternation->AddAlternative(
                GuardedAlternative(body->ToNode(compiler, answer)));
            alternation->AddAlternative(GuardedAlternative(on_success));
          } else {
            alternation->AddAlternative(GuardedAlternative(on_success));
            alternation->AddAlternative(
                GuardedAlternative(body->ToNode(compiler, answer)));
          }
          answer = alternation;
          if (not_at_start && !compiler->read_backward()) {
            alternation->set_not_at_start();
          }
        }
        return answer;
      }
    }
  }
  bool has_min = min > 0;
  bool has_max = max < RegExpTree::kInfinity;
  bool needs_counter = has_min || has_max;
  intptr_t reg_ctr = needs_counter ? compiler->AllocateRegister()
                                   : RegExpCompiler::kNoRegister;
  LoopChoiceNode* center = new (zone)
      LoopChoiceNode(body->min_match() == 0, compiler->read_backward(), zone);
  if (not_at_start && !compiler->read_backward()) center->set_not_at_start();
  RegExpNode* loop_return =
      needs_counter ? static_cast<RegExpNode*>(
                          ActionNode::IncrementRegister(reg_ctr, center))
                    : static_cast<RegExpNode*>(center);
  if (body_can_be_empty) {
    // If the body can be empty we need to check if it was and then
    // backtrack.
    loop_return =
        ActionNode::EmptyMatchCheck(body_start_reg, reg_ctr, min, loop_return);
  }
  RegExpNode* body_node = body->ToNode(compiler, loop_return);
  if (body_can_be_empty) {
    // If the body can be empty we need to store the start position
    // so we can bail out if it was empty.
    body_node = ActionNode::StorePosition(body_start_reg, false, body_node);
  }
  if (needs_capture_clearing) {
    // Before entering the body of this loop we need to clear captures.
    body_node = ActionNode::ClearCaptures(capture_registers, body_node);
  }
  GuardedAlternative body_alt(body_node);
  if (has_max) {
    Guard* body_guard = new (zone) Guard(reg_ctr, Guard::LT, max);
    body_alt.AddGuard(body_guard, zone);
  }
  GuardedAlternative rest_alt(on_success);
  if (has_min) {
    Guard* rest_guard = new (zone) Guard(reg_ctr, Guard::GEQ, min);
    rest_alt.AddGuard(rest_guard, zone);
  }
  if (is_greedy) {
    center->AddLoopAlternative(body_alt);
    center->AddContinueAlternative(rest_alt);
  } else {
    center->AddContinueAlternative(rest_alt);
    center->AddLoopAlternative(body_alt);
  }
  if (needs_counter) {
    return ActionNode::SetRegister(reg_ctr, 0, center);
  } else {
    return center;
  }
}

ToNode() [2/2]

RegExpNode * dart::RegExpQuantifier::ToNode ( RegExpCompiler *  compiler, RegExpNode *  on_success  )

virtual

Implements dart::RegExpTree.

Definition at line 4216 of file regexp.cc.

                                                             {
  return ToNode(min(), max(), is_greedy(), body(), compiler, on_success);
}

---

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

• third_party/dart-lang/sdk/runtime/vm/regexp_ast.h
• third_party/dart-lang/sdk/runtime/vm/regexp.cc
• third_party/dart-lang/sdk/runtime/vm/regexp_ast.cc