re2::DFA Class Reference

Classes
class	RWLocker
struct	SearchParams
struct	StartInfo
struct	State
struct	StateEqual
struct	StateHash
class	StateSaver
class	Workq

Public Types
enum	{   kByteEndText = 256, kFlagEmptyMask = 0xFF, kFlagMatch = 0x0100, kFlagLastWord = 0x0200,   kFlagNeedShift = 16 }
enum	{   kByteEndText = 256, kFlagEmptyMask = 0xFF, kFlagMatch = 0x0100, kFlagLastWord = 0x0200,   kFlagNeedShift = 16 }
typedef std::unordered_set< State *, StateHash, StateEqual >	StateSet
typedef std::unordered_set< State *, StateHash, StateEqual >	StateSet

Public Member Functions
int	BuildAllStates (const Prog::DFAStateCallback &cb)
int	BuildAllStates (const Prog::DFAStateCallback &cb)
	DFA (Prog *prog, Prog::MatchKind kind, int64_t max_mem)
	DFA (Prog *prog, Prog::MatchKind kind, int64_t max_mem)
Prog::MatchKind	kind ()
Prog::MatchKind	kind ()
bool	ok () const
bool	ok () const
bool	PossibleMatchRange (std::string *min, std::string *max, int maxlen)
bool	PossibleMatchRange (std::string *min, std::string *max, int maxlen)
bool	Search (const StringPiece &text, const StringPiece &context, bool anchored, bool want_earliest_match, bool run_forward, bool *failed, const char **ep, SparseSet *matches)
bool	Search (const StringPiece &text, const StringPiece &context, bool anchored, bool want_earliest_match, bool run_forward, bool *failed, const char **ep, SparseSet *matches)
	~DFA ()
	~DFA ()

Private Types
enum	{ kFbUnknown = -1, kFbNone = -2 }
enum	{   kStartBeginText = 0, kStartBeginLine = 2, kStartAfterWordChar = 4, kStartAfterNonWordChar = 6,   kMaxStart = 8, kStartAnchored = 1 }
enum	{   kStartBeginText = 0, kStartBeginLine = 2, kStartAfterWordChar = 4, kStartAfterNonWordChar = 6,   kMaxStart = 8, kStartAnchored = 1 }
using	CacheMutex = Mutex

Private Member Functions
void	AddToQueue (Workq *q, int id, uint32_t flag)
void	AddToQueue (Workq *q, int id, uint32_t flag)
bool	AnalyzeSearch (SearchParams *params)
bool	AnalyzeSearch (SearchParams *params)
bool	AnalyzeSearchHelper (SearchParams *params, StartInfo *info, uint32_t flags)
bool	AnalyzeSearchHelper (SearchParams *params, StartInfo *info, uint32_t flags)
int	ByteMap (int c)
int	ByteMap (int c)
State *	CachedState (int *inst, int ninst, uint32_t flag)
State *	CachedState (int *inst, int ninst, uint32_t flag)
void	ClearCache ()
void	ClearCache ()
	DFA (const DFA &)=delete
bool	FastSearchLoop (SearchParams *params)
bool	FastSearchLoop (SearchParams *params)
template<bool can_prefix_accel, bool want_earliest_match, bool run_forward>
bool	InlinedSearchLoop (SearchParams *params)
bool	InlinedSearchLoop (SearchParams *params, bool have_first_byte, bool want_earliest_match, bool run_forward)
DFA &	operator= (const DFA &)=delete
void	ResetCache (RWLocker *cache_lock)
void	ResetCache (RWLocker *cache_lock)
State *	RunStateOnByte (State *, int)
State *	RunStateOnByte (State *, int)
State *	RunStateOnByteUnlocked (State *, int)
State *	RunStateOnByteUnlocked (State *, int)
void	RunWorkqOnByte (Workq *q, Workq *nq, int c, uint32_t flag, bool *ismatch)
void	RunWorkqOnByte (Workq *q, Workq *nq, int c, uint32_t flag, bool *ismatch)
void	RunWorkqOnEmptyString (Workq *q, Workq *nq, uint32_t flag)
void	RunWorkqOnEmptyString (Workq *q, Workq *nq, uint32_t flag)
bool	SearchFFF (SearchParams *params)
bool	SearchFFF (SearchParams *params)
bool	SearchFFT (SearchParams *params)
bool	SearchFFT (SearchParams *params)
bool	SearchFTF (SearchParams *params)
bool	SearchFTF (SearchParams *params)
bool	SearchFTT (SearchParams *params)
bool	SearchFTT (SearchParams *params)
bool	SearchTFF (SearchParams *params)
bool	SearchTFF (SearchParams *params)
bool	SearchTFT (SearchParams *params)
bool	SearchTFT (SearchParams *params)
bool	SearchTTF (SearchParams *params)
bool	SearchTTF (SearchParams *params)
bool	SearchTTT (SearchParams *params)
bool	SearchTTT (SearchParams *params)
bool	SlowSearchLoop (SearchParams *params)
void	StateToWorkq (State *s, Workq *q)
void	StateToWorkq (State *s, Workq *q)
State *	WorkqToCachedState (Workq *q, Workq *mq, uint32_t flag)
State *	WorkqToCachedState (Workq *q, Workq *mq, uint32_t flag)

