#include <WTO.h>

Classes
class	WTOCycleDepthBuilder
	Visitor to build the cycle depths of each node. More...

Public Types
typedef GraphT::NodeType	NodeT

typedef GraphT::EdgeType	EdgeT

typedef WTOCycleDepth< GraphT >	GraphTWTOCycleDepth

typedef WTOComponent< GraphT >	WTOComponentT

typedef WTONode< GraphT >	WTONodeT

typedef WTOCycle< GraphT >	WTOCycleT

typedef Set< const NodeT * >	NodeRefList

typedef WTOComponentRefList::const_iterator	Iterator
	Iterator over the components.

Public Member Functions
	WTO (const NodeT *entry)
	Compute the weak topological order of the given graph.

	WTO (const WTO &other)=default
	No copy constructor.

	WTO (WTO &&other)=default
	Move constructor.

WTO &	operator= (const WTO &other)=default
	No copy assignment operator.

WTO &	operator= (WTO &&other)=default
	Move assignment operator.

	~WTO ()
	Destructor.

const WTOComponentRefList &	getWTOComponents () const
	Get all wto components in WTO.

Iterator	begin () const
	Begin iterator over the components.

Iterator	end () const
	End iterator over the components.

bool	isHead (const NodeT *node) const

NodeRefToWTOCycleMap::const_iterator	headBegin () const

NodeRefToWTOCycleMap::const_iterator	headEnd () const
	End iterator over the components.

const GraphTWTOCycleDepth &	cycleDepth (const NodeT *n) const
	Return the cycleDepth of the given node.

bool	in_cycleDepth_table (const NodeT *n) const
	Return the cycleDepth of the given node.

void	accept (WTOComponentVisitor< GraphT > &v)
	Accept the given visitor.

std::string	toString () const
	Dump the order, for debugging purpose.

void	init ()

Protected Types
typedef const WTOComponentT *	WTOComponentPtr

typedef std::list< WTOComponentPtr >	WTOComponentRefList

typedef Set< WTOComponentPtr >	WTOComponentRefSet

typedef Map< const NodeT , const WTOCycleT >	NodeRefToWTOCycleMap

typedef Map< const NodeT *, NodeRefList >	NodeRefTONodeRefListMap

typedef u32_t	CycleDepthNumber

typedef Map< const NodeT *, CycleDepthNumber >	NodeRefToCycleDepthNumber

typedef std::vector< const NodeT * >	Stack

typedef std::shared_ptr< GraphTWTOCycleDepth >	WTOCycleDepthPtr

typedef Map< const NodeT *, WTOCycleDepthPtr >	NodeRefToWTOCycleDepthPtr

Protected Member Functions
virtual std::vector< const NodeT * >	getSuccessors (const NodeT *node)
	Return the successors of node.

CycleDepthNumber	getCDN (const NodeT *n) const
	Return the depth-first number of the given node.

void	setCDN (const NodeT *n, const CycleDepthNumber &dfn)
	Set the depth-first number of the given node.

const NodeT *	pop ()
	Pop a node from the stack.

void	push (const NodeT *n)
	Push a node on the stack.

const WTONodeT *	newNode (const NodeT *node)

const WTOCycleT *	newCycle (const WTONodeT *node, const WTOComponentRefList &partition)

virtual const WTOCycleT *	component (const NodeT *node)
	Create the cycle component for the given node.

virtual CycleDepthNumber	visit (const NodeT *node, WTOComponentRefList &partition)

void	buildNodeToDepth ()
	Build the node to WTO cycle depth table.

Protected Attributes
WTOComponentRefList	_components

WTOComponentRefSet	_allComponents

NodeRefToWTOCycleMap	headRefToCycle

NodeRefToWTOCycleDepthPtr	_nodeToDepth

NodeRefToCycleDepthNumber	_nodeToCDN

CycleDepthNumber	_num

Stack	_stack

const NodeT *	_entry

Friends
std::ostream &	operator<< (std::ostream &o, const WTO< GraphT > &wto)
	Overloading operator << for dumping ICFG node ID.

Detailed Description

template<typename GraphT>
class SVF::WTO< GraphT >

Weak topological order for GraphT

