Partitioner.h

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

#include <Rose/BinaryAnalysis/Partitioner2/AddressUsageMap.h>
#include <Rose/BinaryAnalysis/Partitioner2/Configuration.h>
#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
#include <Rose/BinaryAnalysis/Partitioner2/Semantics.h>

#include <Rose/BinaryAnalysis/InstructionProvider.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/SymbolicSemantics.h>
#include <Rose/BinaryAnalysis/SerialIo.h>
#include <Rose/BinaryAnalysis/SourceLocations.h>
#include <Rose/BinaryAnalysis/Unparser/Settings.h>
#include <Rose/Progress.h>

#include <Sawyer/Attribute.h>
#include <Sawyer/Callbacks.h>
#include <Sawyer/IntervalSet.h>
#include <Sawyer/Map.h>
#include <Sawyer/Message.h>
#include <Sawyer/Optional.h>
#include <Sawyer/ProgressBar.h>
#include <Sawyer/SharedObject.h>
#include <Sawyer/SharedPointer.h>

#include <boost/filesystem.hpp>
#include <boost/format.hpp>
#include <boost/move/utility_core.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/serialization/version.hpp>

#include <ostream>
#include <set>
#include <string>
#include <vector>

// Derived classes needed for serialization
#include <Rose/BinaryAnalysis/Z3Solver.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherAarch32.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherAarch64.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherM68k.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherPowerpc.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/DispatcherX86.h>

// [Robb Matzke 2022-06-22]: deprecated. Needed because some user code doesn't include the old InstructionSemantics2 header
// files where this same thing is defined, yet they use InstructionSemantics2 because such things were once declared by this
// header file due to it originally including InstructionSemantics2 headers (which it no longer does).
namespace Rose { namespace BinaryAnalysis { namespace InstructionSemantics2 = InstructionSemantics; }}

// Define ROSE_PARTITIONER_MOVE if boost::move works. Mainly this is to work around a GCC bug that reports this error:
//
//   prototype for
//   'Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)'
//   does not match any in class 'Rose::BinaryAnalysis::Partitioner2::Partitioner'
//
// followed by saying that the exact same signature is one of the candidates:
//
//   candidates are:
//   Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)
//
// This is apparently GCC issue 49377 [https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49377] fixed in GCC-6.1.0.
#if __cplusplus >= 201103L
    #define ROSE_PARTITIONER_MOVE
#elif defined(__GNUC__)
    #if __GNUC__ > 5
       #define ROSE_PARTITIONER_MOVE
    #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
       #define ROSE_PARTITIONER_MOVE
    #endif
#endif

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

