WTO.h

Go to the documentation of this file.

//===- WTO.h -- Weakest Topological Order Analysis-------------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
 
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * WTO.h
 *
 * The implementation is based on F. Bourdoncle's paper:
 * "Efficient chaotic iteration strategies with widenings", Formal
 * Methods in Programming and Their Applications, 1993, pages 128-141.
 *
 *  Created on: Jan 22, 2024
 *      Author: Xiao Cheng, Jiawei Wang
 *
 */
#ifndef WTO_H_
#define WTO_H_
 
#include "Util/GeneralType.h"
#include <functional>
 
namespace SVF
{
 
template <typename GraphT> class WTO;
 
template <typename GraphT> class WTONode;
 
template <typename GraphT> class WTOCycle;
 
template <typename GraphT> class WTOComponentVisitor;
 
// Helper to test for the existence of a sub type
template <typename T, typename = void> struct has_nodetype : std::false_type
{
};
 
template <typename T>
struct has_nodetype<T, std::void_t<typename T::NodeType>> : std::true_type
{
};
 
template <typename T, typename = void> struct has_edgetype : std::false_type
{
};
 
template <typename T>
struct has_edgetype<T, std::void_t<typename T::EdgeType>> : std::true_type
{
};
 
template <typename GraphT> class WTOCycleDepth
{
public:
    static_assert(has_nodetype<GraphT>::value,
                  "GraphT must have a nested type named 'NodeType'");
    typedef typename GraphT::NodeType NodeT;
 
private:
    typedef std::vector<const NodeT*> NodeRefList;
 
public:
    typedef typename NodeRefList::const_iterator Iterator;
 
private:
    NodeRefList _heads;
 
public:
    WTOCycleDepth() = default;
 
    WTOCycleDepth(const WTOCycleDepth&) = default;
 
    WTOCycleDepth(WTOCycleDepth&&) = default;
 
    WTOCycleDepth& operator=(const WTOCycleDepth&) = default;
 
    WTOCycleDepth& operator=(WTOCycleDepth&&) = default;
 
    ~WTOCycleDepth() = default;
 
    void add(const NodeT* head)
    {
        _heads.push_back(head);
    }
 
    Iterator begin() const
    {
        return _heads.cbegin();
    }
 
    Iterator end() const
    {
        return _heads.cend();
    }
 
    WTOCycleDepth operator^(const WTOCycleDepth& other) const
    {
        WTOCycleDepth res;
        for (auto this_it = begin(), other_it = other.begin();
                this_it != end() && other_it != other.end(); ++this_it, ++other_it)
        {
            if (*this_it == *other_it)
            {
                res.add(*this_it);
            }
            else
            {
                break;
            }
        }
        return res;
    }
 
private:
    int compare(const WTOCycleDepth& other) const
    {
        if (this == &other)
        {
            return 0; // equals
        }
 
        auto this_it = begin();
        auto other_it = other.begin();
        while (this_it != end())
        {
            if (other_it == other.end())
            {
                return 1; // `this` is nested within `other`
            }
            else if (*this_it == *other_it)
            {
                ++this_it;
                ++other_it;
            }
            else
            {
                return 2; // not comparable
            }
        }
        if (other_it == other.end())
        {
            return 0; // equals
        }
        else
        {
            return -1; // `other` is nested within `this`
        }
    }
 
public:
    bool operator<(const WTOCycleDepth& other) const
    {
        return compare(other) == -1;
    }
 
    bool operator<=(const WTOCycleDepth& other) const
    {
        return compare(other) <= 0;
    }
 
    bool operator==(const WTOCycleDepth& other) const
    {
        return compare(other) == 0;
    }
 
    bool operator>=(const WTOCycleDepth& other) const
    {
        return operator<=(other, *this);
    }
 
    bool operator>(const WTOCycleDepth& other) const
    {
        return compare(other) == 1;
    }
 
    [[nodiscard]] std::string toString() const
    {
        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();
    }
 
 
    friend std::ostream& operator<<(std::ostream& o,
                                    const WTOCycleDepth<GraphT>& wto)
    {
        o << wto.toString();
        return o;
    }
 
}; // end class WTOCycleDepth
 
template <typename GraphT> class WTOComponent
{
public:
    enum WTOCT
    {
        Node,
        Cycle
    };
 
    explicit WTOComponent(WTOCT k) : _type(k) {};
 
    WTOComponent(const WTOComponent&) noexcept = default;
 
    WTOComponent(WTOComponent&&) noexcept = default;
 
    WTOComponent& operator=(const WTOComponent&) noexcept = default;
 
    WTOComponent& operator=(WTOComponent&&) noexcept = default;
 
    virtual void accept(WTOComponentVisitor<GraphT>&) const = 0;
 
    virtual ~WTOComponent() = default;
 
    inline WTOCT getKind() const
    {
        return _type;
    }
 
    [[nodiscard]] virtual std::string toString() const = 0;
 
 
    friend std::ostream& operator<<(std::ostream& o,
                                    const WTOComponent<GraphT>& wto)
    {
        o << wto.toString();
        return o;
    }
 
    WTOCT _type;
 
}; // end class WTOComponent
 
template <typename GraphT> class WTONode final : public WTOComponent<GraphT>
{
public:
    static_assert(has_nodetype<GraphT>::value,
                  "GraphT must have a nested type named 'NodeType'");
    typedef typename GraphT::NodeType NodeT;
 
private:
    const NodeT* _node;
 
public:
    explicit WTONode(const NodeT* node)
        : WTOComponent<GraphT>(WTOComponent<GraphT>::Node), _node(node)
    {
    }
 
    const NodeT* getICFGNode() const
    {
        return _node;
    }
 
    void accept(WTOComponentVisitor<GraphT>& v) const override
    {
        v.visit(*this);
    }
 
    [[nodiscard]] std::string toString() const override
    {
        // return _node->toString();
        return std::to_string(_node->getId());
    }
 
 
    static inline bool classof(const WTONode<GraphT>*)
    {
        return true;
    }
 
    static inline bool classof(const WTOComponent<GraphT>* c)
    {
        return c->getKind() == WTOComponent<GraphT>::Node;
    }
 
}; // end class WTONode
 
template <typename GraphT> class WTOCycle final : public WTOComponent<GraphT>
{
public:
    static_assert(has_nodetype<GraphT>::value,
                  "GraphT must have a nested type named 'NodeType'");
    typedef typename GraphT::NodeType NodeT;
    typedef WTOComponent<GraphT> WTOComponentT;
 
private:
    typedef const WTOComponentT* WTOComponentPtr;
    typedef std::list<WTOComponentPtr> WTOComponentRefList;
 
public:
    typedef typename WTOComponentRefList::const_iterator Iterator;
 
private:
    const WTONode<GraphT>* _head;
 
    WTOComponentRefList _components;
 
public:
    WTOCycle(const WTONode<GraphT>* head, WTOComponentRefList components)
        : WTOComponent<GraphT>(WTOComponent<GraphT>::Cycle), _head(head),
          _components(std::move(components))
    {
    }
 
    const WTONode<GraphT>* head() const
    {
        return _head;
    }
 
    const WTOComponentRefList& getWTOComponents() const
    {
        return _components;
    }
 
    Iterator begin() const
    {
        return _components.cbegin();
    }
 
    Iterator end() const
    {
        return _components.cend();
    }
 
    void accept(WTOComponentVisitor<GraphT>& v) const override
    {
        v.visit(*this);
    }
 
 
    static inline bool classof(const WTOCycle<GraphT>*)
    {
        return true;
    }
 
    static inline bool classof(const WTOComponent<GraphT>* c)
    {
        return c->getKind() == WTOComponent<GraphT>::Cycle;
    }
 
    [[nodiscard]] std::string toString() const override
    {
        std::string str;
        std::stringstream rawstr(str);
        rawstr << "(";
        rawstr << _head->getICFGNode()->getId() << ", ";
        for (auto it = begin(), et = end(); it != et;)
        {
            rawstr << (*it)->toString();
            ++it;
            if (it != et)
            {
                rawstr << ", ";
            }
        }
        rawstr << ")";
        return rawstr.str();
    }
 
}; // end class WTOCycle
 
template <typename GraphT> class WTOComponentVisitor
{
public:
    typedef WTONode<GraphT> WTONodeT;
    typedef WTOCycle<GraphT> WTOCycleT;
 
public:
    WTOComponentVisitor() = default;
 
    WTOComponentVisitor(const WTOComponentVisitor&) noexcept = default;
 
    WTOComponentVisitor(WTOComponentVisitor&&) noexcept = default;
 
    WTOComponentVisitor& operator=(const WTOComponentVisitor&) noexcept =
        default;
 
    WTOComponentVisitor& operator=(WTOComponentVisitor&&) noexcept = default;
 
    virtual void visit(const WTONodeT&) = 0;
 
    virtual void visit(const WTOCycleT&) = 0;
 
    virtual ~WTOComponentVisitor() = default;
 
}; // end class WTOComponentVisitor
 
template <typename GraphT> class WTO
{
 
public:
    static_assert(has_nodetype<GraphT>::value,
                  "GraphT must have a nested type named 'NodeType'");
    static_assert(has_edgetype<GraphT>::value,
                  "GraphT must have a nested type named 'EdgeType'");
    typedef typename GraphT::NodeType NodeT;
    typedef typename GraphT::EdgeType EdgeT;
    typedef WTOCycleDepth<GraphT> GraphTWTOCycleDepth;
    typedef WTOComponent<GraphT> WTOComponentT;
    typedef WTONode<GraphT> WTONodeT;
    typedef WTOCycle<GraphT> WTOCycleT;
    typedef Set<const NodeT*> NodeRefList;
 
protected:
    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;
 
public:
    typedef typename WTOComponentRefList::const_iterator Iterator;
 
protected:
    WTOComponentRefList _components;
    WTOComponentRefSet _allComponents;
    NodeRefToWTOCycleMap headRefToCycle;
    NodeRefToWTOCycleDepthPtr _nodeToDepth;
    NodeRefToCycleDepthNumber _nodeToCDN;
    CycleDepthNumber _num;
    Stack _stack;
    const NodeT* _entry;
 
public:
 
    explicit WTO(const NodeT* entry) : _num(0), _entry(entry)
    {
    }
 
    WTO(const WTO& other) = default;
 
    WTO(WTO&& other) = default;
 
    WTO& operator=(const WTO& other) = default;
 
    WTO& operator=(WTO&& other) = default;
 
    ~WTO()
    {
        for (const auto& component : _allComponents)
        {
            delete component;
        }
    }
 
    const WTOComponentRefList& getWTOComponents() const
    {
        return _components;
    }
 
    Iterator begin() const
    {
        return _components.cbegin();
    }
 
    Iterator end() const
    {
        return _components.cend();
    }
 
    bool isHead(const NodeT* node) const
    {
        return headRefToCycle.find(node) != headRefToCycle.end();
    }
 
    typename NodeRefToWTOCycleMap::const_iterator headBegin() const
    {
        return headRefToCycle.cbegin();
    }
 
    typename NodeRefToWTOCycleMap::const_iterator headEnd() const
    {
        return headRefToCycle.cend();
    }
 
    const GraphTWTOCycleDepth& cycleDepth(const NodeT* n) const
    {
        auto it = _nodeToDepth.find(n);
        assert(it != _nodeToDepth.end() && "node not found");
        return *(it->second);
    }
 
    inline bool in_cycleDepth_table(const NodeT* n) const
    {
        auto it = _nodeToDepth.find(n);
        return it != _nodeToDepth.end();
    }
 
    void accept(WTOComponentVisitor<GraphT>& v)
    {
        for (const auto& c : _components)
        {
            c->accept(v);
        }
    }
 
    [[nodiscard]] std::string toString() const
    {
        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();
    }
 
 
    friend std::ostream& operator<<(std::ostream& o, const WTO<GraphT>& wto)
    {
        o << wto.toString();
        return o;
    }
 
    void init()
    {
        visit(_entry, _components);
        _nodeToCDN.clear();
        _stack.clear();
        buildNodeToDepth();
    }
 
protected:
 
    class WTOCycleDepthBuilder final : public WTOComponentVisitor<GraphT>
    {
    private:
        WTOCycleDepthPtr _wtoCycleDepth;
        NodeRefToWTOCycleDepthPtr& _nodeToWTOCycleDepth;
 
    public:
        explicit WTOCycleDepthBuilder(
            NodeRefToWTOCycleDepthPtr& nodeToWTOCycleDepth)
            : _wtoCycleDepth(std::make_shared<GraphTWTOCycleDepth>()),
              _nodeToWTOCycleDepth(nodeToWTOCycleDepth)
        {
        }
 
        void visit(const WTOCycleT& cycle) override
        {
            const NodeT* head = cycle.head()->getICFGNode();
            WTOCycleDepthPtr previous_cycleDepth = _wtoCycleDepth;
            _nodeToWTOCycleDepth.insert(std::make_pair(head, _wtoCycleDepth));
            _wtoCycleDepth =
                std::make_shared<GraphTWTOCycleDepth>(*_wtoCycleDepth);
            _wtoCycleDepth->add(head);
            for (auto it = cycle.begin(), et = cycle.end(); it != et; ++it)
            {
                (*it)->accept(*this);
            }
            _wtoCycleDepth = previous_cycleDepth;
        }
 
        void visit(const WTONodeT& node) override
        {
            _nodeToWTOCycleDepth.insert(
                std::make_pair(node.getICFGNode(), _wtoCycleDepth));
        }
 
    }; // end class WTOCycleDepthBuilder
 
protected:
    inline virtual std::vector<const NodeT *> getSuccessors(const NodeT* node)
    {
        std::vector<const NodeT *> succssors;
        for (const auto& e : node->getOutEdges())
        {
            succssors.push_back(e->getDstNode());
        }
        return succssors;
    }
 
protected:
    CycleDepthNumber getCDN(const NodeT* n) const
    {
        auto it = _nodeToCDN.find(n);
        if (it != _nodeToCDN.end())
        {
            return it->second;
        }
        else
        {
            return 0;
        }
    }
 
    void setCDN(const NodeT* n, const CycleDepthNumber& dfn)
    {
        auto res = _nodeToCDN.insert(std::make_pair(n, dfn));
        if (!res.second)
        {
            (res.first)->second = dfn;
        }
    }
 
    const NodeT* pop()
    {
        assert(!_stack.empty() && "empty stack");
        const NodeT* top = _stack.back();
        _stack.pop_back();
        return top;
    }
 
    void push(const NodeT* n)
    {
        _stack.push_back(n);
    }
 
    const WTONodeT* newNode(const NodeT* node)
    {
        const WTONodeT* ptr = new WTONodeT(node);
        _allComponents.insert(ptr);
        return ptr;
    }
 
    const WTOCycleT* newCycle(const WTONodeT* node,
                              const WTOComponentRefList& partition)
    {
        const WTOCycleT* ptr = new WTOCycleT(node, std::move(partition));
        _allComponents.insert(ptr);
        return ptr;
    }
 
    virtual const WTOCycleT* component(const NodeT* node)
    {
        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;
    }
 
    virtual CycleDepthNumber visit(const NodeT* node,
                                   WTOComponentRefList& partition)
    {
        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;
    }
 
    void buildNodeToDepth()
    {
        WTOCycleDepthBuilder builder(_nodeToDepth);
        for (auto it = begin(), et = end(); it != et; ++it)
        {
            (*it)->accept(builder);
        }
    }
 
}; // end class WTO
 
} // namespace SVF
 
#endif /* WTO_H_ */