Flutter Engine
The Flutter Engine
Public Member Functions | Static Public Attributes | Protected Types | Protected Member Functions | Protected Attributes | List of all members
dart::RegExpNode Class Referenceabstract

#include <regexp.h>

Inheritance diagram for dart::RegExpNode:
dart::ZoneAllocated dart::ChoiceNode dart::EndNode dart::SeqRegExpNode dart::LoopChoiceNode dart::NegativeLookaroundChoiceNode dart::NegativeSubmatchSuccess dart::ActionNode dart::AssertionNode dart::BackReferenceNode dart::TextNode

Public Member Functions

 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)
 

Static Public Attributes

static constexpr intptr_t kNodeIsTooComplexForGreedyLoops = -1
 
static constexpr intptr_t kRecursionBudget = 200
 
static constexpr intptr_t kMaxCopiesCodeGenerated = 10
 

Protected Types

enum  LimitResult { DONE , CONTINUE }
 

Protected Member Functions

LimitResult LimitVersions (RegExpCompiler *compiler, Trace *trace)
 
void set_bm_info (bool not_at_start, BoyerMooreLookahead *bm)
 

Protected Attributes

RegExpNode * replacement_
 

Detailed Description

Definition at line 384 of file regexp.h.

Member Enumeration Documentation

◆ LimitResult

enum dart::RegExpNode::LimitResult
protected
Enumerator
DONE 
CONTINUE 

Definition at line 486 of file regexp.h.

486{ DONE, CONTINUE };

Constructor & Destructor Documentation

◆ RegExpNode()

dart::RegExpNode::RegExpNode ( Zone *  zone)
inlineexplicit

Definition at line 386 of file regexp.h.

387 : replacement_(nullptr), trace_count_(0), zone_(zone) {
388 bm_info_[0] = bm_info_[1] = nullptr;
389 }
dart::RegExpNode::replacement_
RegExpNode * replacement_
Definition: regexp.h:487
dart::RegExpNode::zone
Zone * zone() const
Definition: regexp.h:483

◆ ~RegExpNode()

dart::RegExpNode::~RegExpNode ( )
virtual

Definition at line 1429 of file regexp.cc.

1429{}

Member Function Documentation

◆ Accept()

virtual void dart::RegExpNode::Accept ( NodeVisitor *  visitor)
pure virtual

Implemented in dart::ActionNode, dart::TextNode, dart::AssertionNode, dart::BackReferenceNode, dart::EndNode, dart::ChoiceNode, and dart::LoopChoiceNode.

◆ bm_info()

BoyerMooreLookahead * dart::RegExpNode::bm_info ( bool  not_at_start)
inline

Definition at line 479 of file regexp.h.

479 {
480 return bm_info_[not_at_start ? 1 : 0];
481 }

◆ EatsAtLeast()

virtual intptr_t dart::RegExpNode::EatsAtLeast ( intptr_t  still_to_find,
intptr_t  budget,
bool  not_at_start 
)
pure virtual

Implemented in dart::ActionNode, dart::TextNode, dart::AssertionNode, dart::ChoiceNode, dart::NegativeLookaroundChoiceNode, dart::LoopChoiceNode, dart::BackReferenceNode, and dart::EndNode.

◆ Emit()

virtual void dart::RegExpNode::Emit ( RegExpCompiler *  compiler,
Trace *  trace 
)
pure virtual

Implemented in dart::ActionNode, dart::TextNode, dart::AssertionNode, dart::BackReferenceNode, dart::EndNode, dart::NegativeSubmatchSuccess, dart::ChoiceNode, and dart::LoopChoiceNode.

◆ EmitQuickCheck()

bool dart::RegExpNode::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 
)

Definition at line 1621 of file regexp.cc.