Definition at line 516 of file WTO.h.

Member Typedef Documentation

◆ CycleDepthNumber

template<typename GraphT >

typedef u32_t SVF::WTO< GraphT >::CycleDepthNumber

protected

Definition at line 539 of file WTO.h.

◆ EdgeT

template<typename GraphT >

typedef GraphT::EdgeType SVF::WTO< GraphT >::EdgeT

Definition at line 525 of file WTO.h.

◆ GraphTWTOCycleDepth

template<typename GraphT >

typedef WTOCycleDepth<GraphT> SVF::WTO< GraphT >::GraphTWTOCycleDepth

Definition at line 526 of file WTO.h.

◆ Iterator

template<typename GraphT >

typedef WTOComponentRefList::const_iterator SVF::WTO< GraphT >::Iterator

Iterator over the components.

Definition at line 547 of file WTO.h.

◆ NodeRefList

template<typename GraphT >

typedef Set<const NodeT*> SVF::WTO< GraphT >::NodeRefList

Definition at line 530 of file WTO.h.

◆ NodeRefToCycleDepthNumber

template<typename GraphT >

typedef Map<const NodeT*, CycleDepthNumber> SVF::WTO< GraphT >::NodeRefToCycleDepthNumber

protected

Definition at line 540 of file WTO.h.

◆ NodeRefTONodeRefListMap

template<typename GraphT >

typedef Map<const NodeT*, NodeRefList> SVF::WTO< GraphT >::NodeRefTONodeRefListMap

protected

Definition at line 537 of file WTO.h.

◆ NodeRefToWTOCycleDepthPtr

template<typename GraphT >

typedef Map<const NodeT*, WTOCycleDepthPtr> SVF::WTO< GraphT >::NodeRefToWTOCycleDepthPtr

protected

Definition at line 543 of file WTO.h.

◆ NodeRefToWTOCycleMap

template<typename GraphT >

typedef Map<const NodeT*, const WTOCycleT*> SVF::WTO< GraphT >::NodeRefToWTOCycleMap

protected

Definition at line 536 of file WTO.h.

◆ NodeT

template<typename GraphT >

typedef GraphT::NodeType SVF::WTO< GraphT >::NodeT

Definition at line 524 of file WTO.h.

◆ Stack

template<typename GraphT >

typedef std::vector<const NodeT*> SVF::WTO< GraphT >::Stack

protected

Definition at line 541 of file WTO.h.

◆ WTOComponentPtr

template<typename GraphT >

typedef const WTOComponentT* SVF::WTO< GraphT >::WTOComponentPtr

protected

Definition at line 533 of file WTO.h.

◆ WTOComponentRefList

template<typename GraphT >

typedef std::list<WTOComponentPtr> SVF::WTO< GraphT >::WTOComponentRefList

protected

Definition at line 534 of file WTO.h.

◆ WTOComponentRefSet

template<typename GraphT >

typedef Set<WTOComponentPtr> SVF::WTO< GraphT >::WTOComponentRefSet

protected

Definition at line 535 of file WTO.h.

◆ WTOComponentT

template<typename GraphT >

typedef WTOComponent<GraphT> SVF::WTO< GraphT >::WTOComponentT

Definition at line 527 of file WTO.h.

◆ WTOCycleDepthPtr

template<typename GraphT >

typedef std::shared_ptr<GraphTWTOCycleDepth> SVF::WTO< GraphT >::WTOCycleDepthPtr

protected

Definition at line 542 of file WTO.h.

◆ WTOCycleT

template<typename GraphT >

typedef WTOCycle<GraphT> SVF::WTO< GraphT >::WTOCycleT

Definition at line 529 of file WTO.h.

◆ WTONodeT

template<typename GraphT >

typedef WTONode<GraphT> SVF::WTO< GraphT >::WTONodeT

Definition at line 528 of file WTO.h.

Constructor & Destructor Documentation

◆ WTO() [1/3]

template<typename GraphT >

SVF::WTO< GraphT >::WTO ( const NodeT * entry )

inlineexplicit

Compute the weak topological order of the given graph.

Definition at line 562 of file WTO.h.

                                     : _num(0), _entry(entry)
    {
    }