class ROSE_DLL_API Partitioner /*final*/
    : public Sawyer::SharedObject, public Sawyer::SharedFromThis<Partitioner>, public Sawyer::Attribute::Storage<> {
#ifdef ROSE_PARTITIONER_MOVE
    BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
#endif

    //
    //                                  Types
    //
public:
    using Ptr = PartitionerPtr;
    using ConstPtr = PartitionerConstPtr;
    // Callback list types
    typedef Sawyer::Callbacks<CfgAdjustmentCallback::Ptr> CfgAdjustmentCallbacks; 
    typedef Sawyer::Callbacks<BasicBlockCallbackPtr> BasicBlockCallbacks; 
    typedef std::vector<FunctionPrologueMatcherPtr> FunctionPrologueMatchers; 
    typedef std::vector<FunctionPaddingMatcherPtr> FunctionPaddingMatchers; 
    struct Thunk {
        BasicBlockPtr bblock;                           
        rose_addr_t target;                             
        Thunk(const BasicBlockPtr&, rose_addr_t target);
        ~Thunk();
    };

    typedef Sawyer::Container::Map<rose_addr_t, std::string> AddressNameMap;

    //
    //                                  Data members
    //
private:
    BasePartitionerSettings settings_;                  // settings adjustable from the command-line
    Configuration config_;                              // configuration information about functions, blocks, etc.
    InstructionProvider::Ptr instructionProvider_;      // cache for all disassembled instructions
    MemoryMap::Ptr memoryMap_;                          // description of memory, especially insns and non-writable
    SgAsmInterpretation *interpretation_;               // Interpretation corresponding to the memory map
    ControlFlowGraph cfg_;                              // basic blocks that will become part of the ROSE AST
    CfgVertexIndex vertexIndex_;                        // Vertex-by-address index for the CFG
    AddressUsageMap aum_;                               // How addresses are used for each address represented by the CFG
    SmtSolverPtr solver_;                               // Satisfiable modulo theory solver used by semantic expressions
    Functions functions_;                               // List of all attached functions by entry address
    bool autoAddCallReturnEdges_;                       // Add E_CALL_RETURN edges when blocks are attached to CFG?
    bool assumeFunctionsReturn_;                        // Assume that unproven functions return to caller?
    size_t stackDeltaInterproceduralLimit_;             // Max depth of call stack when computing stack deltas
    AddressNameMap addressNames_;                       // Names for various addresses
    SourceLocations sourceLocations_;                   // Mapping between source locations and addresses
    SemanticMemoryParadigm semanticMemoryParadigm_;     // Slow and precise, or fast and imprecise?
    Unparser::BasePtr unparser_;                        // For unparsing things to pseudo-assembly
    Unparser::BasePtr insnUnparser_;                    // For unparsing single instructions in diagnostics
    Unparser::BasePtr insnPlainUnparser_;               // For unparsing just instruction mnemonic and operands

    // Callback lists
    CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
    BasicBlockCallbacks basicBlockCallbacks_;
    FunctionPrologueMatchers functionPrologueMatchers_;
    FunctionPaddingMatchers functionPaddingMatchers_;

    // Special CFG vertices.
    ControlFlowGraph::VertexIterator undiscoveredVertex_;
    ControlFlowGraph::VertexIterator indeterminateVertex_;
    ControlFlowGraph::VertexIterator nonexistingVertex_;
    static const size_t nSpecialVertices = 3;

    // Optional cached information
    Sawyer::Optional<rose_addr_t> elfGotVa_;            // address of ELF GOT, set by findElfGotVa

    // Protects the following data members
    mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
    Progress::Ptr progress_;                            // Progress reporter to update, or null
    mutable size_t cfgProgressTotal_;                   // Expected total for the CFG progress bar; initialized at first report

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

    template<class S>
    void serializeCommon(S &s, const unsigned version) {
        s.template register_type<InstructionSemantics::SymbolicSemantics::SValue>();
        s.template register_type<InstructionSemantics::SymbolicSemantics::RiscOperators>();
#ifdef ROSE_ENABLE_ASM_AARCH64
        s.template register_type<InstructionSemantics::DispatcherAarch64>();
#endif
#ifdef ROSE_ENABLE_ASM_AARCH32
        s.template register_type<InstructionSemantics::DispatcherAarch32>();
#endif
        s.template register_type<InstructionSemantics::DispatcherX86>();
        s.template register_type<InstructionSemantics::DispatcherM68k>();
        s.template register_type<InstructionSemantics::DispatcherPowerpc>();
        s.template register_type<SymbolicExpression::Interior>();
        s.template register_type<SymbolicExpression::Leaf>();
        s.template register_type<Z3Solver>();
        s.template register_type<Semantics::SValue>();
        s.template register_type<Semantics::MemoryListState>();
        s.template register_type<Semantics::MemoryMapState>();
        s.template register_type<Semantics::RegisterState>();
        s.template register_type<Semantics::State>();
        s.template register_type<Semantics::RiscOperators>();
        s & BOOST_SERIALIZATION_NVP(settings_);
        // s & config_;                         -- FIXME[Robb P Matzke 2016-11-08]
        s & BOOST_SERIALIZATION_NVP(instructionProvider_);
        s & BOOST_SERIALIZATION_NVP(memoryMap_);
        s & BOOST_SERIALIZATION_NVP(cfg_);
        // s & vertexIndex_;                    -- initialized by rebuildVertexIndices
        s & BOOST_SERIALIZATION_NVP(aum_);
        // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
        s & BOOST_SERIALIZATION_NVP(functions_);
        s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
        s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
        s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
        s & BOOST_SERIALIZATION_NVP(addressNames_);
        if (version >= 1)
            s & BOOST_SERIALIZATION_NVP(sourceLocations_);
        s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
        // s & unparser_;                       -- not saved; restored from disassembler
        // s & cfgAdjustmentCallbacks_;         -- not saved/restored
        // s & basicBlockCallbacks_;            -- not saved/restored
        // s & functionPrologueMatchers_;       -- not saved/restored
        // s & functionPaddingMatchers_;        -- not saved/restored
        // s & undiscoveredVertex_;             -- initialized by rebuildVertexIndices
        // s & indeterminateVertex_;            -- initialized by rebuildVertexIndices
        // s & nonexistingVertex_;              -- initialized by rebuildVertexIndices
        if (version >= 2)
            s & BOOST_SERIALIZATION_NVP(elfGotVa_);
        // s & progress_;                       -- not saved/restored
        // s & cfgProgressTotal_;               -- not saved/restored
    }

    template<class S>
    void save(S &s, const unsigned version) const {
        const_cast<Partitioner*>(this)->serializeCommon(s, version);
        if (version >= 3)
            saveAst(s, interpretation_);
    }

    template<class S>
    void load(S &s, const unsigned version) {
        serializeCommon(s, version);
        if (version >= 3) {
            SgNode *node = restoreAst(s);
            interpretation_ = isSgAsmInterpretation(node);
            ASSERT_require(!node || interpretation_);
        }
        rebuildVertexIndices();
    }

    BOOST_SERIALIZATION_SPLIT_MEMBER();
#endif

    //
    //                                  Constructors
    //
private:
    // Partitioner objects are reference counted and always allocated on the heap. Use the `instance` methods to construct
    // these objects.  Also, since the Partitioner class is final, we make the constructors private instead of the usual
    // protected constructors elsewhere in ROSE.
    Partitioner();
    Partitioner(const Disassembler::BasePtr&, const MemoryMap::Ptr&);
public:
    ~Partitioner();

public:
    static Ptr instance();

    static Ptr instance(const Disassembler::BasePtr&, const MemoryMap::Ptr&);

    static PartitionerPtr instanceFromRbaFile(const boost::filesystem::path&, SerialIo::Format = SerialIo::BINARY);

    void saveAsRbaFile(const boost::filesystem::path &name, SerialIo::Format fmt) const;

#ifdef ROSE_PARTITIONER_MOVE

    Partitioner(BOOST_RV_REF(Partitioner));

    Partitioner& operator=(BOOST_RV_REF(Partitioner));
#else
    // These are unsafe
    Partitioner(const Partitioner&);
    Partitioner& operator=(const Partitioner&);
#endif

    bool isDefaultConstructed() const;

    void clear();

    Configuration& configuration();
    const Configuration& configuration() const;
    InstructionProvider& instructionProvider();
    const InstructionProvider& instructionProvider() const;
    MemoryMap::Ptr memoryMap() const;

    SgAsmInterpretation *interpretation() const;
    void interpretation(SgAsmInterpretation*);
    bool addressIsExecutable(rose_addr_t) const;


    //
    //                                  Unparsing
    //
public:
    Unparser::BasePtr unparser() const;
    void unparser(const Unparser::BasePtr&);
    Unparser::BasePtr insnUnparser() const;
    void insnUnparser(const Unparser::BasePtr&);
    void configureInsnUnparser(const Unparser::BasePtr&) const;

    void configureInsnPlainUnparser(const Unparser::BasePtr&) const;

    std::string unparse(SgAsmInstruction*) const;
    void unparse(std::ostream&, SgAsmInstruction*) const;
    void unparse(std::ostream&, const BasicBlockPtr&) const;
    void unparse(std::ostream&, const DataBlockPtr&) const;
    void unparse(std::ostream&, const FunctionPtr&) const;
    void unparse(std::ostream&) const;
    std::string unparsePlain(SgAsmInstruction*) const;

    //
    //                                  Partitioner CFG queries
    //
public:
    size_t nBytes() const;

    ControlFlowGraph::VertexIterator undiscoveredVertex();
    ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const;
    ControlFlowGraph::VertexIterator indeterminateVertex();
    ControlFlowGraph::ConstVertexIterator indeterminateVertex() const;
    ControlFlowGraph::VertexIterator nonexistingVertex();
    ControlFlowGraph::ConstVertexIterator nonexistingVertex() const;
    const ControlFlowGraph& cfg() const;

    const AddressUsageMap& aum() const;

    AddressUsageMap aum(const FunctionPtr&) const;

    std::vector<AddressUser> users(rose_addr_t) const;

    std::set<rose_addr_t> ghostSuccessors() const;

    bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge, const FunctionPtr&) const;
    bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge, const FunctionPtr&) const;
    bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge) const;
    bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge) const;
    bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge) const;
    bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge, const FunctionPtr &sourceFunction) const;
    bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge, const FunctionPtr &sourceFunction,
                               const FunctionPtr &targetFunction) const;

    bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge) const;
    bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge, const FunctionPtr &sourceFunction) const;
    bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge, const FunctionPtr &sourceFunction,
                               const FunctionPtr &targetFunction) const;
    //
    //                                  Partitioner instruction operations
    //
