dart::ChoiceNode Class Reference

#include <regexp.h>

Inheritance diagram for dart::ChoiceNode:

Public Member Functions
	ChoiceNode (intptr_t expected_size, Zone *zone)
virtual void	Accept (NodeVisitor *visitor)
void	AddAlternative (GuardedAlternative node)
ZoneGrowableArray< GuardedAlternative > *	alternatives ()
virtual void	Emit (RegExpCompiler *compiler, Trace *trace)
virtual intptr_t	EatsAtLeast (intptr_t still_to_find, intptr_t budget, bool not_at_start)
intptr_t	EatsAtLeastHelper (intptr_t still_to_find, intptr_t budget, RegExpNode *ignore_this_node, bool not_at_start)
virtual void	GetQuickCheckDetails (QuickCheckDetails *details, RegExpCompiler *compiler, intptr_t characters_filled_in, bool not_at_start)
virtual void	FillInBMInfo (intptr_t offset, intptr_t budget, BoyerMooreLookahead *bm, bool not_at_start)
bool	being_calculated ()
bool	not_at_start ()
void	set_not_at_start ()
void	set_being_calculated (bool b)
virtual bool	try_to_emit_quick_check_for_alternative (bool is_first)
virtual RegExpNode *	FilterOneByte (intptr_t depth)
virtual bool	read_backward ()
Public Member Functions inherited from dart::RegExpNode
	RegExpNode (Zone *zone)
virtual	~RegExpNode ()
virtual void	Accept (NodeVisitor *visitor)=0
virtual void	Emit (RegExpCompiler *compiler, Trace *trace)=0
virtual intptr_t	EatsAtLeast (intptr_t still_to_find, intptr_t budget, bool not_at_start)=0
bool	EmitQuickCheck (RegExpCompiler *compiler, Trace *bounds_check_trace, Trace *trace, bool preload_has_checked_bounds, BlockLabel *on_possible_success, QuickCheckDetails *details_return, bool fall_through_on_failure)
virtual void	GetQuickCheckDetails (QuickCheckDetails *details, RegExpCompiler *compiler, intptr_t characters_filled_in, bool not_at_start)=0
virtual intptr_t	GreedyLoopTextLength ()
virtual RegExpNode *	GetSuccessorOfOmnivorousTextNode (RegExpCompiler *compiler)
virtual void	FillInBMInfo (intptr_t offset, intptr_t budget, BoyerMooreLookahead *bm, bool not_at_start)
virtual RegExpNode *	FilterOneByte (intptr_t depth)
RegExpNode *	replacement ()
RegExpNode *	set_replacement (RegExpNode *replacement)
void	SaveBMInfo (BoyerMooreLookahead *bm, bool not_at_start, intptr_t offset)
BlockLabel *	label ()
NodeInfo *	info ()
BoyerMooreLookahead *	bm_info (bool not_at_start)
Zone *	zone () const
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)

Protected Member Functions
intptr_t	GreedyLoopTextLengthForAlternative (const GuardedAlternative *alternative)
Protected Member Functions inherited from dart::RegExpNode
LimitResult	LimitVersions (RegExpCompiler *compiler, Trace *trace)
void	set_bm_info (bool not_at_start, BoyerMooreLookahead *bm)

Protected Attributes
ZoneGrowableArray< GuardedAlternative > *	alternatives_
Protected Attributes inherited from dart::RegExpNode
RegExpNode *	replacement_

Friends
class	Analysis

Additional Inherited Members
Static Public Attributes inherited from dart::RegExpNode
static constexpr intptr_t	kNodeIsTooComplexForGreedyLoops = -1
static constexpr intptr_t	kRecursionBudget = 200
static constexpr intptr_t	kMaxCopiesCodeGenerated = 10
Protected Types inherited from dart::RegExpNode
enum	LimitResult { DONE , CONTINUE }

Detailed Description

Definition at line 894 of file regexp.h.

Constructor & Destructor Documentation

ChoiceNode()