◆ WTO() [2/3]

template<typename GraphT >

SVF::WTO< GraphT >::WTO ( const WTO< GraphT > & other )

default

No copy constructor.

◆ WTO() [3/3]

template<typename GraphT >

SVF::WTO< GraphT >::WTO ( WTO< GraphT > && other )

default

Move constructor.

◆ ~WTO()

template<typename GraphT >

SVF::WTO< GraphT >::~WTO ( )

inline

Destructor.

Definition at line 579 of file WTO.h.

    {
        for (const auto& component : _allComponents)
        {
            delete component;
        }
    }

Member Function Documentation

◆ accept()

template<typename GraphT >

void SVF::WTO< GraphT >::accept ( WTOComponentVisitor< GraphT > & v )

inline

Accept the given visitor.

Definition at line 637 of file WTO.h.

    {
        for (const auto& c : _components)
        {
            c->accept(v);
        }
    }

◆ begin()

template<typename GraphT >

Iterator SVF::WTO< GraphT >::begin ( ) const

inline

Begin iterator over the components.

Definition at line 594 of file WTO.h.

    {
        return _components.cbegin();
    }

◆ buildNodeToDepth()

template<typename GraphT >

void SVF::WTO< GraphT >::buildNodeToDepth ( )

inlineprotected

Build the node to WTO cycle depth table.

Definition at line 862 of file WTO.h.

    {
        WTOCycleDepthBuilder builder(_nodeToDepth);
        for (auto it = begin(), et = end(); it != et; ++it)
        {
            (*it)->accept(builder);
        }
    }

◆ component()

template<typename GraphT >

virtual const WTOCycleT * SVF::WTO< GraphT >::component ( const NodeT * node )

inlineprotectedvirtual

Create the cycle component for the given node.

Definition at line 789 of file WTO.h.

    {
        WTOComponentRefList partition;
 
        for (auto succ: getSuccessors(node))
        {
            if (getCDN(succ) == 0)
            {
                visit(succ, partition);
            }
        }
        const WTONodeT* head = newNode(node);
        const WTOCycleT* ptr = newCycle(head, partition);
        headRefToCycle.emplace(node, ptr);
        return ptr;
    }

◆ cycleDepth()

template<typename GraphT >

const GraphTWTOCycleDepth & SVF::WTO< GraphT >::cycleDepth ( const NodeT * n ) const

inline

Return the cycleDepth of the given node.

Definition at line 622 of file WTO.h.

    {
        auto it = _nodeToDepth.find(n);
        assert(it != _nodeToDepth.end() && "node not found");
        return *(it->second);
    }

◆ end()

template<typename GraphT >

Iterator SVF::WTO< GraphT >::end ( ) const

inline

End iterator over the components.

Definition at line 600 of file WTO.h.

    {
        return _components.cend();
    }

◆ getCDN()

template<typename GraphT >

CycleDepthNumber SVF::WTO< GraphT >::getCDN ( const NodeT * n ) const

inlineprotected

Return the depth-first number of the given node.

Definition at line 735 of file WTO.h.

    {
        auto it = _nodeToCDN.find(n);
        if (it != _nodeToCDN.end())
        {
            return it->second;
        }
        else
        {
            return 0;
        }
    }

◆ getSuccessors()

template<typename GraphT >

virtual std::vector< const NodeT * > SVF::WTO< GraphT >::getSuccessors ( const NodeT * node )

inlineprotectedvirtual

Return the successors of node.

Definition at line 723 of file WTO.h.

    {
        std::vector<const NodeT *> succssors;
        for (const auto& e : node->getOutEdges())
        {
            succssors.push_back(e->getDstNode());
        }
        return succssors;
    }

◆ getWTOComponents()

template<typename GraphT >

const WTOComponentRefList & SVF::WTO< GraphT >::getWTOComponents ( ) const

inline

Get all wto components in WTO.

Definition at line 588 of file WTO.h.

    {
        return _components;
    }

◆ headBegin()

template<typename GraphT >

NodeRefToWTOCycleMap::const_iterator SVF::WTO< GraphT >::headBegin ( ) const

inline

Definition at line 610 of file WTO.h.

    {
        return headRefToCycle.cbegin();
    }