public:
    size_t nInstructions() const;

    AddressUser instructionExists(rose_addr_t startVa) const;
    AddressUser instructionExists(SgAsmInstruction *insn) const;
    ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;

    std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const;

    std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const;

    std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const;

    AddressInterval instructionExtent(SgAsmInstruction*) const;

    SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const;

    CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const;



    //
    //                                  Partitioner basic block placeholder operations
    //
public:
     size_t nPlaceholders() const;

    bool placeholderExists(rose_addr_t startVa) const;

    ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa);
    ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const;
    ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa);

    BasicBlockPtr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
    BasicBlockPtr erasePlaceholder(rose_addr_t startVa) /*final*/;
    //
    //                                  Partitioner basic block operations
    //
public:
    bool basicBlockSemanticsAutoDrop() const;
    void basicBlockSemanticsAutoDrop(bool);
    void basicBlockDropSemantics() const;

    size_t nBasicBlocks() const;

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

    BasicBlockPtr basicBlockExists(rose_addr_t startVa) const;
    BasicBlockPtr basicBlockExists(const BasicBlockPtr&) const;
    std::vector<BasicBlockPtr> basicBlocksOverlapping(const AddressInterval&) const;

    std::vector<BasicBlockPtr> basicBlocksSpanning(const AddressInterval&) const;

    std::vector<BasicBlockPtr> basicBlocksContainedIn(const AddressInterval&) const;

    BasicBlockPtr basicBlockContainingInstruction(rose_addr_t insnVa) const;

    AddressIntervalSet basicBlockInstructionExtent(const BasicBlockPtr&) const;

    AddressIntervalSet basicBlockDataExtent(const BasicBlockPtr&) const;

    BasicBlockPtr detachBasicBlock(rose_addr_t startVa);
    BasicBlockPtr detachBasicBlock(const BasicBlockPtr &basicBlock);
    BasicBlockPtr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder);
    ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
                                                        SgAsmInstruction *insn);

    void attachBasicBlock(const BasicBlockPtr&);
    void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlockPtr&);
    BasicBlockPtr discoverBasicBlock(rose_addr_t startVa) const;
    BasicBlockPtr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const;
    BasicBlockSuccessors basicBlockSuccessors(const BasicBlockPtr&, Precision::Level precision = Precision::HIGH) const;

    std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlockPtr&, bool *isComplete=NULL) const;

    std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlockPtr&) const;

    bool basicBlockIsFunctionCall(const BasicBlockPtr&, Precision::Level precision = Precision::HIGH) const;

    bool basicBlockIsFunctionReturn(const BasicBlockPtr&) const;

     bool basicBlockPopsStack(const BasicBlockPtr&) const;

    InstructionSemantics::BaseSemantics::SValuePtr
    basicBlockStackDeltaIn(const BasicBlockPtr&, const FunctionPtr &function) const;

    InstructionSemantics::BaseSemantics::SValuePtr
    basicBlockStackDeltaOut(const BasicBlockPtr&, const FunctionPtr &function) const;
    void forgetStackDeltas() const;
    void forgetStackDeltas(const FunctionPtr&) const;
    size_t stackDeltaInterproceduralLimit() const;
    void stackDeltaInterproceduralLimit(size_t);
    Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlockPtr&) const;
    Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const;
    void basicBlockMayReturnReset() const;