Static Private Member Functions
static std::string	DumpState (State *state)
static std::string	DumpState (State *state)
static std::string	DumpWorkq (Workq *q)
static std::string	DumpWorkq (Workq *q)

Private Attributes
CacheMutex	cache_mutex_
Mutex	cache_mutex_
bool	init_failed_
Prog::MatchKind	kind_
int64_t	mem_budget_
Mutex	mutex_
Prog *	prog_
Workq *	q0_
Workq *	q1_
PODArray< int >	stack_
StartInfo	start_ [kMaxStart]
int64_t	state_budget_
StateSet	state_cache_

Detailed Description

Definition at line 77 of file bloaty/third_party/re2/re2/dfa.cc.

Member Typedef Documentation

CacheMutex

using re2::DFA::CacheMutex = Mutex

private

Definition at line 175 of file re2/re2/dfa.cc.

StateSet [1/2]

typedef std::unordered_set<State*, StateHash, StateEqual> re2::DFA::StateSet

Definition at line 171 of file re2/re2/dfa.cc.

StateSet [2/2]

typedef std::unordered_set<State*, StateHash, StateEqual> re2::DFA::StateSet

Definition at line 177 of file bloaty/third_party/re2/re2/dfa.cc.

Member Enumeration Documentation

anonymous enum

anonymous enum

Enumerator
kByteEndText
kFlagEmptyMask
kFlagMatch
kFlagLastWord
kFlagNeedShift

Definition at line 140 of file bloaty/third_party/re2/re2/dfa.cc.

anonymous enum

anonymous enum

private

Enumerator
kFbUnknown
kFbNone

Definition at line 181 of file bloaty/third_party/re2/re2/dfa.cc.

anonymous enum

anonymous enum

private

Enumerator
kStartBeginText
kStartBeginLine
kStartAfterWordChar
kStartAfterNonWordChar
kMaxStart
kStartAnchored

Definition at line 186 of file bloaty/third_party/re2/re2/dfa.cc.

anonymous enum

anonymous enum

Enumerator
kByteEndText
kFlagEmptyMask
kFlagMatch
kFlagLastWord
kFlagNeedShift

Definition at line 134 of file re2/re2/dfa.cc.

anonymous enum

anonymous enum

private

Enumerator
kStartBeginText
kStartBeginLine
kStartAfterWordChar
kStartAfterNonWordChar
kMaxStart
kStartAnchored

Definition at line 177 of file re2/re2/dfa.cc.

Constructor & Destructor Documentation

DFA() [1/3]

re2::DFA::DFA	(	Prog *	prog,
		Prog::MatchKind	kind,
		int64_t	max_mem
	)

Definition at line 437 of file bloaty/third_party/re2/re2/dfa.cc.

~DFA() [1/2]

re2::DFA::~DFA

(

)

Definition at line 486 of file bloaty/third_party/re2/re2/dfa.cc.

DFA() [2/3]

re2::DFA::DFA	(	Prog *	prog,
		Prog::MatchKind	kind,
		int64_t	max_mem
	)

~DFA() [2/2]

re2::DFA::~DFA

(

)

DFA() [3/3]

re2::DFA::DFA ( const DFA &  )

privatedelete

Member Function Documentation

AddToQueue() [1/2]

