AbstractPointsToDS.h

Go to the documentation of this file.

//===- AbstractPointsToDS.h -- Abstract points-to data structure-------------//
//
//                     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 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/>.
//
//===----------------------------------------------------------------------===//
 
 
 
 
/*
 * AbstractPointsToDS.h
 *
 * Authors: Mohamad Barbar and Yulei Sui
 *
 * The implementation is based on
 * Mohamad Barbar and Yulei Sui. Hash Consed Points-To Sets.
 * 28th Static Analysis Symposium (SAS'21)
 */
 
#ifndef ABSTRACT_POINTSTO_H_
#define ABSTRACT_POINTSTO_H_
 
namespace SVF
{
template <typename Key, typename KeySet, typename Data, typename DataSet>
class PTData
{
public:
    enum PTDataTy
    {
        Base,
        MutBase,
        Diff,
        MutDiff,
        DataFlow,
        MutDataFlow,
        MutIncDataFlow,
        Versioned,
        MutVersioned,
        PersBase,
        PersDiff,
        PersDataFlow,
        PersIncDataFlow,
        PersVersioned,
    };
 
    PTData(bool reversePT = true, PTDataTy ty = PTDataTy::Base) : rev(reversePT), ptdTy(ty) { }
 
    virtual ~PTData() { }
 
    inline PTDataTy getPTDTY() const
    {
        return ptdTy;
    }
 
    inline bool hasReversePts() const
    {
        return rev;
    }
 
    virtual void clear() = 0;
 
    virtual const DataSet& getPts(const Key& var) = 0;
    virtual const KeySet& getRevPts(const Data& datum) = 0;
 
    virtual bool addPts(const Key& var, const Data& element) = 0;
 
    virtual bool unionPts(const Key& dstVar, const Key& srcVar) = 0;
    virtual bool unionPts(const Key& dstVar, const DataSet& srcDataSet) = 0;
 
    virtual void clearPts(const Key& var, const Data& element) = 0;
    virtual void clearFullPts(const Key& var) = 0;
 
    virtual void remapAllPts(void) = 0;
 
    virtual void dumpPTData() = 0;
 
    virtual Map<DataSet, unsigned> getAllPts(bool liveOnly) const = 0;
 
protected:
    bool rev;
    PTDataTy ptdTy;
};
 
template <typename Key, typename KeySet, typename Data, typename DataSet>
class DiffPTData : public PTData<Key, KeySet, Data, DataSet>
{
public:
    typedef PTData<Key, KeySet, Data, DataSet> BasePTData;
    typedef typename BasePTData::PTDataTy PTDataTy;
 
    DiffPTData(bool reversePT = true, PTDataTy ty = PTDataTy::Diff) : BasePTData(reversePT, ty) { }
 
    virtual ~DiffPTData() { }
 
    virtual const DataSet& getDiffPts(Key& var) = 0;
 
    virtual bool computeDiffPts(Key& var, const DataSet& all) = 0;
 
    virtual void updatePropaPtsMap(Key& src, Key& dst) = 0;
 
    virtual void clearPropaPts(Key& var) = 0;
 
    static inline bool classof(const DiffPTData<Key, KeySet, Data, DataSet> *)
    {
        return true;
    }
    static inline bool classof(const PTData<Key, KeySet, Data, DataSet>* ptd)
    {
        return ptd->getPTDTY() == PTDataTy::Diff
               || ptd->getPTDTY() == PTDataTy::MutDiff
               || ptd->getPTDTY() == PTDataTy::PersDiff;
    }
};
 
template <typename Key, typename KeySet, typename Data, typename DataSet>
class DFPTData : public PTData<Key, KeySet, Data, DataSet>
{
public:
    typedef PTData<Key, KeySet, Data, DataSet> BasePTData;
    typedef typename BasePTData::PTDataTy PTDataTy;
 
    typedef NodeID LocID;
 
    DFPTData(bool reversePT = true, PTDataTy ty = BasePTData::DataFlow) : BasePTData(reversePT, ty) { }
 
    virtual ~DFPTData() { }
 
    virtual bool hasDFInSet(LocID loc) const = 0;
    virtual bool hasDFOutSet(LocID loc) const = 0;
 