private:
    // Per-vertex data used during may-return analysis
    struct MayReturnVertexInfo {
        enum State {INIT, CALCULATING, FINISHED};
        State state;                                        // current state of vertex
        bool processedCallees;                              // have we processed BBs this vertex calls?
        boost::logic::tribool anyCalleesReturn;             // do any of those called BBs have a true may-return value?
        boost::logic::tribool result;                       // final result (eventually cached in BB)
        MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
    };

    // Is edge significant for analysis? See .C file for full documentation.
    bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
                                    std::vector<MayReturnVertexInfo> &vertexInfo) const;

    // Determine (and cache in vertexInfo) whether any callees return.
    boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
                                                    std::vector<MayReturnVertexInfo> &vertexInfo) const;

    // Maximum may-return result from significant successors including phantom call-return edge.
    boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
                                                       std::vector<MayReturnVertexInfo> &vertexInfo) const;

    // The guts of the may-return analysis
    Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
                                                       std::vector<MayReturnVertexInfo> &vertexInfo) const;



    //
    //                                  Partitioner data block operations
    //
public:
    size_t nDataBlocks() const;

    DataBlockPtr dataBlockExists(const DataBlockPtr&) const;

    DataBlockPtr findBestDataBlock(const AddressInterval&) const;

    DataBlockPtr attachDataBlock(const DataBlockPtr&);

    void detachDataBlock(const DataBlockPtr&);

    DataBlockPtr attachDataBlockToFunction(const DataBlockPtr&, const FunctionPtr&);

    DataBlockPtr attachDataBlockToBasicBlock(const DataBlockPtr&, const BasicBlockPtr&);

    std::vector<DataBlockPtr> dataBlocksOverlapping(const AddressInterval&) const;

    std::vector<DataBlockPtr> dataBlocksSpanning(const AddressInterval&) const;

    std::vector<DataBlockPtr> dataBlocksContainedIn(const AddressInterval&) const;

    AddressInterval dataBlockExtent(const DataBlockPtr&) const;

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



    //
    //                                  Partitioner function operations
    //