dart::ChoiceNode::ChoiceNode ( intptr_t  expected_size, Zone *  zone  )

inlineexplicit

Definition at line 896 of file regexp.h.

      : RegExpNode(zone),
        alternatives_(new(zone)
                          ZoneGrowableArray<GuardedAlternative>(expected_size)),
        not_at_start_(false),
        being_calculated_(false) {}

Member Function Documentation

Accept()

virtual void dart::ChoiceNode::Accept ( NodeVisitor *  visitor )

virtual

Implements dart::RegExpNode.

Reimplemented in dart::LoopChoiceNode.

AddAlternative()

void dart::ChoiceNode::AddAlternative ( GuardedAlternative  node )

inline

Definition at line 903 of file regexp.h.

{ alternatives()->Add(node); }

alternatives()

ZoneGrowableArray< GuardedAlternative > * dart::ChoiceNode::alternatives ( )

inline

Definition at line 904 of file regexp.h.

                                                        {
    return alternatives_;
  }

being_calculated()

bool dart::ChoiceNode::being_calculated ( )

inline

Definition at line 924 of file regexp.h.

{ return being_calculated_; }

EatsAtLeast()

intptr_t dart::ChoiceNode::EatsAtLeast ( intptr_t  still_to_find, intptr_t  budget, bool  not_at_start  )

virtual

Implements dart::RegExpNode.

Reimplemented in dart::NegativeLookaroundChoiceNode, and dart::LoopChoiceNode.

Definition at line 1582 of file regexp.cc.

                                                    {
  return EatsAtLeastHelper(still_to_find, budget, nullptr, not_at_start);
}

EatsAtLeastHelper()

intptr_t dart::ChoiceNode::EatsAtLeastHelper	(	intptr_t	still_to_find,
		intptr_t	budget,
		RegExpNode *	ignore_this_node,
		bool	not_at_start
	)

Definition at line 1557 of file regexp.cc.

                                                          {
  if (budget <= 0) return 0;
  intptr_t min = 100;
  intptr_t choice_count = alternatives_->length();
  budget = (budget - 1) / choice_count;
  for (intptr_t i = 0; i < choice_count; i++) {
    RegExpNode* node = (*alternatives_)[i].node();
    if (node == ignore_this_node) continue;
    intptr_t node_eats_at_least =
        node->EatsAtLeast(still_to_find, budget, not_at_start);
    if (node_eats_at_least < min) min = node_eats_at_least;
    if (min == 0) return 0;
  }
  return min;
}

Emit()

void dart::ChoiceNode::Emit ( RegExpCompiler *  compiler, Trace *  trace  )

virtual

Implements dart::RegExpNode.

Reimplemented in dart::LoopChoiceNode.

