#include <jsregexp.h>

Inheritance diagram for v8::internal::ChoiceNode:

Collaboration diagram for v8::internal::ChoiceNode:

Public Member Functions
	ChoiceNode (int expected_size, Zone *zone)

virtual void	Accept (NodeVisitor *visitor)

void	AddAlternative (GuardedAlternative node)

ZoneList< GuardedAlternative > *	alternatives ()

DispatchTable *	GetTable (bool ignore_case)

virtual void	Emit (RegExpCompiler compiler, Trace trace)

virtual int	EatsAtLeast (int still_to_find, int budget, bool not_at_start)

int	EatsAtLeastHelper (int still_to_find, int budget, RegExpNode *ignore_this_node, bool not_at_start)

virtual void	GetQuickCheckDetails (QuickCheckDetails details, RegExpCompiler compiler, int characters_filled_in, bool not_at_start)

virtual void	FillInBMInfo (int offset, int 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 (int depth, bool ignore_case)

Public Member Functions inherited from v8::internal::RegExpNode
	RegExpNode (Zone *zone)

virtual	~RegExpNode ()

bool	EmitQuickCheck (RegExpCompiler compiler, Trace bounds_check_trace, Trace trace, bool preload_has_checked_bounds, Label on_possible_success, QuickCheckDetails *details_return, bool fall_through_on_failure)

virtual int	GreedyLoopTextLength ()

virtual RegExpNode *	GetSuccessorOfOmnivorousTextNode (RegExpCompiler *compiler)

RegExpNode *	replacement ()

RegExpNode *	set_replacement (RegExpNode *replacement)

void	SaveBMInfo (BoyerMooreLookahead *bm, bool not_at_start, int offset)

Label *	label ()

NodeInfo *	info ()

BoyerMooreLookahead *	bm_info (bool not_at_start)

Zone *	zone () const

Public Member Functions inherited from v8::internal::ZoneObject
	INLINE (void operator new(size_t size, Zone zone))

void	operator delete (void *, size_t)

void	operator delete (void pointer, Zone zone)

Protected Member Functions
int	GreedyLoopTextLengthForAlternative (GuardedAlternative *alternative)

Protected Member Functions inherited from v8::internal::RegExpNode
LimitResult	LimitVersions (RegExpCompiler compiler, Trace trace)

void	set_bm_info (bool not_at_start, BoyerMooreLookahead *bm)

Protected Attributes
ZoneList< GuardedAlternative > *	alternatives_

Protected Attributes inherited from v8::internal::RegExpNode
RegExpNode *	replacement_

Private Member Functions
void	GenerateGuard (RegExpMacroAssembler macro_assembler, Guard guard, Trace *trace)

int	CalculatePreloadCharacters (RegExpCompiler *compiler, int eats_at_least)

void	EmitOutOfLineContinuation (RegExpCompiler compiler, Trace trace, GuardedAlternative alternative, AlternativeGeneration *alt_gen, int preload_characters, bool next_expects_preload)

void	SetUpPreLoad (RegExpCompiler compiler, Trace current_trace, PreloadState *preloads)

void	AssertGuardsMentionRegisters (Trace *trace)

int	EmitOptimizedUnanchoredSearch (RegExpCompiler compiler, Trace trace)

Trace *	EmitGreedyLoop (RegExpCompiler compiler, Trace trace, AlternativeGenerationList alt_gens, PreloadState preloads, GreedyLoopState *greedy_loop_state, int text_length)

void	EmitChoices (RegExpCompiler compiler, AlternativeGenerationList alt_gens, int first_choice, Trace trace, PreloadState preloads)

Private Attributes
DispatchTable *	table_

bool	not_at_start_

bool	being_calculated_

Friends
class	DispatchTableConstructor

class	Analysis

Additional Inherited Members
Static Public Attributes inherited from v8::internal::RegExpNode
static const int	kNodeIsTooComplexForGreedyLoops = -1

static const int	kRecursionBudget = 200

static const int	kMaxCopiesCodeGenerated = 10

Protected Types inherited from v8::internal::RegExpNode
enum	LimitResult { DONE , CONTINUE }

Detailed Description

Definition at line 1051 of file jsregexp.h.

Constructor & Destructor Documentation

◆ ChoiceNode()

v8::internal::ChoiceNode::ChoiceNode	(	int	expected_size,
		Zone *	zone
	)

inlineexplicit

Definition at line 1053 of file jsregexp.h.

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

Member Function Documentation

◆ Accept()

virtual void v8::internal::ChoiceNode::Accept ( NodeVisitor * visitor )

virtual

Implements v8::internal::RegExpNode.

Reimplemented in v8::internal::LoopChoiceNode.

◆ AddAlternative()

void v8::internal::ChoiceNode::AddAlternative ( GuardedAlternative node )

inline

Definition at line 1061 of file jsregexp.h.

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

References alternatives(), and v8::internal::RegExpNode::zone().

Referenced by v8::internal::LoopChoiceNode::AddAlternative(), v8::internal::RegExpEngine::Compile(), and v8::internal::NegativeLookaheadChoiceNode::NegativeLookaheadChoiceNode().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ alternatives()

ZoneList<GuardedAlternative>* v8::internal::ChoiceNode::alternatives ( )

inline

Definition at line 1064 of file jsregexp.h.

1064 { return alternatives_; }

References alternatives_.

Referenced by AddAlternative(), v8::internal::DispatchTableConstructor::BuildTable(), FillInBMInfo(), and v8::internal::Analysis::VisitLoopChoice().

Here is the caller graph for this function:

◆ AssertGuardsMentionRegisters()

void v8::internal::ChoiceNode::AssertGuardsMentionRegisters ( Trace * trace )

private

Definition at line 3900 of file jsregexp.cc.

                                                           {
 #ifdef DEBUG
   int choice_count = alternatives_->length();
   for (int i = 0; i < choice_count - 1; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     for (int j = 0; j < guard_count; j++) {
       DCHECK(!trace->mentions_reg(guards->at(j)->reg()));
     }
   }
 #endif
 }

References alternatives_, v8::internal::List< T, AllocationPolicy >::at(), DCHECK, v8::internal::GuardedAlternative::guards(), v8::internal::Trace::mentions_reg(), and NULL.

Referenced by Emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ being_calculated()

bool v8::internal::ChoiceNode::being_calculated ( )

inline

Definition at line 1081 of file jsregexp.h.

1081 { return being_calculated_; }

References being_calculated_.

◆ CalculatePreloadCharacters()

int v8::internal::ChoiceNode::CalculatePreloadCharacters	(	RegExpCompiler *	compiler,
		int	eats_at_least
	)

private

Definition at line 3506 of file jsregexp.cc.

                                                               {
   int preload_characters = Min(4, eats_at_least);
   if (compiler->macro_assembler()->CanReadUnaligned()) {
     bool one_byte = compiler->one_byte();
     if (one_byte) {
       if (preload_characters > 4) preload_characters = 4;
       // We can't preload 3 characters because there is no machine instruction
       // to do that.  We can't just load 4 because we could be reading
       // beyond the end of the string, which could cause a memory fault.
       if (preload_characters == 3) preload_characters = 2;
     } else {
       if (preload_characters > 2) preload_characters = 2;
     }
   } else {
     if (preload_characters > 1) preload_characters = 1;
   }
   return preload_characters;
 }

References v8::internal::RegExpMacroAssembler::CanReadUnaligned(), v8::internal::RegExpCompiler::macro_assembler(), v8::internal::Min(), and v8::internal::RegExpCompiler::one_byte().

Referenced by SetUpPreLoad().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EatsAtLeast()

int v8::internal::ChoiceNode::EatsAtLeast	(	int	still_to_find,
		int	budget,
		bool	not_at_start
	)

virtual

Implements v8::internal::RegExpNode.

Reimplemented in v8::internal::LoopChoiceNode, and v8::internal::NegativeLookaheadChoiceNode.

Definition at line 2400 of file jsregexp.cc.

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

References NULL.

Referenced by EmitOptimizedUnanchoredSearch(), and SetUpPreLoad().

Here is the caller graph for this function:

◆ EatsAtLeastHelper()

int v8::internal::ChoiceNode::EatsAtLeastHelper	(	int	still_to_find,
		int	budget,
		RegExpNode *	ignore_this_node,
		bool	not_at_start
	)

Definition at line 2370 of file jsregexp.cc.

                                                      {
   if (budget <= 0) return 0;
   int min = 100;
   int choice_count = alternatives_->length();
   budget = (budget - 1) / choice_count;
   for (int i = 0; i < choice_count; i++) {
     RegExpNode* node = alternatives_->at(i).node();
     if (node == ignore_this_node) continue;
     int 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;
 }

References v8::internal::RegExpNode::EatsAtLeast(), and v8::internal::min().

Here is the call graph for this function:

◆ Emit()

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

virtual

Implements v8::internal::RegExpNode.

Reimplemented in v8::internal::LoopChoiceNode.

Definition at line 3933 of file jsregexp.cc.

                                                             {
   int choice_count = alternatives_->length();
  
   AssertGuardsMentionRegisters(trace);
  
   LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return;
   DCHECK(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() != NULL) {
     trace->Flush(compiler, this);
     return;
   }
  
   RecursionCheck rc(compiler);
  
   PreloadState preload;
   preload.init();
   GreedyLoopState greedy_loop_state(not_at_start());
  
   int text_length = GreedyLoopTextLengthForAlternative(&alternatives_->at(0));
   AlternativeGenerationList alt_gens(choice_count, zone());
  
   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.
     Label second_choice;
     compiler->macro_assembler()->Bind(&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.
   int new_flush_budget = trace->flush_budget() / choice_count;
   for (int 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() != NULL) {
       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);
   }
 }

References v8::internal::Trace::actions(), alternatives_, AssertGuardsMentionRegisters(), v8::internal::AlternativeGenerationList::at(), v8::internal::RegExpMacroAssembler::Bind(), v8::internal::RegExpNode::CONTINUE, DCHECK, v8::internal::RegExpNode::DONE, v8::internal::PreloadState::eats_at_least_, EmitChoices(), EmitGreedyLoop(), EmitOptimizedUnanchoredSearch(), EmitOutOfLineContinuation(), v8::internal::AlternativeGeneration::expects_preload, false, v8::internal::Trace::Flush(), v8::internal::Trace::flush_budget(), GreedyLoopTextLengthForAlternative(), v8::internal::PreloadState::init(), v8::internal::RegExpNode::kNodeIsTooComplexForGreedyLoops, v8::internal::RegExpNode::LimitVersions(), v8::internal::RegExpCompiler::macro_assembler(), not_at_start(), NULL, v8::internal::PreloadState::preload_characters_, v8::internal::Trace::set_flush_budget(), and v8::internal::RegExpNode::zone().

Referenced by v8::internal::LoopChoiceNode::Emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EmitChoices()

void v8::internal::ChoiceNode::EmitChoices	(	RegExpCompiler *	compiler,
		AlternativeGenerationList *	alt_gens,
		int	first_choice,
		Trace *	trace,
		PreloadState *	preloads
	)

private

Definition at line 4103 of file jsregexp.cc.

                                                     {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   SetUpPreLoad(compiler, trace, preload);
  
   // For now we just call all choices one after the other.  The idea ultimately
   // is to use the Dispatch table to try only the relevant ones.
   int choice_count = alternatives_->length();
  
   int new_flush_budget = trace->flush_budget() / choice_count;
  
   for (int i = first_choice; i < choice_count; i++) {
     bool is_last = i == choice_count - 1;
     bool fall_through_on_failure = !is_last;
     GuardedAlternative alternative = alternatives_->at(i);
     AlternativeGeneration* alt_gen = alt_gens->at(i);
     alt_gen->quick_check_details.set_characters(preload->preload_characters_);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     Trace new_trace(*trace);
     new_trace.set_characters_preloaded(preload->preload_is_current_ ?
                                          preload->preload_characters_ :
                                          0);
     if (preload->preload_has_checked_bounds_) {
       new_trace.set_bound_checked_up_to(preload->preload_characters_);
     }
     new_trace.quick_check_performed()->Clear();
     if (not_at_start_) new_trace.set_at_start(Trace::FALSE_VALUE);
     if (!is_last) {
       new_trace.set_backtrack(&alt_gen->after);
     }
     alt_gen->expects_preload = preload->preload_is_current_;
     bool generate_full_check_inline = false;
     if (FLAG_regexp_optimization &&
         try_to_emit_quick_check_for_alternative(i == 0) &&
         alternative.node()->EmitQuickCheck(compiler,
                                            trace,
                                            &new_trace,
                                            preload->preload_has_checked_bounds_,
                                            &alt_gen->possible_success,
                                            &alt_gen->quick_check_details,
                                            fall_through_on_failure)) {
       // Quick check was generated for this choice.
       preload->preload_is_current_ = true;
       preload->preload_has_checked_bounds_ = true;
       // If we generated the quick check to fall through on possible success,
       // we now need to generate the full check inline.
       if (!fall_through_on_failure) {
         macro_assembler->Bind(&alt_gen->possible_success);
         new_trace.set_quick_check_performed(&alt_gen->quick_check_details);
         new_trace.set_characters_preloaded(preload->preload_characters_);
         new_trace.set_bound_checked_up_to(preload->preload_characters_);
         generate_full_check_inline = true;
       }
     } else if (alt_gen->quick_check_details.cannot_match()) {
       if (!fall_through_on_failure) {
         macro_assembler->GoTo(trace->backtrack());
       }
       continue;
     } else {
       // No quick check was generated.  Put the full code here.
       // If this is not the first choice then there could be slow checks from
       // previous cases that go here when they fail.  There's no reason to
       // insist that they preload characters since the slow check we are about
       // to generate probably can't use it.
       if (i != first_choice) {
         alt_gen->expects_preload = false;
         new_trace.InvalidateCurrentCharacter();
       }
       generate_full_check_inline = true;
     }
     if (generate_full_check_inline) {
       if (new_trace.actions() != NULL) {
         new_trace.set_flush_budget(new_flush_budget);
       }
       for (int j = 0; j < guard_count; j++) {
         GenerateGuard(macro_assembler, guards->at(j), &new_trace);
       }
       alternative.node()->Emit(compiler, &new_trace);
       preload->preload_is_current_ = false;
     }
     macro_assembler->Bind(&alt_gen->after);
   }
 }

Referenced by Emit(), and EmitGreedyLoop().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EmitGreedyLoop()

Trace * v8::internal::ChoiceNode::EmitGreedyLoop	(	RegExpCompiler *	compiler,
		Trace *	trace,
		AlternativeGenerationList *	alt_gens,
		PreloadState *	preloads,
		GreedyLoopState *	greedy_loop_state,
		int	text_length
	)

private

Definition at line 4005 of file jsregexp.cc.

                                                    {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   // Here we have special handling for greedy loops containing only text nodes
   // and other simple nodes.  These are handled by pushing the current
   // position on the stack and then incrementing the current position each
   // time around the switch.  On backtrack we decrement the current position
   // and check it against the pushed value.  This avoids pushing backtrack
   // information for each iteration of the loop, which could take up a lot of
   // space.
   DCHECK(trace->stop_node() == NULL);
   macro_assembler->PushCurrentPosition();
   Label greedy_match_failed;
   Trace greedy_match_trace;
   if (not_at_start()) greedy_match_trace.set_at_start(false);
   greedy_match_trace.set_backtrack(&greedy_match_failed);
   Label loop_label;
   macro_assembler->Bind(&loop_label);
   greedy_match_trace.set_stop_node(this);
   greedy_match_trace.set_loop_label(&loop_label);
   alternatives_->at(0).node()->Emit(compiler, &greedy_match_trace);
   macro_assembler->Bind(&greedy_match_failed);
  
   Label second_choice;  // For use in greedy matches.
   macro_assembler->Bind(&second_choice);
  
   Trace* new_trace = greedy_loop_state->counter_backtrack_trace();
  
   EmitChoices(compiler,
               alt_gens,
               1,
               new_trace,
               preload);
  
   macro_assembler->Bind(greedy_loop_state->label());
   // If we have unwound to the bottom then backtrack.
   macro_assembler->CheckGreedyLoop(trace->backtrack());
   // Otherwise try the second priority at an earlier position.
   macro_assembler->AdvanceCurrentPosition(-text_length);
   macro_assembler->GoTo(&second_choice);
   return new_trace;
 }

References v8::internal::RegExpMacroAssembler::AdvanceCurrentPosition(), alternatives_, v8::internal::Trace::backtrack(), v8::internal::RegExpMacroAssembler::Bind(), v8::internal::RegExpMacroAssembler::CheckGreedyLoop(), v8::internal::GreedyLoopState::counter_backtrack_trace(), DCHECK, EmitChoices(), v8::internal::RegExpMacroAssembler::GoTo(), v8::internal::GreedyLoopState::label(), v8::internal::RegExpCompiler::macro_assembler(), not_at_start(), NULL, v8::internal::RegExpMacroAssembler::PushCurrentPosition(), v8::internal::Trace::set_at_start(), v8::internal::Trace::set_backtrack(), v8::internal::Trace::set_loop_label(), v8::internal::Trace::set_stop_node(), and v8::internal::Trace::stop_node().

Referenced by Emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EmitOptimizedUnanchoredSearch()

int v8::internal::ChoiceNode::EmitOptimizedUnanchoredSearch	(	RegExpCompiler *	compiler,
		Trace *	trace
	)

private

Definition at line 4052 of file jsregexp.cc.

                                                             {
   int eats_at_least = PreloadState::kEatsAtLeastNotYetInitialized;
   if (alternatives_->length() != 2) return eats_at_least;
  
   GuardedAlternative alt1 = alternatives_->at(1);
   if (alt1.guards() != NULL && alt1.guards()->length() != 0) {
     return eats_at_least;
   }
   RegExpNode* eats_anything_node = alt1.node();
   if (eats_anything_node->GetSuccessorOfOmnivorousTextNode(compiler) != this) {
     return eats_at_least;
   }
  
   // Really we should be creating a new trace when we execute this function,
   // but there is no need, because the code it generates cannot backtrack, and
   // we always arrive here with a trivial trace (since it's the entry to a
   // loop.  That also implies that there are no preloaded characters, which is
   // good, because it means we won't be violating any assumptions by
   // overwriting those characters with new load instructions.
   DCHECK(trace->is_trivial());
  
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   // At this point we know that we are at a non-greedy loop that will eat
   // any character one at a time.  Any non-anchored regexp has such a
   // loop prepended to it in order to find where it starts.  We look for
   // a pattern of the form ...abc... where we can look 6 characters ahead
   // and step forwards 3 if the character is not one of abc.  Abc need
   // not be atoms, they can be any reasonably limited character class or
   // small alternation.
   BoyerMooreLookahead* bm = bm_info(false);
   if (bm == NULL) {
     eats_at_least = Min(kMaxLookaheadForBoyerMoore,
                         EatsAtLeast(kMaxLookaheadForBoyerMoore,
                                     kRecursionBudget,
                                     false));
     if (eats_at_least >= 1) {
       bm = new(zone()) BoyerMooreLookahead(eats_at_least,
                                            compiler,
                                            zone());
       GuardedAlternative alt0 = alternatives_->at(0);
       alt0.node()->FillInBMInfo(0, kRecursionBudget, bm, false);
     }
   }
   if (bm != NULL) {
     bm->EmitSkipInstructions(macro_assembler);
   }
   return eats_at_least;
 }

References alternatives_, v8::internal::RegExpNode::bm_info(), DCHECK, EatsAtLeast(), v8::internal::BoyerMooreLookahead::EmitSkipInstructions(), v8::internal::RegExpNode::FillInBMInfo(), v8::internal::RegExpNode::GetSuccessorOfOmnivorousTextNode(), v8::internal::GuardedAlternative::guards(), v8::internal::Trace::is_trivial(), v8::internal::PreloadState::kEatsAtLeastNotYetInitialized, v8::internal::kMaxLookaheadForBoyerMoore, v8::internal::RegExpNode::kRecursionBudget, v8::internal::RegExpCompiler::macro_assembler(), v8::internal::Min(), v8::internal::GuardedAlternative::node(), NULL, and v8::internal::RegExpNode::zone().

Referenced by Emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EmitOutOfLineContinuation()

void v8::internal::ChoiceNode::EmitOutOfLineContinuation	(	RegExpCompiler *	compiler,
		Trace *	trace,
		GuardedAlternative	alternative,
		AlternativeGeneration *	alt_gen,
		int	preload_characters,
		bool	next_expects_preload
	)

private

Definition at line 4192 of file jsregexp.cc.

                                                                       {
   if (!alt_gen->possible_success.is_linked()) return;
  
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   macro_assembler->Bind(&alt_gen->possible_success);
   Trace out_of_line_trace(*trace);
   out_of_line_trace.set_characters_preloaded(preload_characters);
   out_of_line_trace.set_quick_check_performed(&alt_gen->quick_check_details);
   if (not_at_start_) out_of_line_trace.set_at_start(Trace::FALSE_VALUE);
   ZoneList<Guard*>* guards = alternative.guards();
   int guard_count = (guards == NULL) ? 0 : guards->length();
   if (next_expects_preload) {
     Label reload_current_char;
     out_of_line_trace.set_backtrack(&reload_current_char);
     for (int j = 0; j < guard_count; j++) {
       GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
     }
     alternative.node()->Emit(compiler, &out_of_line_trace);
     macro_assembler->Bind(&reload_current_char);
     // Reload the current character, since the next quick check expects that.
     // We don't need to check bounds here because we only get into this
     // code through a quick check which already did the checked load.
     macro_assembler->LoadCurrentCharacter(trace->cp_offset(),
                                           NULL,
                                           false,
                                           preload_characters);
     macro_assembler->GoTo(&(alt_gen->after));
   } else {
     out_of_line_trace.set_backtrack(&(alt_gen->after));
     for (int j = 0; j < guard_count; j++) {
       GenerateGuard(macro_assembler, guards->at(j), &out_of_line_trace);
     }
     alternative.node()->Emit(compiler, &out_of_line_trace);
   }
 }

References v8::internal::AlternativeGeneration::after, v8::internal::List< T, AllocationPolicy >::at(), v8::internal::RegExpMacroAssembler::Bind(), v8::internal::Trace::cp_offset(), v8::internal::RegExpNode::Emit(), v8::internal::Trace::FALSE_VALUE, GenerateGuard(), v8::internal::RegExpMacroAssembler::GoTo(), v8::internal::GuardedAlternative::guards(), v8::internal::RegExpMacroAssembler::LoadCurrentCharacter(), v8::internal::RegExpCompiler::macro_assembler(), v8::internal::GuardedAlternative::node(), not_at_start_, NULL, v8::internal::AlternativeGeneration::possible_success, v8::internal::AlternativeGeneration::quick_check_details, v8::internal::Trace::set_at_start(), v8::internal::Trace::set_backtrack(), v8::internal::Trace::set_characters_preloaded(), and v8::internal::Trace::set_quick_check_performed().

Referenced by Emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FillInBMInfo()

void v8::internal::ChoiceNode::FillInBMInfo	(	int	offset,
		int	budget,
		BoyerMooreLookahead *	bm,
		bool	not_at_start
	)

virtual

Reimplemented from v8::internal::RegExpNode.

Reimplemented in v8::internal::LoopChoiceNode, and v8::internal::NegativeLookaheadChoiceNode.

Definition at line 5836 of file jsregexp.cc.

                                                  {
   ZoneList<GuardedAlternative>* alts = alternatives();
   budget = (budget - 1) / alts->length();
   for (int i = 0; i < alts->length(); i++) {
     GuardedAlternative& alt = alts->at(i);
     if (alt.guards() != NULL && 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);
 }

References alternatives(), v8::internal::List< T, AllocationPolicy >::at(), v8::internal::RegExpNode::FillInBMInfo(), v8::internal::GuardedAlternative::guards(), v8::internal::GuardedAlternative::node(), not_at_start(), NULL, v8::internal::RegExpNode::SaveBMInfo(), and v8::internal::BoyerMooreLookahead::SetRest().

Referenced by v8::internal::LoopChoiceNode::FillInBMInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FilterOneByte()

RegExpNode * v8::internal::ChoiceNode::FilterOneByte	(	int	depth,
		bool	ignore_case
	)

virtual

Reimplemented from v8::internal::RegExpNode.

Reimplemented in v8::internal::LoopChoiceNode, and v8::internal::NegativeLookaheadChoiceNode.

Definition at line 2861 of file jsregexp.cc.

                                                                  {
   if (info()->replacement_calculated) return replacement();
   if (depth < 0) return this;
   if (info()->visited) return this;
   VisitMarker marker(info());
   int choice_count = alternatives_->length();
  
   for (int i = 0; i < choice_count; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
     if (alternative.guards() != NULL && alternative.guards()->length() != 0) {
       set_replacement(this);
       return this;
     }
   }
  
   int surviving = 0;
   RegExpNode* survivor = NULL;
   for (int i = 0; i < choice_count; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
     RegExpNode* replacement =
         alternative.node()->FilterOneByte(depth - 1, ignore_case);
     DCHECK(replacement != this);  // No missing EMPTY_MATCH_CHECK.
     if (replacement != NULL) {
       alternatives_->at(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.
   ZoneList<GuardedAlternative>* new_alternatives =
       new(zone()) ZoneList<GuardedAlternative>(surviving, zone());
   for (int i = 0; i < choice_count; i++) {
     RegExpNode* replacement =
         alternatives_->at(i).node()->FilterOneByte(depth - 1, ignore_case);
     if (replacement != NULL) {
       alternatives_->at(i).set_node(replacement);
       new_alternatives->Add(alternatives_->at(i), zone());
     }
   }
   alternatives_ = new_alternatives;
   return this;
 }

References v8::internal::List< T, AllocationPolicy >::Add(), DCHECK, v8::internal::RegExpNode::FilterOneByte(), v8::internal::GuardedAlternative::guards(), v8::internal::GuardedAlternative::node(), and NULL.

Referenced by v8::internal::LoopChoiceNode::FilterOneByte().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GenerateGuard()

void v8::internal::ChoiceNode::GenerateGuard	(	RegExpMacroAssembler *	macro_assembler,
		Guard *	guard,
		Trace *	trace
	)

private

Definition at line 1568 of file jsregexp.cc.

                                              {
   switch (guard->op()) {
     case Guard::LT:
       DCHECK(!trace->mentions_reg(guard->reg()));
       macro_assembler->IfRegisterGE(guard->reg(),
                                     guard->value(),
                                     trace->backtrack());
       break;
     case Guard::GEQ:
       DCHECK(!trace->mentions_reg(guard->reg()));
       macro_assembler->IfRegisterLT(guard->reg(),
                                     guard->value(),
                                     trace->backtrack());
       break;
   }
 }

References v8::internal::Trace::backtrack(), DCHECK, v8::internal::Guard::GEQ, v8::internal::RegExpMacroAssembler::IfRegisterGE(), v8::internal::RegExpMacroAssembler::IfRegisterLT(), v8::internal::Guard::LT, v8::internal::Trace::mentions_reg(), v8::internal::Guard::op(), v8::internal::Guard::reg(), and v8::internal::Guard::value().

Referenced by EmitChoices(), and EmitOutOfLineContinuation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetQuickCheckDetails()

void v8::internal::ChoiceNode::GetQuickCheckDetails	(	QuickCheckDetails *	details,
		RegExpCompiler *	compiler,
		int	characters_filled_in,
		bool	not_at_start
	)

virtual

Implements v8::internal::RegExpNode.

Reimplemented in v8::internal::LoopChoiceNode, and v8::internal::NegativeLookaheadChoiceNode.

Definition at line 2962 of file jsregexp.cc.

                                                          {
   not_at_start = (not_at_start || not_at_start_);
   int choice_count = alternatives_->length();
   DCHECK(choice_count > 0);
   alternatives_->at(0).node()->GetQuickCheckDetails(details,
                                                     compiler,
                                                     characters_filled_in,
                                                     not_at_start);
   for (int i = 1; i < choice_count; i++) {
     QuickCheckDetails new_details(details->characters());
     RegExpNode* node = alternatives_->at(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);
   }
 }

References v8::internal::QuickCheckDetails::characters(), DCHECK, v8::internal::RegExpNode::GetQuickCheckDetails(), and v8::internal::QuickCheckDetails::Merge().

Referenced by v8::internal::LoopChoiceNode::GetQuickCheckDetails().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetTable()

DispatchTable * v8::internal::ChoiceNode::GetTable ( bool ignore_case )

Definition at line 936 of file jsregexp.cc.

                                                     {
   if (table_ == NULL) {
     table_ = new(zone()) DispatchTable(zone());
     DispatchTableConstructor cons(table_, ignore_case, zone());
     cons.BuildTable(this);
   }
   return table_;
 }

References v8::internal::DispatchTableConstructor::BuildTable(), and NULL.

Here is the call graph for this function:

◆ GreedyLoopTextLengthForAlternative()

int v8::internal::ChoiceNode::GreedyLoopTextLengthForAlternative ( GuardedAlternative * alternative )

protected

Definition at line 3446 of file jsregexp.cc.

                                      {
   int 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.
   int recursion_depth = 0;
   while (node != this) {
     if (recursion_depth++ > RegExpCompiler::kMaxRecursion) {
       return kNodeIsTooComplexForGreedyLoops;
     }
     int 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 length;
 }

References v8::internal::RegExpNode::GreedyLoopTextLength(), v8::internal::RegExpCompiler::kMaxRecursion, v8::internal::GuardedAlternative::node(), and v8::internal::SeqRegExpNode::on_success().

Referenced by Emit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ not_at_start()

bool v8::internal::ChoiceNode::not_at_start ( )

inline

Definition at line 1082 of file jsregexp.h.

1082 { return not_at_start_; }

References not_at_start_.

Referenced by Emit(), EmitGreedyLoop(), FillInBMInfo(), and v8::internal::NegativeLookaheadChoiceNode::FillInBMInfo().

Here is the caller graph for this function:

◆ set_being_calculated()

void v8::internal::ChoiceNode::set_being_calculated ( bool b )

inline

Definition at line 1084 of file jsregexp.h.

1084 { being_calculated_ = b; }

References being_calculated_.

Referenced by v8::internal::DispatchTableConstructor::BuildTable().

Here is the caller graph for this function:

◆ set_not_at_start()

void v8::internal::ChoiceNode::set_not_at_start ( )

inline

Definition at line 1083 of file jsregexp.h.

1083 { not_at_start_ = true; }

References not_at_start_.

◆ SetUpPreLoad()

void v8::internal::ChoiceNode::SetUpPreLoad	(	RegExpCompiler *	compiler,
		Trace *	current_trace,
		PreloadState *	preloads
	)

private

Definition at line 3915 of file jsregexp.cc.

                                                    {
     if (state->eats_at_least_ == PreloadState::kEatsAtLeastNotYetInitialized) {
       // Save some time by looking at most one machine word ahead.
       state->eats_at_least_ =
           EatsAtLeast(compiler->one_byte() ? 4 : 2, kRecursionBudget,
                       current_trace->at_start() == Trace::FALSE_VALUE);
     }
     state->preload_characters_ =
         CalculatePreloadCharacters(compiler, state->eats_at_least_);
  
     state->preload_is_current_ =
         (current_trace->characters_preloaded() == state->preload_characters_);
     state->preload_has_checked_bounds_ = state->preload_is_current_;
 }

References v8::internal::Trace::at_start(), CalculatePreloadCharacters(), v8::internal::Trace::characters_preloaded(), v8::internal::PreloadState::eats_at_least_, EatsAtLeast(), v8::internal::Trace::FALSE_VALUE, v8::internal::PreloadState::kEatsAtLeastNotYetInitialized, v8::internal::RegExpNode::kRecursionBudget, v8::internal::RegExpCompiler::one_byte(), v8::internal::PreloadState::preload_characters_, v8::internal::PreloadState::preload_has_checked_bounds_, and v8::internal::PreloadState::preload_is_current_.

Referenced by EmitChoices().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ try_to_emit_quick_check_for_alternative()

virtual bool v8::internal::ChoiceNode::try_to_emit_quick_check_for_alternative ( bool is_first )

inlinevirtual

Reimplemented in v8::internal::NegativeLookaheadChoiceNode.

Definition at line 1085 of file jsregexp.h.

                                                                       {
     return true;
   }

Referenced by EmitChoices().

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ Analysis

friend class Analysis

friend

Definition at line 1096 of file jsregexp.h.

◆ DispatchTableConstructor

friend class DispatchTableConstructor

friend

Definition at line 1095 of file jsregexp.h.

Member Data Documentation

◆ alternatives_

ZoneList<GuardedAlternative>* v8::internal::ChoiceNode::alternatives_

protected

Definition at line 1092 of file jsregexp.h.

Referenced by alternatives(), AssertGuardsMentionRegisters(), Emit(), EmitChoices(), EmitGreedyLoop(), EmitOptimizedUnanchoredSearch(), and v8::internal::NegativeLookaheadChoiceNode::FillInBMInfo().

◆ being_calculated_

bool v8::internal::ChoiceNode::being_calculated_

private

Definition at line 1127 of file jsregexp.h.

Referenced by being_calculated(), and set_being_calculated().

◆ not_at_start_

bool v8::internal::ChoiceNode::not_at_start_

private

Definition at line 1126 of file jsregexp.h.

Referenced by EmitChoices(), EmitOutOfLineContinuation(), not_at_start(), and set_not_at_start().

◆ table_

DispatchTable* v8::internal::ChoiceNode::table_

private

Definition at line 1123 of file jsregexp.h.

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

/mnt/V8SourceCode/src/jsregexp.h
/mnt/V8SourceCode/src/jsregexp.cc

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ChoiceNode()

Member Function Documentation

◆ Accept()

◆ AddAlternative()

◆ alternatives()

◆ AssertGuardsMentionRegisters()

◆ being_calculated()

◆ CalculatePreloadCharacters()

◆ EatsAtLeast()

◆ EatsAtLeastHelper()

◆ Emit()

◆ EmitChoices()

◆ EmitGreedyLoop()

◆ EmitOptimizedUnanchoredSearch()

◆ EmitOutOfLineContinuation()

◆ FillInBMInfo()

◆ FilterOneByte()

◆ GenerateGuard()

◆ GetQuickCheckDetails()

◆ GetTable()

◆ GreedyLoopTextLengthForAlternative()

◆ not_at_start()

◆ set_being_calculated()

◆ set_not_at_start()

◆ SetUpPreLoad()

◆ try_to_emit_quick_check_for_alternative()

Friends And Related Function Documentation

◆ Analysis

◆ DispatchTableConstructor

Member Data Documentation

◆ alternatives_

◆ being_calculated_

◆ not_at_start_

◆ table_