public:
    size_t nFunctions() const;

    FunctionPtr functionExists(rose_addr_t entryVa) const;
    FunctionPtr functionExists(const BasicBlockPtr &entryBlock) const;
    FunctionPtr functionExists(const FunctionPtr &function) const;
    std::vector<FunctionPtr> functions() const;

    std::vector<FunctionPtr> functionsOverlapping(const AddressInterval&) const;

    std::vector<FunctionPtr> functionsSpanning(const AddressInterval&) const;

    std::vector<FunctionPtr> functionsContainedIn(const AddressInterval&) const;

    AddressIntervalSet functionExtent(const FunctionPtr&) const;
    void functionExtent(const FunctionPtr &function, AddressIntervalSet &retval /*in,out*/) const;
    AddressIntervalSet functionBasicBlockExtent(const FunctionPtr &function) const;
    void functionBasicBlockExtent(const FunctionPtr &function, AddressIntervalSet &retval /*in,out*/) const;
    AddressIntervalSet functionDataBlockExtent(const FunctionPtr &function) const;
    void functionDataBlockExtent(const FunctionPtr &function, AddressIntervalSet &retval /*in,out*/) const;
    size_t attachFunction(const FunctionPtr&);
    size_t attachFunctions(const Functions&);
    FunctionPtr attachOrMergeFunction(const FunctionPtr&);

    size_t attachFunctionBasicBlocks(const Functions&);
    size_t attachFunctionBasicBlocks(const FunctionPtr&);
    void detachFunction(const FunctionPtr&);

    std::vector<FunctionPtr>
    functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const;

    std::vector<FunctionPtr>
    functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const;

    std::vector<FunctionPtr>
    functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const;

    std::vector<FunctionPtr>
    functionsOwningBasicBlock(const BasicBlockPtr&, bool doSort = true) const;

    template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
    std::vector<FunctionPtr>
    functionsOwningBasicBlocks(const Container &bblocks) const {
        std::vector<FunctionPtr> retval;
        for (const typename Container::value_type& bblock: bblocks) {
            for (const FunctionPtr &function: functionsOwningBasicBlock(bblock, false))
                insertUnique(retval, function, sortFunctionsByAddress);
        }
        return retval;
    }
    std::vector<FunctionPtr> discoverCalledFunctions() const;

    std::vector<FunctionPtr> discoverFunctionEntryVertices() const;

    Sawyer::Optional<Thunk> functionIsThunk(const FunctionPtr&) const;

    void discoverFunctionBasicBlocks(const FunctionPtr &function) const;

    std::set<rose_addr_t> functionGhostSuccessors(const FunctionPtr&) const;

    FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const;

    InstructionSemantics::BaseSemantics::SValuePtr functionStackDelta(const FunctionPtr &function) const;

    void allFunctionStackDelta() const;

    Sawyer::Optional<bool> functionOptionalMayReturn(const FunctionPtr &function) const;

    void allFunctionMayReturn() const;

    const CallingConvention::Analysis& functionCallingConvention(const FunctionPtr&) const;
    const CallingConvention::Analysis& functionCallingConvention(const FunctionPtr&,
                                                                 const CallingConvention::Definition::Ptr &dflt) const;
    void allFunctionCallingConvention() const;
    void allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt) const;

    CallingConvention::Dictionary functionCallingConventionDefinitions(const FunctionPtr&) const;
    CallingConvention::Dictionary functionCallingConventionDefinitions(const FunctionPtr&,
                                                                       const CallingConvention::Definition::Ptr&) const;
    void allFunctionCallingConventionDefinition() const;
    void allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr&) const;
    void fixInterFunctionEdges();
    void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&);
    bool functionIsNoop(const FunctionPtr&) const;

    void allFunctionIsNoop() const;

    void forgetFunctionIsNoop() const;
    void forgetFunctionIsNoop(const FunctionPtr&) const;
    std::set<rose_addr_t> functionDataFlowConstants(const FunctionPtr&) const;



    //
    //                                  Callbacks
    //