1627 {
1628 if (details->characters() == 0) return false;
1629 GetQuickCheckDetails(details, compiler, 0,
1630 trace->at_start() == Trace::FALSE_VALUE);
1631 if (details->cannot_match()) return false;
1632 if (!details->Rationalize(compiler->one_byte())) return false;
1633 ASSERT(details->characters() == 1 ||
1634 compiler->macro_assembler()->CanReadUnaligned());
1635 uint32_t mask = details->mask();
1636 uint32_t value = details->value();
1637
1638 RegExpMacroAssembler* assembler = compiler->macro_assembler();
1639
1640 if (trace->characters_preloaded() != details->characters()) {
1641 ASSERT(trace->cp_offset() == bounds_check_trace->cp_offset());
1642 // We are attempting to preload the minimum number of characters
1643 // any choice would eat, so if the bounds check fails, then none of the
1644 // choices can succeed, so we can just immediately backtrack, rather
1645 // than go to the next choice.
1646 assembler->LoadCurrentCharacter(
1647 trace->cp_offset(), bounds_check_trace->backtrack(),
1648 !preload_has_checked_bounds, details->characters());
1649 }
1650
1651 bool need_mask = true;
1652
1653 if (details->characters() == 1) {
1654 // If number of characters preloaded is 1 then we used a byte or 16 bit
1655 // load so the value is already masked down.
1656 uint32_t char_mask;
1657 if (compiler->one_byte()) {
1658 char_mask = Symbols::kMaxOneCharCodeSymbol;
1659 } else {
1660 char_mask = Utf16::kMaxCodeUnit;
1661 }
1662 if ((mask & char_mask) == char_mask) need_mask = false;
1663 mask &= char_mask;
1664 } else {
1665 // For 2-character preloads in one-byte mode or 1-character preloads in
1666 // two-byte mode we also use a 16 bit load with zero extend.
1667 if (details->characters() == 2 && compiler->one_byte()) {
1668 if ((mask & 0xffff) == 0xffff) need_mask = false;
1669 } else if (details->characters() == 1 && !compiler->one_byte()) {
1670 if ((mask & 0xffff) == 0xffff) need_mask = false;
1671 } else {
1672 if (mask == 0xffffffff) need_mask = false;
1673 }
1674 }
1675
1676 if (fall_through_on_failure) {
1677 if (need_mask) {
1678 assembler->CheckCharacterAfterAnd(value, mask, on_possible_success);
1679 } else {
1680 assembler->CheckCharacter(value, on_possible_success);
1681 }
1682 } else {
1683 if (need_mask) {
1684 assembler->CheckNotCharacterAfterAnd(value, mask, trace->backtrack());
1685 } else {
1686 assembler->CheckNotCharacter(value, trace->backtrack());
1687 }
1688 }
1689 return true;
1690}
dart::RegExpNode::GetQuickCheckDetails
virtual void GetQuickCheckDetails(QuickCheckDetails *details, RegExpCompiler *compiler, intptr_t characters_filled_in, bool not_at_start)=0
dart::Symbols::kMaxOneCharCodeSymbol
@ kMaxOneCharCodeSymbol
Definition: symbols.h:577
dart::Trace::FALSE_VALUE
@ FALSE_VALUE
Definition: regexp.h:1206
dart::Utf16::kMaxCodeUnit
static constexpr int32_t kMaxCodeUnit
Definition: unicode.h:158
ASSERT
#define ASSERT(E)
Definition: entrypoints_verification_test.cc:25
value
uint8_t value
Definition: fl_standard_message_codec.cc:36

◆ FillInBMInfo()

virtual void dart::RegExpNode::FillInBMInfo ( intptr_t  offset,
intptr_t  budget,
BoyerMooreLookahead *  bm,
bool  not_at_start 
)
inlinevirtual

Reimplemented in dart::SeqRegExpNode, dart::ActionNode, dart::TextNode, dart::AssertionNode, dart::BackReferenceNode, dart::EndNode, dart::ChoiceNode, dart::NegativeLookaroundChoiceNode, and dart::LoopChoiceNode.

Definition at line 439 of file regexp.h.

442 {
443 UNREACHABLE();
444 }
UNREACHABLE
#define UNREACHABLE()
Definition: assert.h:248

◆ FilterOneByte()

virtual RegExpNode * dart::RegExpNode::FilterOneByte ( intptr_t  depth)
inlinevirtual

Reimplemented in dart::SeqRegExpNode, dart::TextNode, dart::ChoiceNode, dart::NegativeLookaroundChoiceNode, and dart::LoopChoiceNode.

Definition at line 449 of file regexp.h.

449{ return this; }

◆ GetQuickCheckDetails()

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

Implemented in dart::TextNode, dart::BackReferenceNode, dart::EndNode, dart::ChoiceNode, dart::NegativeLookaroundChoiceNode, dart::LoopChoiceNode, dart::ActionNode, and dart::AssertionNode.

◆ GetSuccessorOfOmnivorousTextNode()

virtual RegExpNode * dart::RegExpNode::GetSuccessorOfOmnivorousTextNode ( RegExpCompiler *  compiler)
inlinevirtual

Reimplemented in dart::TextNode.

Definition at line 428 of file regexp.h.

429 {
430 return nullptr;
431 }

◆ GreedyLoopTextLength()

virtual intptr_t dart::RegExpNode::GreedyLoopTextLength ( )
inlinevirtual

Reimplemented in dart::ActionNode, and dart::TextNode.

Definition at line 423 of file regexp.h.

423 {
424 return kNodeIsTooComplexForGreedyLoops;
425 }
dart::RegExpNode::kNodeIsTooComplexForGreedyLoops
static constexpr intptr_t kNodeIsTooComplexForGreedyLoops
Definition: regexp.h:422

◆ info()

NodeInfo * dart::RegExpNode::info ( )
inline

Definition at line 477 of file regexp.h.

477{ return &info_; }

◆ label()

BlockLabel * dart::RegExpNode::label ( )
inline

Definition at line 469 of file regexp.h.

469{ return &label_; }

◆ LimitVersions()

