DPItem.h

Go to the documentation of this file.

//===- DPItem.h -- Context/path sensitive classes----------------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2017>  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero 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 Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * DPItem.h
 *
 *  Created on: Apr 1, 2014
 *      Author: Yulei Sui
 */
 
#ifndef DPITEM_H_
#define DPITEM_H_
 
#include "MemoryModel/ConditionalPT.h"
#include "Util/GeneralType.h"
#include <algorithm>    // std::sort
 
namespace SVF
{
 
class DPItem
{
protected:
    NodeID cur;
    static u64_t maximumBudget;
 
public:
    DPItem(NodeID c) : cur(c)
    {
    }
    DPItem(const DPItem& dps) : cur(dps.cur)
    {
    }
    DPItem(DPItem&& dps) noexcept : cur(dps.cur)
    {
 
    }
    DPItem &operator=(DPItem &&rhs) noexcept
    {
        if (this != &rhs)
        {
            cur = rhs.cur;
        }
        return *this;
    }
    virtual ~DPItem()
    {
    }
    inline NodeID getCurNodeID() const
    {
        return cur;
    }
    inline void setCurNodeID(NodeID c)
    {
        cur = c;
    }
    static inline void setMaxBudget(u32_t max)
    {
        maximumBudget = max;
    }
    static inline u32_t getMaxBudget()
    {
        return maximumBudget;
    }
    inline bool operator< (const DPItem& rhs) const
    {
        return cur < rhs.cur;
    }
    inline DPItem& operator= (const DPItem& rhs)
    {
        if(*this!=rhs)
        {
            cur = rhs.cur;
        }
        return *this;
    }
    inline bool operator== (const DPItem& rhs) const
    {
        return (cur == rhs.cur);
    }
    inline bool operator!= (const DPItem& rhs) const
    {
        return !(*this == rhs);
    }
 
    inline void dump() const
    {
        SVFUtil::outs() << "var " << cur << "\n";
    }
};
 
 
template<class LocCond>
class StmtDPItem : public DPItem
{
 
 
protected:
    const LocCond* curloc;
 
public:
    StmtDPItem(NodeID c, const LocCond* locCond) : DPItem(c), curloc(locCond)
    {
    }
    StmtDPItem(const StmtDPItem& dps) :
        DPItem(dps), curloc(dps.curloc)
    {
    }
    virtual ~StmtDPItem()
    {
    }
    inline const LocCond* getLoc() const
    {
        return this->curloc;
    }
    inline void setLoc(const LocCond* l)
    {
        this->curloc = l;
    }
    inline void setLocVar(const LocCond* l,NodeID v)
    {
        this->curloc = l;
        this->cur = v;
    }
    inline bool operator< (const StmtDPItem& rhs) const
    {
        if (this->cur != rhs.cur)
            return this->cur < rhs.cur;
        else
            return this->curloc < rhs.curloc;
    }
    inline StmtDPItem& operator= (const StmtDPItem& rhs)
    {
        if(*this!=rhs)
        {
            DPItem::operator=(rhs);
            this->curloc = rhs.getLoc();
        }
        return *this;
    }
    inline bool operator== (const StmtDPItem& rhs) const
    {
        return (this->cur == rhs.cur && this->curloc == rhs.getLoc());
    }
    inline bool operator!= (const StmtDPItem& rhs) const
    {
        return !(*this==rhs);
    }
    inline void dump() const
    {
        SVFUtil::outs() << "statement " << *(this->curloc)  << ", var " << this->cur << "\n";
    }
};
 
class ContextCond
{
public:
    typedef CallStrCxt::const_iterator const_iterator;
    ContextCond():concreteCxt(true)
    {
    }
    ContextCond(const ContextCond& cond): context(cond.getContexts()), concreteCxt(cond.isConcreteCxt())
    {
    }
    ContextCond(ContextCond &&cond) noexcept: context(std::move(cond.context)), concreteCxt(cond.concreteCxt) {}
    ContextCond& operator=(ContextCond&&cond) noexcept
    {
        if(this!=&cond)
        {
            context = std::move(cond.context);
            concreteCxt = cond.concreteCxt;
        }
        return *this;
    }
    virtual ~ContextCond()
    {
    }
    inline const CallStrCxt& getContexts() const
    {
        return context;
    }
    inline CallStrCxt& getContexts()
    {
        return context;
    }
    inline bool isConcreteCxt() const
    {
        return concreteCxt;
    }
    inline void setNonConcreteCxt()
    {
        concreteCxt = false;
    }
    inline bool containCallStr(NodeID cxt) const
    {
        return std::find(context.begin(),context.end(),cxt) != context.end();
    }
    inline u32_t cxtSize() const
    {
        return context.size();
    }
    static inline void setMaxCxtLen(u32_t max)
    {
        maximumCxtLen = max;
    }
    static inline void setMaxPathLen(u32_t max)
    {
        maximumPathLen = max;
    }
    inline u32_t getMaxPathLen() const
    {
        return maximumPathLen;
    }
    inline virtual bool pushContext(NodeID ctx)
    {
 
        if(context.size() < maximumCxtLen)
        {
            context.push_back(ctx);
 
            if(context.size() > maximumCxt)
                maximumCxt = context.size();
            return true;
        }
        else   
        {
            if(!context.empty())
            {
                setNonConcreteCxt();
                context.erase(context.begin());
                context.push_back(ctx);
            }
            return false;
        }
    }
 