◆ headEnd()

template<typename GraphT >

NodeRefToWTOCycleMap::const_iterator SVF::WTO< GraphT >::headEnd ( ) const

inline

End iterator over the components.

Definition at line 616 of file WTO.h.

    {
        return headRefToCycle.cend();
    }

◆ in_cycleDepth_table()

template<typename GraphT >

bool SVF::WTO< GraphT >::in_cycleDepth_table ( const NodeT * n ) const

inline

Return the cycleDepth of the given node.

Definition at line 630 of file WTO.h.

    {
        auto it = _nodeToDepth.find(n);
        return it != _nodeToDepth.end();
    }

◆ init()

template<typename GraphT >

void SVF::WTO< GraphT >::init ( )

inline

Definition at line 673 of file WTO.h.

    {
        visit(_entry, _components);
        _nodeToCDN.clear();
        _stack.clear();
        buildNodeToDepth();
    }

◆ isHead()

template<typename GraphT >

bool SVF::WTO< GraphT >::isHead ( const NodeT * node ) const

inline

Definition at line 605 of file WTO.h.

    {
        return headRefToCycle.find(node) != headRefToCycle.end();
    }

◆ newCycle()

template<typename GraphT >

const WTOCycleT * SVF::WTO< GraphT >::newCycle	(	const WTONodeT *	node,
		const WTOComponentRefList &	partition
	)

inlineprotected

Definition at line 780 of file WTO.h.

    {
        const WTOCycleT* ptr = new WTOCycleT(node, std::move(partition));
        _allComponents.insert(ptr);
        return ptr;
    }

◆ newNode()

template<typename GraphT >

const WTONodeT * SVF::WTO< GraphT >::newNode ( const NodeT * node )

inlineprotected

Definition at line 773 of file WTO.h.

    {
        const WTONodeT* ptr = new WTONodeT(node);
        _allComponents.insert(ptr);
        return ptr;
    }

◆ operator=() [1/2]

template<typename GraphT >

WTO & SVF::WTO< GraphT >::operator= ( const WTO< GraphT > & other )

default

No copy assignment operator.

◆ operator=() [2/2]

template<typename GraphT >

WTO & SVF::WTO< GraphT >::operator= ( WTO< GraphT > && other )

default

Move assignment operator.

◆ pop()

template<typename GraphT >

const NodeT * SVF::WTO< GraphT >::pop ( )

inlineprotected

Pop a node from the stack.

Definition at line 759 of file WTO.h.

    {
        assert(!_stack.empty() && "empty stack");
        const NodeT* top = _stack.back();
        _stack.pop_back();
        return top;
    }

◆ push()

template<typename GraphT >

void SVF::WTO< GraphT >::push ( const NodeT * n )

inlineprotected

Push a node on the stack.

Definition at line 768 of file WTO.h.

    {
        _stack.push_back(n);
    }

◆ setCDN()

template<typename GraphT >

void SVF::WTO< GraphT >::setCDN	(	const NodeT *	n,
		const CycleDepthNumber &	dfn
	)

inlineprotected

Set the depth-first number of the given node.

Definition at line 749 of file WTO.h.

    {
        auto res = _nodeToCDN.insert(std::make_pair(n, dfn));
        if (!res.second)
        {
            (res.first)->second = dfn;
        }
    }

◆ toString()

template<typename GraphT >

std::string SVF::WTO< GraphT >::toString ( ) const

inline

Dump the order, for debugging purpose.

Definition at line 646 of file WTO.h.

    {
        std::string str;
        std::stringstream rawstr(str);
        rawstr << "[";
        for (auto it = begin(), et = end(); it != et;)
        {
            rawstr << (*it)->toString();
            ++it;
            if (it != et)
            {
                rawstr << ", ";
            }
        }
        rawstr << "]";
        return rawstr.str();
    }

◆ visit()

template<typename GraphT >

virtual CycleDepthNumber SVF::WTO< GraphT >::visit	(	const NodeT *	node,
		WTOComponentRefList &	partition
	)

inlineprotectedvirtual

Visit the given node

Algorithm to build a weak topological order of a graph