RegExpNode::LimitResult dart::RegExpNode::LimitVersions ( RegExpCompiler *  compiler,
Trace *  trace 
)
protected

Definition at line 1431 of file regexp.cc.

1432 {
1433 // If we are generating a greedy loop then don't stop and don't reuse code.
1434 if (trace->stop_node() != nullptr) {
1435 return CONTINUE;
1436 }
1437
1438 RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
1439 if (trace->is_trivial()) {
1440 if (label_.is_bound()) {
1441 // We are being asked to generate a generic version, but that's already
1442 // been done so just go to it.
1443 macro_assembler->GoTo(&label_);
1444 return DONE;
1445 }
1446 if (compiler->recursion_depth() >= RegExpCompiler::kMaxRecursion) {
1447 // To avoid too deep recursion we push the node to the work queue and just
1448 // generate a goto here.
1449 compiler->AddWork(this);
1450 macro_assembler->GoTo(&label_);
1451 return DONE;
1452 }
1453 // Generate generic version of the node and bind the label for later use.
1454 macro_assembler->BindBlock(&label_);
1455 return CONTINUE;
1456 }
1457
1458 // We are being asked to make a non-generic version. Keep track of how many
1459 // non-generic versions we generate so as not to overdo it.
1460 trace_count_++;
1461 if (kRegexpOptimization && trace_count_ < kMaxCopiesCodeGenerated &&
1462 compiler->recursion_depth() <= RegExpCompiler::kMaxRecursion) {
1463 return CONTINUE;
1464 }
1465
1466 // If we get here code has been generated for this node too many times or
1467 // recursion is too deep. Time to switch to a generic version. The code for
1468 // generic versions above can handle deep recursion properly.
1469 trace->Flush(compiler, this);
1470 return DONE;
1471}
dart::BlockLabel::is_bound
bool is_bound() const
Definition: regexp_assembler.h:44
dart::RegExpCompiler::kMaxRecursion
static constexpr intptr_t kMaxRecursion
Definition: regexp.cc:336
dart::RegExpNode::kMaxCopiesCodeGenerated
static constexpr intptr_t kMaxCopiesCodeGenerated
Definition: regexp.h:475
dart::kRegexpOptimization
static constexpr bool kRegexpOptimization
Definition: regexp.cc:31

◆ replacement()

RegExpNode * dart::RegExpNode::replacement ( )
inline

Definition at line 451 of file regexp.h.

451 {
452 ASSERT(info()->replacement_calculated);
453 return replacement_;
454 }
dart::RegExpNode::info
NodeInfo * info()
Definition: regexp.h:477

◆ SaveBMInfo()

void dart::RegExpNode::SaveBMInfo ( BoyerMooreLookahead *  bm,
bool  not_at_start,
intptr_t  offset 
)
inline

Definition at line 465 of file regexp.h.

465 {
466 if (offset == 0) set_bm_info(not_at_start, bm);
467 }
dart::RegExpNode::set_bm_info
void set_bm_info(bool not_at_start, BoyerMooreLookahead *bm)
Definition: regexp.h:491
offset
SeparatedVector2 offset
Definition: stroke_path_geometry.cc:311

◆ set_bm_info()

void dart::RegExpNode::set_bm_info ( bool  not_at_start,
BoyerMooreLookahead *  bm 
)
inlineprotected

Definition at line 491 of file regexp.h.

491 {
492 bm_info_[not_at_start ? 1 : 0] = bm;
493 }

◆ set_replacement()

RegExpNode * dart::RegExpNode::set_replacement ( RegExpNode *  replacement)
inline

Definition at line 455 of file regexp.h.

455 {
456 info()->replacement_calculated = true;
457 replacement_ = replacement;
458 return replacement; // For convenience.
459 }
dart::RegExpNode::replacement
RegExpNode * replacement()
Definition: regexp.h:451
dart::NodeInfo::replacement_calculated
bool replacement_calculated
Definition: regexp.h:334

◆ zone()

Zone * dart::RegExpNode::zone ( ) const
inline

Definition at line 483 of file regexp.h.

483{ return zone_; }

Member Data Documentation

◆ kMaxCopiesCodeGenerated

constexpr intptr_t dart::RegExpNode::kMaxCopiesCodeGenerated = 10
staticconstexpr

Definition at line 475 of file regexp.h.

◆ kNodeIsTooComplexForGreedyLoops

constexpr intptr_t dart::RegExpNode::kNodeIsTooComplexForGreedyLoops = -1
staticconstexpr

Definition at line 422 of file regexp.h.

◆ kRecursionBudget

constexpr intptr_t dart::RegExpNode::kRecursionBudget = 200
staticconstexpr

Definition at line 438 of file regexp.h.

◆ replacement_

RegExpNode* dart::RegExpNode::replacement_
protected

Definition at line 487 of file regexp.h.

The documentation for this class was generated from the following files:
Generated on Sun Jun 23 2024 21:59:31 for Flutter Engine by doxygen 1.9.4