AddressUsageMap.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_AddressUsageMap_H
#define ROSE_BinaryAnalysis_Partitioner2_AddressUsageMap_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>

#include <AstSerialization.h>                           // rose

#include <Sawyer/IntervalMap.h>
#include <Sawyer/IntervalSet.h>
#include <Sawyer/Optional.h>

#include <boost/serialization/access.hpp>
#include <boost/serialization/vector.hpp>

#include <algorithm>
#include <ostream>
#include <string>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

// AddressUser

class AddressUser {
    SgAsmInstruction *insn_;
    std::vector<BasicBlockPtr> bblocks_;                // sorted and unique
    DataBlockPtr dblock_;

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned version) {
        transferAst(s, insn_);
        s & BOOST_SERIALIZATION_NVP(bblocks_);
        if (version < 1) {
            ASSERT_not_reachable("Rose::BinaryAnalysis::Partitioner2::AddressUser version 0 no longer supported");
        } else {
            s & BOOST_SERIALIZATION_NVP(dblock_);
        }
    }

#endif

public:
    AddressUser();

    AddressUser(SgAsmInstruction*, const BasicBlockPtr&);

    explicit AddressUser(const DataBlockPtr&);

    ~AddressUser();

    rose_addr_t address() const;

    bool isBasicBlock() const;

    bool isDataBlock() const;

    bool isEmpty() const;

    SgAsmInstruction* insn() const;

    BasicBlockPtr firstBasicBlock() const;

    const std::vector<BasicBlockPtr>& basicBlocks() const;

    void insertBasicBlock(const BasicBlockPtr &bblock);

    void eraseBasicBlock(const BasicBlockPtr &bblock);
    
    DataBlockPtr dataBlock() const;

    BasicBlockPtr isBlockEntry() const;

    bool operator==(const AddressUser &other) const;

    bool operator<(const AddressUser&) const;

    void print(std::ostream&) const;

    bool isConsistent() const;

    operator bool() const {
        return !isEmpty();
    }
};


// AddressUsers

class AddressUsers {
    std::vector<AddressUser> users_;                    // sorted

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(users_);
    }
#endif

public:
    AddressUsers();
    ~AddressUsers();

    explicit AddressUsers(SgAsmInstruction *insn, const BasicBlockPtr&);

    explicit AddressUsers(const DataBlockPtr&);

    SgAsmInstruction* instructionExists(SgAsmInstruction*) const;
    SgAsmInstruction* instructionExists(rose_addr_t va) const;
    BasicBlockPtr basicBlockExists(const BasicBlockPtr&) const;
    BasicBlockPtr basicBlockExists(rose_addr_t va) const;
    DataBlockPtr dataBlockExists(const DataBlockPtr&) const;
    DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
    AddressUser findInstruction(SgAsmInstruction*) const;
    AddressUser findInstruction(rose_addr_t va) const;
    AddressUser findBasicBlock(const BasicBlockPtr&) const;
    AddressUser findBasicBlock(rose_addr_t va) const;
    AddressUser findDataBlock(const DataBlockPtr&) const;
    AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
    AddressUser insertInstruction(SgAsmInstruction*, const BasicBlockPtr&);

    AddressUser insertDataBlock(const DataBlockPtr&);

    void insert(const AddressUsers&);

    SgAsmInstruction* eraseInstruction(SgAsmInstruction*, const BasicBlockPtr&);

    DataBlockPtr eraseDataBlock(const DataBlockPtr&);

    static bool selectAllUsers(const AddressUser&);

    static bool selectBasicBlocks(const AddressUser&);

    static bool selectDataBlocks(const AddressUser&);

    template<class UserPredicate>
    AddressUsers select(UserPredicate predicate) const {
        AddressUsers retval;
        for (const AddressUser &user: users_) {
            if (predicate(user))
                retval.users_.push_back(user);
        }
        return retval;
    }

    const std::vector<AddressUser>& addressUsers() const;

    AddressUsers instructionUsers() const;

    AddressUsers dataBlockUsers() const;

    std::vector<SgAsmInstruction*> instructions() const;

    std::vector<BasicBlockPtr> instructionOwners() const;

    std::vector<DataBlockPtr> dataBlocks() const;

    size_t size() const;

    bool isEmpty() const;

    AddressUsers intersection(const AddressUsers&) const;

    AddressUsers union_(const AddressUsers&) const;

    bool operator==(const AddressUsers &other) const;

    void print(std::ostream&) const;

    bool isConsistent() const;
};


// AddressUsageMap

class AddressUsageMap {
    using Map = Sawyer::Container::IntervalMap<AddressInterval, AddressUsers>;
    Map map_;

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(map_);
    }
#endif

public:
    AddressUsageMap();
    ~AddressUsageMap();

public:
    bool isEmpty() const;

    void clear();

    size_t size() const;

    AddressInterval hull() const;

    AddressIntervalSet extent() const;

    bool exists(rose_addr_t) const;

    bool anyExists(const AddressInterval&) const;
    bool anyExists(const AddressIntervalSet&) const;
    AddressIntervalSet unusedExtent(size_t nBits) const;
    AddressIntervalSet unusedExtent(const AddressInterval&) const;
    AddressIntervalSet unusedExtent(const AddressIntervalSet&) const;
    AddressInterval nextUnused(rose_addr_t minVa) const;

    SgAsmInstruction* instructionExists(SgAsmInstruction*) const;
    SgAsmInstruction* instructionExists(rose_addr_t va) const;
    BasicBlockPtr basicBlockExists(const BasicBlockPtr&) const;
    BasicBlockPtr basicBlockExists(rose_addr_t startOfBlock) const;
    DataBlockPtr dataBlockExists(const DataBlockPtr&) const;
    DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
    AddressUser findInstruction(SgAsmInstruction*) const;
    AddressUser findInstruction(rose_addr_t va) const;
    AddressUser findBasicBlock(const BasicBlockPtr&) const;
    AddressUser findBasicBlock(rose_addr_t va) const;
    AddressUser findDataBlock(const DataBlockPtr&) const;
    AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
    AddressUser insertInstruction(SgAsmInstruction*, const BasicBlockPtr&);

    AddressUser insertDataBlock(const DataBlockPtr&);

    SgAsmInstruction* eraseInstruction(SgAsmInstruction*, const BasicBlockPtr&);

    DataBlockPtr eraseDataBlock(const DataBlockPtr&);

    AddressUsers spanning(const AddressInterval&) const;

    template<class UserPredicate>
    AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
        AddressUsers retval;
        size_t nIters = 0;
        for (const Map::Node &node: map_.findAll(interval)) {
            AddressUsers users = node.value().select(userPredicate);
            retval = 0==nIters++ ? users : retval.intersection(users);
            if (retval.isEmpty())
                break;
        }
        return retval;
    }
    AddressUsers overlapping(const AddressInterval&) const;

    template<class UserPredicate>
    AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
        AddressUsers retval;
        for (const Map::Node &node: map_.findAll(interval))
            retval.insert(node.value().select(userPredicate));
        return retval;
    }
    // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
    AddressUsers containedIn(const AddressInterval&) const;

    //template<class UserPredicate>
    //AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const {...}
    Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const;

    void print(std::ostream&, const std::string &prefix="") const;

    void checkConsistency() const;
};

} // namespace
} // namespace
} // namespace

// Class versions must be at global scope
BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::AddressUser, 1);

#endif
#endif