greenplumn CStateMachine 源码

greenplumn CStateMachine 代码

文件路径：/src/backend/gporca/libgpopt/include/gpopt/base/CStateMachine.h

//---------------------------------------------------------------------------
//	Greenplum Database
//	Copyright (C) 2009 Greenplum, Inc.
//
//	@filename:
//		CStateMachine.h
//
//	@doc:
//		Basic FSM implementation;
//		This superclass provides the API and handles only the bookkeeping;
//
//		Each subclass has to provide a transition function which encodes
//		the actual state graph and determines validity of transitions;
//
//		Provides debug functionality to draw state diagram and validation
//		function to detect unreachable states.
//---------------------------------------------------------------------------
#ifndef GPOPT_CStateMachine_H
#define GPOPT_CStateMachine_H

#include "gpos/base.h"
#include "gpos/common/CEnumSet.h"
#include "gpos/types.h"

#ifdef GPOS_DEBUG
#include "gpos/common/CEnumSetIter.h"

// history of past N states/events
#define GPOPT_FSM_HISTORY 25u

#endif	// GPOS_DEBUG

// maximum length of names used for states and events
#define GPOPT_FSM_NAME_LENGTH 128

namespace gpopt
{
using namespace gpos;

//---------------------------------------------------------------------------
//	@class:
//		CStateMachine
//
//	@doc:
//		Abstract FSM which accepts events to manage state transitions;
//		Corresponds to a Moore Machine;
//
//---------------------------------------------------------------------------
template <class TEnumState, TEnumState tenumstateSentinel, class TEnumEvent,
		  TEnumEvent tenumeventSentinel>
class CStateMachine
{
private:
#ifdef GPOS_DEBUG
	// shorthand for sets and iterators
	using EsetStates = CEnumSet<TEnumState, tenumstateSentinel>;
	using EsetEvents = CEnumSet<TEnumEvent, tenumeventSentinel>;

	using EsetStatesIter = CEnumSetIter<TEnumState, tenumstateSentinel>;
	using EsetEventsIter = CEnumSetIter<TEnumEvent, tenumeventSentinel>;
#endif	// GPOS_DEBUG

	// current state
	TEnumState m_tenumstate;

	// flag indicating if the state machine is initialized
	BOOL m_fInit{false};

	// array of transitions
	TEnumEvent m_rgrgtenumeventTransitions[tenumstateSentinel]
										  [tenumstateSentinel];

#ifdef GPOS_DEBUG

#define GRAPHVIZ_SHAPE(shape, x) \
	"node [shape = " << shape << " ]; \"" << x << "\" ; node [shape = circle];"

#define GRAPHVIZ_DOUBLE_CIRCLE(x) GRAPHVIZ_SHAPE("doublecircle", x)
#define GRAPHVIZ_BOX(x) GRAPHVIZ_SHAPE("box", x)

	// state names
	const WCHAR *m_rgwszStates[tenumstateSentinel];

	// event names
	const WCHAR *m_rgwszEvents[tenumeventSentinel];

	// current index into history
	ULONG m_ulHistory{0};

	// state history
	TEnumState m_tenumstateHistory[GPOPT_FSM_HISTORY];

	// event history
	TEnumEvent m_tenumeventHistory[GPOPT_FSM_HISTORY];

	// track event
	void
	RecordHistory(TEnumEvent tenumevent, TEnumState tenumstate)
	{
		ULONG ulHistory = m_ulHistory % GPOPT_FSM_HISTORY;

		m_tenumeventHistory[ulHistory] = tenumevent;
		m_tenumstateHistory[ulHistory] = tenumstate;

		++m_ulHistory;
	}

	// resolve names for states
	const WCHAR *
	WszState(TEnumState tenumstate) const
	{
		GPOS_ASSERT(m_fInit);
		GPOS_ASSERT(0 <= tenumstate && tenumstate < tenumstateSentinel);

		return m_rgwszStates[tenumstate];
	}