public:
    CfgAdjustmentCallbacks& cfgAdjustmentCallbacks();
    const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const;
    BasicBlockCallbacks& basicBlockCallbacks();
    const BasicBlockCallbacks& basicBlockCallbacks() const;
public:
    FunctionPrologueMatchers& functionPrologueMatchers();
    const FunctionPrologueMatchers& functionPrologueMatchers() const;
    std::vector<FunctionPtr> nextFunctionPrologue(rose_addr_t startVa);
    std::vector<FunctionPtr> nextFunctionPrologue(rose_addr_t startVa, rose_addr_t &lastSearchedVa /*out*/);
public:
    FunctionPaddingMatchers& functionPaddingMatchers();
    const FunctionPaddingMatchers& functionPaddingMatchers() const;
    DataBlockPtr matchFunctionPadding(const FunctionPtr&);



    //
    //                                  Partitioner miscellaneous
    //
public:
    void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true, bool computeProperties=true) const;

    void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(), bool showNeighbors=true) const;

    static std::string vertexName(const ControlFlowGraph::Vertex&);
    std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const;
    static std::string vertexNameEnd(const ControlFlowGraph::Vertex&);

    static std::string edgeNameSrc(const ControlFlowGraph::Edge&);
    std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const;
    static std::string edgeNameDst(const ControlFlowGraph::Edge&);
    std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const;
    static std::string edgeName(const ControlFlowGraph::Edge&);
    std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const;
    static std::string basicBlockName(const BasicBlockPtr&);

    static std::string dataBlockName(const DataBlockPtr&);

    static std::string functionName(const FunctionPtr&);

    void expandIndeterminateCalls();

    Progress::Ptr progress() const;
    void progress(const Progress::Ptr&);
    void updateProgress(const std::string &phase, double completion) const;

    void showStatistics() const;

    // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
    void checkConsistency() const;

    SgAsmGenericSection* elfGot(SgAsmElfFileHeader*);

    Sawyer::Optional<rose_addr_t> elfGotVa() const;



    //
    //                                  Settings
    //