Definition at line 3127 of file regexp.cc.

                                                            {
  intptr_t choice_count = alternatives_->length();
 
  if (choice_count == 1 && alternatives_->At(0).guards() == nullptr) {
    alternatives_->At(0).node()->Emit(compiler, trace);
    return;
  }
 
  AssertGuardsMentionRegisters(trace);
 
  LimitResult limit_result = LimitVersions(compiler, trace);
  if (limit_result == DONE) return;
  ASSERT(limit_result == CONTINUE);
 
  // For loop nodes we already flushed (see LoopChoiceNode::Emit), but for
  // other choice nodes we only flush if we are out of code size budget.
  if (trace->flush_budget() == 0 && trace->actions() != nullptr) {
    trace->Flush(compiler, this);
    return;
  }
 
  RecursionCheck rc(compiler);
 
  PreloadState preload;
  preload.init();
  GreedyLoopState greedy_loop_state(not_at_start());
 
  intptr_t text_length =
      GreedyLoopTextLengthForAlternative(&alternatives_->At(0));
  AlternativeGenerationList alt_gens(choice_count);
 
  if (choice_count > 1 && text_length != kNodeIsTooComplexForGreedyLoops) {
    trace = EmitGreedyLoop(compiler, trace, &alt_gens, &preload,
                           &greedy_loop_state, text_length);
  } else {
    // TODO(erikcorry): Delete this.  We don't need this label, but it makes us
    // match the traces produced pre-cleanup.
    BlockLabel second_choice;
    compiler->macro_assembler()->BindBlock(&second_choice);
 
    preload.eats_at_least_ = EmitOptimizedUnanchoredSearch(compiler, trace);
 
    EmitChoices(compiler, &alt_gens, 0, trace, &preload);
  }
 
  // At this point we need to generate slow checks for the alternatives where
  // the quick check was inlined.  We can recognize these because the associated
  // label was bound.
  intptr_t new_flush_budget = trace->flush_budget() / choice_count;
  for (intptr_t i = 0; i < choice_count; i++) {
    AlternativeGeneration* alt_gen = alt_gens.at(i);
    Trace new_trace(*trace);
    // If there are actions to be flushed we have to limit how many times
    // they are flushed.  Take the budget of the parent trace and distribute
    // it fairly amongst the children.
    if (new_trace.actions() != nullptr) {
      new_trace.set_flush_budget(new_flush_budget);
    }
    bool next_expects_preload =
        i == choice_count - 1 ? false : alt_gens.at(i + 1)->expects_preload;
    EmitOutOfLineContinuation(compiler, &new_trace, alternatives_->At(i),
                              alt_gen, preload.preload_characters_,
                              next_expects_preload);
  }
}

FillInBMInfo()

void dart::ChoiceNode::FillInBMInfo ( intptr_t  offset, intptr_t  budget, BoyerMooreLookahead *  bm, bool  not_at_start  )

virtual

Reimplemented from dart::RegExpNode.

Reimplemented in dart::NegativeLookaroundChoiceNode, and dart::LoopChoiceNode.

Definition at line 5185 of file regexp.cc.

                                                 {
  ZoneGrowableArray<GuardedAlternative>* alts = alternatives();
  budget = (budget - 1) / alts->length();
  for (intptr_t i = 0; i < alts->length(); i++) {
    GuardedAlternative& alt = (*alts)[i];
    if (alt.guards() != nullptr && alt.guards()->length() != 0) {
      bm->SetRest(offset);  // Give up trying to fill in info.
      SaveBMInfo(bm, not_at_start, offset);
      return;
    }
    alt.node()->FillInBMInfo(offset, budget, bm, not_at_start);
  }
  SaveBMInfo(bm, not_at_start, offset);
}

FilterOneByte()

RegExpNode * dart::ChoiceNode::FilterOneByte ( intptr_t  depth )

virtual

Reimplemented from dart::RegExpNode.

Reimplemented in dart::NegativeLookaroundChoiceNode, and dart::LoopChoiceNode.

Definition at line 2049 of file regexp.cc.

                                                    {
  if (info()->replacement_calculated) return replacement();
  if (depth < 0) return this;
  if (info()->visited) return this;
  VisitMarker marker(info());
  intptr_t choice_count = alternatives_->length();
 
  for (intptr_t i = 0; i < choice_count; i++) {
    GuardedAlternative alternative = alternatives_->At(i);
    if (alternative.guards() != nullptr &&
        alternative.guards()->length() != 0) {
      set_replacement(this);
      return this;
    }
  }
 
  intptr_t surviving = 0;
  RegExpNode* survivor = nullptr;
  for (intptr_t i = 0; i < choice_count; i++) {
    GuardedAlternative alternative = alternatives_->At(i);
    RegExpNode* replacement = alternative.node()->FilterOneByte(depth - 1);
    ASSERT(replacement != this);  // No missing EMPTY_MATCH_CHECK.
    if (replacement != nullptr) {
      (*alternatives_)[i].set_node(replacement);
      surviving++;
      survivor = replacement;
    }
  }
  if (surviving < 2) return set_replacement(survivor);
 
  set_replacement(this);
  if (surviving == choice_count) {
    return this;
  }
  // Only some of the nodes survived the filtering.  We need to rebuild the
  // alternatives list.
  ZoneGrowableArray<GuardedAlternative>* new_alternatives =
      new (Z) ZoneGrowableArray<GuardedAlternative>(surviving);
  for (intptr_t i = 0; i < choice_count; i++) {
    RegExpNode* replacement =
        (*alternatives_)[i].node()->FilterOneByte(depth - 1);
    if (replacement != nullptr) {
      (*alternatives_)[i].set_node(replacement);
      new_alternatives->Add((*alternatives_)[i]);
    }
  }
  alternatives_ = new_alternatives;
  return this;
}