	// resolve names for events
	const WCHAR *
	WszEvent(TEnumEvent tenumevent) const
	{
		GPOS_ASSERT(m_fInit);
		GPOS_ASSERT(0 <= tenumevent && tenumevent < tenumeventSentinel);

		return m_rgwszEvents[tenumevent];
	}

	// retrieve all states -- enum might have 'holes'
	void
	States(EsetStates *peset) const
	{
		for (ULONG ul = 0; ul < tenumstateSentinel; ul++)
		{
			(void) peset->ExchangeSet((TEnumState) ul);
		}
	}

	// determine all possible transitions between 2 given states
	void
	Transitions(TEnumState tenumstateOld, TEnumState tenumstateNew,
				EsetEvents *peset) const
	{
		TEnumEvent tenumevent =
			m_rgrgtenumeventTransitions[tenumstateOld][tenumstateNew];
		if (tenumeventSentinel != tenumevent)
		{
			(void) peset->ExchangeSet(tenumevent);
		}
	}

	// shorthand for walker function type
	using PfWalker = void (*)(const CStateMachine *, TEnumState, TEnumState,
							  TEnumEvent, void *);

	// generic walker function, called for every edge in the graph
	void
	Walk(CMemoryPool *mp, PfWalker Pfpv, void *pvContext) const
	{
		// retrieve all states
		EsetStates *pesetStates = GPOS_NEW(mp) EsetStates(mp);
		States(pesetStates);

		// loop through all sink states
		EsetStatesIter esetIterSink(*pesetStates);
		while (esetIterSink.Advance())
		{
			TEnumState tenumstateSink = esetIterSink.TBit();

			// loop through all source states
			EsetStatesIter esetIterSource(*pesetStates);
			while (esetIterSource.Advance())
			{
				TEnumState tenumstateSource = esetIterSource.TBit();

				// for all pairs of states (source, sink)
				// compute possible transitions
				EsetEvents *pesetEvents = GPOS_NEW(mp) EsetEvents(mp);
				Transitions(tenumstateSource, tenumstateSink, pesetEvents);

				// loop through all connecting edges
				EsetEventsIter esetIterTrans(*pesetEvents);
				while (esetIterTrans.Advance())
				{
					// apply walker function
					Pfpv(this, tenumstateSource, tenumstateSink,
						 esetIterTrans.TBit(), pvContext);
				}

				pesetEvents->Release();
			}
		}

		pesetStates->Release();
	}

	// print function -- used with walker
	static void
	Diagram(const CStateMachine *psm, TEnumState tenumstateSource,
			TEnumState tenumstateSink, TEnumEvent tenumevent, void *pvContext)
	{
		IOstream &os = *(IOstream *) pvContext;

		os << "\"" << psm->WszState(tenumstateSource) << "\" -> \""
		   << psm->WszState(tenumstateSink) << "\" [ label = \""
		   << psm->WszEvent(tenumevent) << "\" ];" << std::endl;
	}


	// check for unreachable nodes -- used with walker
	static void
	Unreachable(const CStateMachine *, TEnumState tenumstateSource,
				TEnumState tenumstateSink, TEnumEvent, void *pvContext)
	{
		EsetStates &eset = *(EsetStates *) pvContext;

		if (tenumstateSource != tenumstateSink)
		{
			// reachable -- remove from set of unreachables
			(void) eset.ExchangeClear(tenumstateSink);
		}
	}
#endif	// GPOS_DEBUG