    inline virtual bool matchContext(NodeID ctx)
    {
        if(context.empty())
            return true;
        else if(context.back() == ctx)
        {
            context.pop_back();
            return true;
        }
        return false;
    }
 
    inline bool operator< (const ContextCond& rhs) const
    {
        return context < rhs.context;
    }
    inline NodeID operator[] (const u32_t index) const
    {
        assert(index < context.size());
        return context[index];
    }
    inline ContextCond& operator= (const ContextCond& rhs)
    {
        if(*this!=rhs)
        {
            context = rhs.getContexts();
            concreteCxt = rhs.isConcreteCxt();
        }
        return *this;
    }
    inline bool operator== (const ContextCond& rhs) const
    {
        return (context == rhs.getContexts());
    }
    inline bool operator!= (const ContextCond& rhs) const
    {
        return !(*this==rhs);
    }
    inline const_iterator begin() const
    {
        return context.begin();
    }
    inline const_iterator end() const
    {
        return context.end();
    }
    inline std::string toString() const
    {
        std::string str;
        std::stringstream rawstr(str);
        rawstr << "[:";
        for(CallStrCxt::const_iterator it = context.begin(), eit = context.end(); it!=eit; ++it)
        {
            rawstr << *it << " ";
        }
        rawstr << " ]";
        return rawstr.str();
    }
protected:
    CallStrCxt context;
    static u32_t maximumCxtLen;
    static u32_t maximumPathLen;
    bool concreteCxt;
public:
    static u32_t maximumCxt;
    static u32_t maximumPath;
};
 
typedef CondVar<ContextCond> CxtVar;
typedef CondStdSet<CxtVar> CxtPtSet;
 
template<class LocCond>
class CxtStmtDPItem : public StmtDPItem<LocCond>
{
private:
    ContextCond context;
public:
    CxtStmtDPItem(const CxtVar& var, const LocCond* locCond) : StmtDPItem<LocCond>(var.get_id(),locCond), context(var.get_cond())
    {
    }
    CxtStmtDPItem(const CxtStmtDPItem<LocCond>& dps) :
        StmtDPItem<LocCond>(dps), context(dps.context)
    {
    }
    virtual ~CxtStmtDPItem()
    {
    }
    inline CxtVar getCondVar() const
    {
        CxtVar var(this->context,this->cur);
        return var;
    }
    inline const ContextCond& getCond() const
    {
        return this->context;
    }
    inline ContextCond& getCond()
    {
        return this->context;
    }
    inline bool pushContext(NodeID cxt)
    {
        return this->context.pushContext(cxt);
    }
 
    inline bool matchContext(NodeID cxt)
    {
        return this->context.matchContext(cxt);
    }
 