    virtual bool hasDFOutSet(LocID loc, const Key& var) const = 0;
    virtual bool hasDFInSet(LocID loc, const Key& var) const = 0;
    virtual const DataSet& getDFInPtsSet(LocID loc, const Key& var) = 0;
    virtual const DataSet& getDFOutPtsSet(LocID loc, const Key& var) = 0;
 
    virtual bool updateDFInFromIn(LocID srcLoc, const Key& srcVar, LocID dstLoc, const Key& dstVar) = 0;
    virtual bool updateAllDFInFromIn(LocID srcLoc, const Key& srcVar, LocID dstLoc, const Key& dstVar) = 0;
    virtual bool updateDFInFromOut(LocID srcLoc, const Key& srcVar, LocID dstLoc, const Key& dstVar) = 0;
    virtual bool updateAllDFInFromOut(LocID srcLoc, const Key& srcVar, LocID dstLoc, const Key& dstVar) = 0;
 
    virtual bool updateDFOutFromIn(LocID srcLoc, const Key& srcVar, LocID dstLoc, const Key& dstVar) = 0;
    virtual bool updateAllDFOutFromIn(LocID loc, const Key& singleton, bool strongUpdates) = 0;
 
    virtual void clearAllDFOutUpdatedVar(LocID) = 0;
 
    virtual bool updateTLVPts(LocID srcLoc, const Key& srcVar, const Key& dstVar) = 0;
    virtual bool updateATVPts(const Key& srcVar, LocID dstLoc, const Key& dstVar) = 0;
 
    static inline bool classof(const DFPTData<Key, KeySet, Data, DataSet> *)
    {
        return true;
    }
 
    static inline bool classof(const PTData<Key, KeySet, Data, DataSet>* ptd)
    {
        return ptd->getPTDTY() == BasePTData::DataFlow
               || ptd->getPTDTY() == BasePTData::MutDataFlow
               || ptd->getPTDTY() == BasePTData::MutIncDataFlow
               || ptd->getPTDTY() == BasePTData::PersDataFlow
               || ptd->getPTDTY() == BasePTData::PersIncDataFlow;
    }
};
 
template <typename Key, typename KeySet, typename Data, typename DataSet, typename VersionedKey, typename VersionedKeySet>
class VersionedPTData : public PTData<Key, KeySet, Data, DataSet>
{
public:
    typedef PTData<Key, KeySet, Data, DataSet> BasePTData;
    typedef typename BasePTData::PTDataTy PTDataTy;
 
    VersionedPTData(bool reversePT = true, PTDataTy ty = PTDataTy::Versioned) : BasePTData(reversePT, ty) { }
 
    virtual ~VersionedPTData() { }
 
    virtual const DataSet& getPts(const VersionedKey& vk) = 0;
    virtual const VersionedKeySet& getVersionedKeyRevPts(const Data& datum) = 0;
 
    virtual bool addPts(const VersionedKey& vk, const Data& element) = 0;
 
    virtual bool unionPts(const VersionedKey& dstVar, const VersionedKey& srcVar) = 0;
    virtual bool unionPts(const VersionedKey& dstVar, const Key& srcVar) = 0;
    virtual bool unionPts(const Key& dstVar, const VersionedKey& srcVar) = 0;
    virtual bool unionPts(const VersionedKey& dstVar, const DataSet& srcDataSet) = 0;
 
    virtual void clearPts(const VersionedKey& vk, const Data& element) = 0;
    virtual void clearFullPts(const VersionedKey& vk) = 0;
 
    static inline bool classof(const VersionedPTData<Key, KeySet, Data, DataSet, VersionedKey, VersionedKeySet> *)
    {
        return true;
    }
 
    static inline bool classof(const PTData<Key, KeySet, Data, DataSet>* ptd)
    {
        return ptd->getPTDTY() == PTDataTy::Versioned
               || ptd->getPTDTY() == PTDataTy::MutVersioned
               || ptd->getPTDTY() == PTDataTy::PersVersioned;
    }
private:
    using BasePTData::getPts;
    using BasePTData::addPts;
    using BasePTData::unionPts;
    using BasePTData::clearPts;
    using BasePTData::clearFullPts;
};
 
} // End namespace SVF
 
#endif  // ABSTRACT_POINTSTO_H_