	// actual implementation of transition
	BOOL
	FAttemptTransition(TEnumState tenumstateOld, TEnumEvent tenumevent,
					   TEnumState &tenumstateNew) const
	{
		GPOS_ASSERT(tenumevent < tenumeventSentinel);
		GPOS_ASSERT(m_fInit);

		for (ULONG ulOuter = 0; ulOuter < tenumstateSentinel; ulOuter++)
		{
			if (m_rgrgtenumeventTransitions[tenumstateOld][ulOuter] ==
				tenumevent)
			{
#ifdef GPOS_DEBUG
				// make sure there isn't another transition possible for the same event
				for (ULONG ulInner = ulOuter + 1; ulInner < tenumstateSentinel;
					 ulInner++)
				{
					GPOS_ASSERT(
						m_rgrgtenumeventTransitions[tenumstateOld][ulInner] !=
						tenumevent);
				}
#endif	// GPOS_DEBUG

				tenumstateNew = (TEnumState) ulOuter;
				return true;
			}
		}

		return false;
	}

public:
	CStateMachine<TEnumState, tenumstateSentinel, TEnumEvent,
				  tenumeventSentinel>(
		const CStateMachine<TEnumState, tenumstateSentinel, TEnumEvent,
							tenumeventSentinel> &) = delete;

	// ctor
	CStateMachine<TEnumState, tenumstateSentinel, TEnumEvent,
				  tenumeventSentinel>()
		: m_tenumstate(TesInitial())
	{
		GPOS_ASSERT(0 < tenumstateSentinel && 0 < tenumeventSentinel &&
					(ULONG) tenumeventSentinel + 1 >=
						(ULONG) tenumstateSentinel);
	}

	// initialize state machine
	void
	Init(const TEnumEvent rgrgtenumeventTransitions[tenumstateSentinel]
												   [tenumstateSentinel]
#ifdef GPOS_DEBUG
		 ,
		 const WCHAR rgwszStates[tenumstateSentinel][GPOPT_FSM_NAME_LENGTH],
		 const WCHAR rgwszEvents[tenumeventSentinel][GPOPT_FSM_NAME_LENGTH]
#endif	// GPOS_DEBUG
	)
	{
		GPOS_ASSERT(!m_fInit);

		for (ULONG ulOuter = 0; ulOuter < tenumstateSentinel; ulOuter++)
		{
			for (ULONG ulInner = 0; ulInner < tenumstateSentinel; ulInner++)
			{
				m_rgrgtenumeventTransitions[ulOuter][ulInner] =
					rgrgtenumeventTransitions[ulOuter][ulInner];
			}
		}

#ifdef GPOS_DEBUG
		for (ULONG ul = 0; ul < tenumstateSentinel; ul++)
		{
			m_rgwszStates[ul] = rgwszStates[ul];
		}

		for (ULONG ul = 0; ul < tenumeventSentinel; ul++)
		{
			m_rgwszEvents[ul] = rgwszEvents[ul];
		}
#endif	// GPOS_DEBUG

		m_tenumstate = TesInitial();
		m_fInit = true;
	}

	// dtor
	~CStateMachine() = default;

	// attempt transition
	BOOL
	FTransition(TEnumEvent tenumevent, TEnumState &tenumstate)
	{
		TEnumState tenumstateNew;
		BOOL fSucceeded =
			FAttemptTransition(m_tenumstate, tenumevent, tenumstateNew);

		if (fSucceeded)
		{
			m_tenumstate = tenumstateNew;
#ifdef GPOS_DEBUG
			RecordHistory(tenumevent, m_tenumstate);
#endif	// GPOS_DEBUG
		}

		tenumstate = m_tenumstate;
		return fSucceeded;
	}

	// shorthand if current state and return value are not needed
	void
	Transition(TEnumEvent tenumevent)
	{
		TEnumState tenumstateDummy;
#ifdef GPOS_DEBUG
		BOOL fCheck =
#else
		(void)
#endif	// GPOS_DEBUG
			FTransition(tenumevent, tenumstateDummy);

		GPOS_ASSERT(fCheck && "Event rejected");
	}

	// inspect current state; to be used only in assertions
	TEnumState
	Estate() const
	{
		return m_tenumstate;
	}

	// get initial state
	TEnumState
	TesInitial() const
	{
		return (TEnumState) 0;
	}

	// get final state
	TEnumState
	TesFinal() const
	{
		return (TEnumState)(tenumstateSentinel - 1);
	}