public:

    const BasePartitionerSettings& settings() const;
    void settings(const BasePartitionerSettings&);
    void enableSymbolicSemantics(bool = true);
    void disableSymbolicSemantics();
    bool usingSymbolicSemantics() const;
    void autoAddCallReturnEdges(bool);
    bool autoAddCallReturnEdges() const;
    void assumeFunctionsReturn(bool);
    bool assumeFunctionsReturn() const;
    void addressName(rose_addr_t, const std::string&);
    const std::string& addressName(rose_addr_t) const;
    const AddressNameMap& addressNames() const;
    const SourceLocations& sourceLocations() const;
    SourceLocations& sourceLocations();
    void sourceLocations(const SourceLocations&);
    bool checkingCallBranch() const;
    void checkingCallBranch(bool);
    //
    //                                  Instruction semantics
    //
public:
    SemanticMemoryParadigm semanticMemoryParadigm() const;
    void semanticMemoryParadigm(SemanticMemoryParadigm);
    SmtSolverPtr smtSolver() const;

    InstructionSemantics::BaseSemantics::RiscOperatorsPtr newOperators() const;
    InstructionSemantics::BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const;
    InstructionSemantics::BaseSemantics::DispatcherPtr
    newDispatcher(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&) const;



    //
    //                                  Python API support functions
    //
#ifdef ROSE_ENABLE_PYTHON_API
    void pythonUnparse() const;
#endif



    //
    //                                  Partitioner internal utilities
    //
private:
    void init(const Disassembler::BasePtr&, const MemoryMap::Ptr&);
    void init(const Partitioner&);
    void updateCfgProgress();

private:
    // Convert a CFG vertex iterator from one partitioner to another.  This is called during copy construction when the source
    // and destination CFGs are identical.
    ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
                                                 ControlFlowGraph::ConstVertexIterator otherIter);

    // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
    // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
    ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);

    // Adjusts edges for a non-existing basic block.  This method erases all outgoing edges for the specified vertex and
    // then inserts a single edge from the vertex to the special "non-existing" vertex. */
    ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);

    // Implementation for the discoverBasicBlock methods.  The startVa must not be the address of an existing placeholder.
    BasicBlockPtr discoverBasicBlockInternal(rose_addr_t startVa) const;

    // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
    // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
    void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);

    // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
    // The call happens immediately after the CFG/AUM are updated.
    void bblockDetached(rose_addr_t startVa, const BasicBlockPtr &removedBlock);

    // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
    void rebuildVertexIndices();
};

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

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

#endif
#endif