void re2::DFA::AddToQueue ( Workq *  q, int  id, uint32_t  flag  )

private

AddToQueue() [2/2]

void re2::DFA::AddToQueue ( Workq *  q, int  id, uint32_t  flag  )

private

Definition at line 833 of file bloaty/third_party/re2/re2/dfa.cc.

AnalyzeSearch() [1/2]

bool re2::DFA::AnalyzeSearch ( SearchParams *  params )

private

AnalyzeSearch() [2/2]

bool re2::DFA::AnalyzeSearch ( SearchParams *  params )

private

Definition at line 1646 of file bloaty/third_party/re2/re2/dfa.cc.

AnalyzeSearchHelper() [1/2]

bool re2::DFA::AnalyzeSearchHelper ( SearchParams *  params, StartInfo *  info, uint32_t  flags  )

private

AnalyzeSearchHelper() [2/2]

bool re2::DFA::AnalyzeSearchHelper ( SearchParams *  params, StartInfo *  info, uint32_t  flags  )

private

Definition at line 1717 of file bloaty/third_party/re2/re2/dfa.cc.

BuildAllStates() [1/2]

int re2::DFA::BuildAllStates

(

const Prog::DFAStateCallback &

cb

)

BuildAllStates() [2/2]

int re2::DFA::BuildAllStates

(

const Prog::DFAStateCallback &

cb

)

Definition at line 1932 of file bloaty/third_party/re2/re2/dfa.cc.

ByteMap() [1/2]

int re2::DFA::ByteMap ( int  c )

inlineprivate

Definition at line 317 of file re2/re2/dfa.cc.

ByteMap() [2/2]

int re2::DFA::ByteMap ( int  c )

inlineprivate

Definition at line 334 of file bloaty/third_party/re2/re2/dfa.cc.

CachedState() [1/2]

State* re2::DFA::CachedState ( int *  inst, int  ninst, uint32_t  flag  )

private

CachedState() [2/2]

DFA::State * re2::DFA::CachedState ( int *  inst, int  ninst, uint32_t  flag  )

private

Definition at line 747 of file bloaty/third_party/re2/re2/dfa.cc.

ClearCache() [1/2]

void re2::DFA::ClearCache ( )

private

ClearCache() [2/2]

void re2::DFA::ClearCache ( )

private

Definition at line 799 of file bloaty/third_party/re2/re2/dfa.cc.

DumpState() [1/2]

static std::string re2::DFA::DumpState ( State *  state )

staticprivate

DumpState() [2/2]

std::string re2::DFA::DumpState ( State *  state )

staticprivate

Definition at line 523 of file bloaty/third_party/re2/re2/dfa.cc.

DumpWorkq() [1/2]

static std::string re2::DFA::DumpWorkq ( Workq *  q )

staticprivate

DumpWorkq() [2/2]

std::string re2::DFA::DumpWorkq ( Workq *  q )

staticprivate

Definition at line 507 of file bloaty/third_party/re2/re2/dfa.cc.

FastSearchLoop() [1/2]

bool re2::DFA::FastSearchLoop ( SearchParams *  params )

private

FastSearchLoop() [2/2]

bool re2::DFA::FastSearchLoop ( SearchParams *  params )

private

Definition at line 1598 of file bloaty/third_party/re2/re2/dfa.cc.

InlinedSearchLoop() [1/2]

template<bool can_prefix_accel, bool want_earliest_match, bool run_forward>

bool re2::DFA::InlinedSearchLoop ( SearchParams *  params )

inlineprivate

Definition at line 1327 of file re2/re2/dfa.cc.

InlinedSearchLoop() [2/2]

bool re2::DFA::InlinedSearchLoop ( SearchParams *  params, bool  have_first_byte, bool  want_earliest_match, bool  run_forward  )

inlineprivate

Definition at line 1326 of file bloaty/third_party/re2/re2/dfa.cc.

kind() [1/2]

Prog::MatchKind re2::DFA::kind ( )

inline

Definition at line 76 of file re2/re2/dfa.cc.

kind() [2/2]

Prog::MatchKind re2::DFA::kind ( )

inline

Definition at line 82 of file bloaty/third_party/re2/re2/dfa.cc.

ok() [1/2]

bool re2::DFA::ok ( ) const

inline