	// reset state
	void
	Reset()
	{
		m_tenumstate = TesInitial();
		m_fInit = false;
	}

#ifdef GPOS_DEBUG
	// dump history
	IOstream &
	OsHistory(IOstream &os) const
	{
		ULONG ulElems = std::min(m_ulHistory, GPOPT_FSM_HISTORY);

		ULONG ulStart = m_ulHistory + 1;
		if (m_ulHistory < GPOPT_FSM_HISTORY)
		{
			// if we haven't rolled over, just start at 0
			ulStart = 0;
		}

		os << "State Machine History (" << (void *) this << ")" << std::endl;

		for (ULONG ul = 0; ul < ulElems; ul++)
		{
			ULONG ulPos = (ulStart + ul) % GPOPT_FSM_HISTORY;
			os << ul << ": " << WszEvent(m_tenumeventHistory[ulPos])
			   << " (event) -> " << WszState(m_tenumstateHistory[ulPos])
			   << " (state)" << std::endl;
		}

		return os;
	}

	// check for unreachable states
	BOOL
	FReachable(CMemoryPool *mp) const
	{
		TEnumState *pestate = nullptr;
		ULONG size = 0;
		Unreachable(mp, &pestate, &size);
		GPOS_DELETE_ARRAY(pestate);

		return (size == 0);
	}

	// compute array of unreachable states
	void
	Unreachable(CMemoryPool *mp, TEnumState **ppestate, ULONG *pulSize) const
	{
		GPOS_ASSERT(nullptr != ppestate);
		GPOS_ASSERT(nullptr != pulSize);

		// initialize output array
		*ppestate = GPOS_NEW_ARRAY(mp, TEnumState, tenumstateSentinel);
		for (ULONG ul = 0; ul < tenumstateSentinel; ul++)
		{
			(*ppestate)[ul] = tenumstateSentinel;
		}

		// mark all states unreachable at first
		EsetStates *peset = GPOS_NEW(mp) EsetStates(mp);
		States(peset);

		Walk(mp, Unreachable, peset);

		// store remaining states in output array
		EsetStatesIter esetIter(*peset);
		ULONG ul = 0;
		while (esetIter.Advance())
		{
			(*ppestate)[ul++] = esetIter.TBit();
		}
		*pulSize = ul;
		peset->Release();
	}

	// dump Moore diagram in graphviz format
	IOstream &
	OsDiagramToGraphviz(CMemoryPool *mp, IOstream &os,
						const WCHAR *wszTitle) const
	{
		os << "digraph " << wszTitle << " { " << std::endl
		   << GRAPHVIZ_DOUBLE_CIRCLE(WszState(TesInitial())) << std::endl;

		// get unreachable states
		EsetStates *peset = GPOS_NEW(mp) EsetStates(mp);
		States(peset);

		Walk(mp, Unreachable, peset);

		// print all unreachable nodes using BOXes
		EsetStatesIter esetIter(*peset);
		while (esetIter.Advance())
		{
			os << GRAPHVIZ_BOX(WszState(esetIter.TBit())) << std::endl;
		}
		peset->Release();

		// print the remainder of the diagram by writing all edges only;
		// nodes are implicit;
		Walk(mp, Diagram, &os);

		os << "} " << std::endl;
		return os;
	}

#endif	// GPOS_DEBUG

};	// class CStateMachine
}  // namespace gpopt



#endif	// !GPOPT_CStateMachine_H


// EOF

相关信息

greenplumn 源码目录

相关文章

greenplumn CAutoOptCtxt 源码

greenplumn CCTEInfo 源码

greenplumn CCTEMap 源码

greenplumn CCTEReq 源码

greenplumn CCastUtils 源码

greenplumn CColConstraintsArrayMapper 源码

greenplumn CColConstraintsHashMapper 源码

greenplumn CColRef 源码

greenplumn CColRefComputed 源码

greenplumn CColRefSet 源码