GetQuickCheckDetails()

void dart::ChoiceNode::GetQuickCheckDetails ( QuickCheckDetails *  details, RegExpCompiler *  compiler, intptr_t  characters_filled_in, bool  not_at_start  )

virtual

Implements dart::RegExpNode.

Reimplemented in dart::NegativeLookaroundChoiceNode, and dart::LoopChoiceNode.

Definition at line 2143 of file regexp.cc.

                                                         {
  not_at_start = (not_at_start || not_at_start_);
  intptr_t choice_count = alternatives_->length();
  ASSERT(choice_count > 0);
  (*alternatives_)[0].node()->GetQuickCheckDetails(
      details, compiler, characters_filled_in, not_at_start);
  for (intptr_t i = 1; i < choice_count; i++) {
    QuickCheckDetails new_details(details->characters());
    RegExpNode* node = (*alternatives_)[i].node();
    node->GetQuickCheckDetails(&new_details, compiler, characters_filled_in,
                               not_at_start);
    // Here we merge the quick match details of the two branches.
    details->Merge(&new_details, characters_filled_in);
  }
}

GreedyLoopTextLengthForAlternative()

intptr_t dart::ChoiceNode::GreedyLoopTextLengthForAlternative ( const GuardedAlternative *  alternative )

protected

Definition at line 2632 of file regexp.cc.

                                           {
  intptr_t length = 0;
  RegExpNode* node = alternative->node();
  // Later we will generate code for all these text nodes using recursion
  // so we have to limit the max number.
  intptr_t recursion_depth = 0;
  while (node != this) {
    if (recursion_depth++ > RegExpCompiler::kMaxRecursion) {
      return kNodeIsTooComplexForGreedyLoops;
    }
    intptr_t node_length = node->GreedyLoopTextLength();
    if (node_length == kNodeIsTooComplexForGreedyLoops) {
      return kNodeIsTooComplexForGreedyLoops;
    }
    length += node_length;
    SeqRegExpNode* seq_node = static_cast<SeqRegExpNode*>(node);
    node = seq_node->on_success();
  }
  return read_backward() ? -length : length;
}

not_at_start()

bool dart::ChoiceNode::not_at_start ( )

inline

Definition at line 925 of file regexp.h.

{ return not_at_start_; }

read_backward()

virtual bool dart::ChoiceNode::read_backward ( )

inlinevirtual

Reimplemented in dart::LoopChoiceNode.

Definition at line 932 of file regexp.h.

{ return false; }

set_being_calculated()

void dart::ChoiceNode::set_being_calculated ( bool  b )

inline

Definition at line 927 of file regexp.h.

{ being_calculated_ = b; }

set_not_at_start()

void dart::ChoiceNode::set_not_at_start ( )

inline

Definition at line 926 of file regexp.h.

{ not_at_start_ = true; }

try_to_emit_quick_check_for_alternative()

virtual bool dart::ChoiceNode::try_to_emit_quick_check_for_alternative ( bool  is_first )

inlinevirtual

Reimplemented in dart::NegativeLookaroundChoiceNode.

Definition at line 928 of file regexp.h.

                                                                      {
    return true;
  }

Friends And Related Function Documentation

Analysis

friend class Analysis

friend

Definition at line 940 of file regexp.h.

Member Data Documentation

alternatives_

ZoneGrowableArray<GuardedAlternative>* dart::ChoiceNode::alternatives_

protected

Definition at line 937 of file regexp.h.

---

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

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