    inline bool operator< (const CxtStmtDPItem<LocCond>& rhs) const
    {
        if (this->cur != rhs.cur)
            return this->cur < rhs.cur;
        else if(this->curloc != rhs.getLoc())
            return this->curloc < rhs.getLoc();
        else
            return this->context < rhs.context;
    }
    inline CxtStmtDPItem<LocCond>& operator= (const CxtStmtDPItem<LocCond>& rhs)
    {
        if(*this!=rhs)
        {
            StmtDPItem<LocCond>::operator=(rhs);
            this->context = rhs.getCond();
        }
        return *this;
    }
    inline bool operator== (const CxtStmtDPItem<LocCond>& rhs) const
    {
        return (this->cur == rhs.cur && this->curloc == rhs.getLoc() && this->context == rhs.context);
    }
    inline bool operator!= (const CxtStmtDPItem<LocCond>& rhs) const
    {
        return !(*this==rhs);
    }
    inline void dump() const
    {
        SVFUtil::outs() << "statement " << *(this->curloc)  << ", var " << this->cur << " ";
        SVFUtil::outs() << this->context.toString()  <<"\n";
    }
};
 
typedef CondVar<ContextCond> CxtVar;
class CxtDPItem : public DPItem
{
private:
    ContextCond context;
 
public:
    CxtDPItem(NodeID c, const ContextCond& cxt) : DPItem(c),context(cxt)
    {
    }
    CxtDPItem(const CxtVar& var) : DPItem(var.get_id()),context(var.get_cond())
    {
    }
    CxtDPItem(const CxtDPItem& dps) :
        DPItem(dps.getCurNodeID()), context(dps.context)
    {
    }
    CxtDPItem(CxtDPItem &&dps) noexcept: DPItem(dps), context(std::move(dps.context))
    {
    }
    CxtDPItem &operator=(CxtDPItem &&dps) noexcept
    {
        if (this != &dps)
        {
            DPItem::operator=(dps);
            context = std::move(dps.context);
        }
        return *this;
    }
    virtual ~CxtDPItem()
    {
    }
 
    inline const ContextCond& getContexts() const
    {
        return context;
    }
    inline void pushContext(NodeID cxt)
    {
        context.pushContext(cxt);
    }
 
    inline virtual bool matchContext(NodeID cxt)
    {
        return context.matchContext(cxt);
    }
 
    inline bool operator< (const CxtDPItem& rhs) const
    {
        if (cur != rhs.cur)
            return cur < rhs.cur;
        else
            return context < rhs.context;
    }
    inline CxtDPItem& operator= (const CxtDPItem& rhs)
    {
        if(*this!=rhs)
        {
            cur = rhs.cur;
            context = rhs.context;
        }
        return *this;
    }
    inline bool operator== (const CxtDPItem& rhs) const
    {
        return (cur == rhs.cur) && (context == rhs.context);
    }
    inline bool operator!= (const CxtDPItem& rhs) const
    {
        return !(*this == rhs);
    }
 
};
} // End namespace SVF
 
template <>
struct std::hash<SVF::CxtDPItem>
{
    size_t operator()(const SVF::CxtDPItem &cdpi) const
    {
        SVF::Hash<std::pair<SVF::NodeID, SVF::ContextCond>> h;
        return h(std::make_pair(cdpi.getCurNodeID(), cdpi.getContexts()));
    }
};
 
template <typename LocCond>
struct std::hash<SVF::StmtDPItem<LocCond>>
{
    size_t operator()(const SVF::StmtDPItem<LocCond> &sdpi) const
    {
        SVF::Hash<std::pair<SVF::NodeID, const LocCond *>> h;
        return h(std::make_pair(sdpi.getCurNodeID(), sdpi.getLoc()));
    }
};
 
template<class LocCond>
struct std::hash<SVF::CxtStmtDPItem<LocCond>>
{
    size_t operator()(const SVF::CxtStmtDPItem<LocCond> &csdpi) const
    {
        SVF::Hash<std::pair<SVF::NodeID, std::pair<const LocCond *, SVF::ContextCond>>> h;
        return h(std::make_pair(csdpi.getCurNodeID(),
                                std::make_pair(csdpi.getLoc(), csdpi.getCond())));
    }
};
 
template <>
struct std::hash<const SVF::ContextCond>
{
    size_t operator()(const SVF::ContextCond &cc) const
    {
        std::hash<SVF::CallStrCxt> h;
        return h(cc.getContexts());
    }
};
 
template <>
struct std::hash<SVF::ContextCond>
{
    size_t operator()(const SVF::ContextCond &cc) const
    {
        std::hash<SVF::CallStrCxt> h;
        return h(cc.getContexts());
    }
};
#endif /* DPITEM_H_ */