Definition at line 809 of file WTO.h.

    {
        CycleDepthNumber head(0);
        CycleDepthNumber min(0);
        bool loop;
 
        push(node);
        _num += CycleDepthNumber(1);
        head = _num;
        setCDN(node, head);
        loop = false;
 
        for (auto succ: getSuccessors(node))
        {
            CycleDepthNumber succ_dfn = getCDN(succ);
            if (succ_dfn == CycleDepthNumber(0))
            {
                min = visit(succ, partition);
            }
            else
            {
                min = succ_dfn;
            }
            if (min <= head)
            {
                head = min;
                loop = true;
            }
        }
 
        if (head == getCDN(node))
        {
            setCDN(node, UINT_MAX);
            const NodeT* element = pop();
            if (loop)
            {
                while (element != node)
                {
                    setCDN(element, 0);
                    element = pop();
                }
                partition.push_front(component(node));
            }
            else
            {
                partition.push_front(newNode(node));
            }
        }
        return head;
    }

Friends And Related Symbol Documentation

◆ operator<<

template<typename GraphT >

std::ostream & operator<<	(	std::ostream &	o,
		const WTO< GraphT > &	wto
	)

friend

Overloading operator << for dumping ICFG node ID.

Definition at line 666 of file WTO.h.

    {
        o << wto.toString();
        return o;
    }

Member Data Documentation

◆ _allComponents

template<typename GraphT >

WTOComponentRefSet SVF::WTO< GraphT >::_allComponents

protected

Definition at line 551 of file WTO.h.

◆ _components

template<typename GraphT >

WTOComponentRefList SVF::WTO< GraphT >::_components

protected

Definition at line 550 of file WTO.h.

◆ _entry

template<typename GraphT >

const NodeT* SVF::WTO< GraphT >::_entry

protected

Definition at line 557 of file WTO.h.

◆ _nodeToCDN

template<typename GraphT >

NodeRefToCycleDepthNumber SVF::WTO< GraphT >::_nodeToCDN

protected

Definition at line 554 of file WTO.h.

◆ _nodeToDepth

template<typename GraphT >

NodeRefToWTOCycleDepthPtr SVF::WTO< GraphT >::_nodeToDepth

protected

Definition at line 553 of file WTO.h.

◆ _num

template<typename GraphT >

CycleDepthNumber SVF::WTO< GraphT >::_num

protected

Definition at line 555 of file WTO.h.

◆ _stack

template<typename GraphT >

Stack SVF::WTO< GraphT >::_stack

protected

Definition at line 556 of file WTO.h.

◆ headRefToCycle

template<typename GraphT >

NodeRefToWTOCycleMap SVF::WTO< GraphT >::headRefToCycle

protected

Definition at line 552 of file WTO.h.

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

/home/runner/work/SVF/SVF/svf/include/Graphs/WTO.h

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ CycleDepthNumber

◆ EdgeT

◆ GraphTWTOCycleDepth

◆ Iterator

◆ NodeRefList

◆ NodeRefToCycleDepthNumber

◆ NodeRefTONodeRefListMap

◆ NodeRefToWTOCycleDepthPtr

◆ NodeRefToWTOCycleMap

◆ NodeT

◆ Stack

◆ WTOComponentPtr

◆ WTOComponentRefList

◆ WTOComponentRefSet

◆ WTOComponentT

◆ WTOCycleDepthPtr

◆ WTOCycleT

◆ WTONodeT

Constructor & Destructor Documentation

◆ WTO() [1/3]

◆ WTO() [2/3]

◆ WTO() [3/3]

◆ ~WTO()

Member Function Documentation

◆ accept()

◆ begin()

◆ buildNodeToDepth()

◆ component()

◆ cycleDepth()

◆ end()

◆ getCDN()

◆ getSuccessors()

◆ getWTOComponents()

◆ headBegin()

◆ headEnd()

◆ in_cycleDepth_table()

◆ init()

◆ isHead()

◆ newCycle()

◆ newNode()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop()

◆ push()

◆ setCDN()

◆ toString()

◆ visit()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ _allComponents

◆ _components

◆ _entry

◆ _nodeToCDN

◆ _nodeToDepth

◆ _num

◆ _stack

◆ headRefToCycle