Definition at line 75 of file re2/re2/dfa.cc.

ok() [2/2]

bool re2::DFA::ok ( ) const

inline

Definition at line 81 of file bloaty/third_party/re2/re2/dfa.cc.

operator=()

DFA& re2::DFA::operator= ( const DFA &  )

privatedelete

PossibleMatchRange() [1/2]

bool re2::DFA::PossibleMatchRange	(	std::string *	min,
		std::string *	max,
		int	maxlen
	)

PossibleMatchRange() [2/2]

bool re2::DFA::PossibleMatchRange	(	std::string *	min,
		std::string *	max,
		int	maxlen
	)

Definition at line 2010 of file bloaty/third_party/re2/re2/dfa.cc.

ResetCache() [1/2]

void re2::DFA::ResetCache ( RWLocker *  cache_lock )

private

ResetCache() [2/2]

void re2::DFA::ResetCache ( RWLocker *  cache_lock )

private

Definition at line 1170 of file bloaty/third_party/re2/re2/dfa.cc.

RunStateOnByte() [1/2]

State* re2::DFA::RunStateOnByte ( State *  , int    )

private

RunStateOnByte() [2/2]

DFA::State * re2::DFA::RunStateOnByte ( State *  state, int  c  )

private

Definition at line 1006 of file bloaty/third_party/re2/re2/dfa.cc.

RunStateOnByteUnlocked() [1/2]

State* re2::DFA::RunStateOnByteUnlocked ( State *  , int    )

private

RunStateOnByteUnlocked() [2/2]

DFA::State * re2::DFA::RunStateOnByteUnlocked ( State *  state, int  c  )

private

Definition at line 998 of file bloaty/third_party/re2/re2/dfa.cc.

RunWorkqOnByte() [1/2]

void re2::DFA::RunWorkqOnByte ( Workq *  q, Workq *  nq, int  c, uint32_t  flag, bool *  ismatch  )

private

RunWorkqOnByte() [2/2]

void re2::DFA::RunWorkqOnByte ( Workq *  q, Workq *  nq, int  c, uint32_t  flag, bool *  ismatch  )

private

Definition at line 947 of file bloaty/third_party/re2/re2/dfa.cc.

RunWorkqOnEmptyString() [1/2]

void re2::DFA::RunWorkqOnEmptyString ( Workq *  q, Workq *  nq, uint32_t  flag  )

private

RunWorkqOnEmptyString() [2/2]

void re2::DFA::RunWorkqOnEmptyString ( Workq *  q, Workq *  nq, uint32_t  flag  )

private

Definition at line 933 of file bloaty/third_party/re2/re2/dfa.cc.

Search() [1/2]

bool re2::DFA::Search	(	const StringPiece &	text,
		const StringPiece &	context,
		bool	anchored,
		bool	want_earliest_match,
		bool	run_forward,
		bool *	failed,
		const char **	ep,
		SparseSet *	matches
	)

Search() [2/2]

bool re2::DFA::Search	(	const StringPiece &	text,
		const StringPiece &	context,
		bool	anchored,
		bool	want_earliest_match,
		bool	run_forward,
		bool *	failed,
		const char **	ep,
		SparseSet *	matches
	)

Definition at line 1765 of file bloaty/third_party/re2/re2/dfa.cc.

SearchFFF() [1/2]

bool re2::DFA::SearchFFF ( SearchParams *  params )

private

SearchFFF() [2/2]

bool re2::DFA::SearchFFF ( SearchParams *  params )

private

Definition at line 1563 of file bloaty/third_party/re2/re2/dfa.cc.

SearchFFT() [1/2]

bool re2::DFA::SearchFFT ( SearchParams *  params )

private

SearchFFT() [2/2]

bool re2::DFA::SearchFFT ( SearchParams *  params )

private

Definition at line 1566 of file bloaty/third_party/re2/re2/dfa.cc.

SearchFTF() [1/2]

bool re2::DFA::SearchFTF ( SearchParams *  params )

private

SearchFTF() [2/2]

bool re2::DFA::SearchFTF ( SearchParams *  params )

private

Definition at line 1569 of file bloaty/third_party/re2/re2/dfa.cc.

SearchFTT() [1/2]

bool re2::DFA::SearchFTT ( SearchParams *  params )

private

SearchFTT() [2/2]

bool re2::DFA::SearchFTT ( SearchParams *  params )

private

Definition at line 1572 of file bloaty/third_party/re2/re2/dfa.cc.

SearchTFF() [1/2]

bool re2::DFA::SearchTFF ( SearchParams *  params )

private

SearchTFF() [2/2]

bool re2::DFA::SearchTFF ( SearchParams *  params )

private

Definition at line 1575 of file bloaty/third_party/re2/re2/dfa.cc.

SearchTFT() [1/2]

bool re2::DFA::SearchTFT ( SearchParams *  params )

private

SearchTFT() [2/2]

bool re2::DFA::SearchTFT ( SearchParams *  params )

private

Definition at line 1578 of file bloaty/third_party/re2/re2/dfa.cc.

SearchTTF() [1/2]

bool re2::DFA::SearchTTF ( SearchParams *  params )

private

SearchTTF() [2/2]

bool re2::DFA::SearchTTF ( SearchParams *  params )

private

Definition at line 1581 of file bloaty/third_party/re2/re2/dfa.cc.

SearchTTT() [1/2]

bool re2::DFA::SearchTTT ( SearchParams *  params )

private

SearchTTT() [2/2]

bool re2::DFA::SearchTTT ( SearchParams *  params )

private

Definition at line 1584 of file bloaty/third_party/re2/re2/dfa.cc.

SlowSearchLoop()

bool re2::DFA::SlowSearchLoop ( SearchParams *  params )

private

Definition at line 1589 of file bloaty/third_party/re2/re2/dfa.cc.

StateToWorkq() [1/2]

void re2::DFA::StateToWorkq ( State *  s, Workq *  q  )

private

StateToWorkq() [2/2]

void re2::DFA::StateToWorkq ( State *  s, Workq *  q  )

private

Definition at line 817 of file bloaty/third_party/re2/re2/dfa.cc.

WorkqToCachedState() [1/2]

State* re2::DFA::WorkqToCachedState ( Workq *  q, Workq *  mq, uint32_t  flag  )

private

WorkqToCachedState() [2/2]

DFA::State * re2::DFA::WorkqToCachedState ( Workq *  q, Workq *  mq, uint32_t  flag  )

private

Definition at line 609 of file bloaty/third_party/re2/re2/dfa.cc.

Member Data Documentation

cache_mutex_ [1/2]

CacheMutex re2::DFA::cache_mutex_

private

Definition at line 341 of file re2/re2/dfa.cc.

cache_mutex_ [2/2]

Mutex re2::DFA::cache_mutex_

private

Definition at line 358 of file bloaty/third_party/re2/re2/dfa.cc.

init_failed_

bool re2::DFA::init_failed_

private

Definition at line 343 of file bloaty/third_party/re2/re2/dfa.cc.

kind_

Prog::MatchKind re2::DFA::kind_

private

Definition at line 342 of file bloaty/third_party/re2/re2/dfa.cc.

mem_budget_

int64_t re2::DFA::mem_budget_

private

Definition at line 359 of file bloaty/third_party/re2/re2/dfa.cc.

mutex_

Mutex re2::DFA::mutex_

private

Definition at line 345 of file bloaty/third_party/re2/re2/dfa.cc.

prog_

Prog * re2::DFA::prog_

private

Definition at line 341 of file bloaty/third_party/re2/re2/dfa.cc.

q0_

Workq * re2::DFA::q0_

private

Definition at line 348 of file bloaty/third_party/re2/re2/dfa.cc.

q1_

Workq * re2::DFA::q1_

private

Definition at line 349 of file bloaty/third_party/re2/re2/dfa.cc.

stack_

PODArray< int > re2::DFA::stack_

private

Definition at line 350 of file bloaty/third_party/re2/re2/dfa.cc.

start_

StartInfo re2::DFA::start_

private

Definition at line 362 of file bloaty/third_party/re2/re2/dfa.cc.

state_budget_

int64_t re2::DFA::state_budget_

private

Definition at line 360 of file bloaty/third_party/re2/re2/dfa.cc.

state_cache_

StateSet re2::DFA::state_cache_

private

Definition at line 361 of file bloaty/third_party/re2/re2/dfa.cc.

---

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

• bloaty/third_party/re2/re2/dfa.cc