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/AddressUsageMap.h>
#include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
#include <Rose/BinaryAnalysis/Partitioner2/Config.h>
#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
#include <Rose/BinaryAnalysis/Partitioner2/DataBlock.h>
#include <Rose/BinaryAnalysis/Partitioner2/Function.h>
#include <Rose/BinaryAnalysis/Partitioner2/FunctionCallGraph.h>
#include <Rose/BinaryAnalysis/Partitioner2/InstructionProvider.h>
#include <Rose/BinaryAnalysis/Partitioner2/Modules.h>
#include <Rose/BinaryAnalysis/Partitioner2/Reference.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/SharedPointer.h>

#include <Rose/BinaryAnalysis/SourceLocations.h>
#include <Rose/BinaryAnalysis/Unparser/Settings.h>
#include <Rose/Progress.h>

#include <boost/filesystem.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/YicesSolver.h>
#include <Rose/BinaryAnalysis/Z3Solver.h>
#include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherAarch32.h>
#include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherAarch64.h>
#include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherM68k.h>
#include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherPowerpc.h>
#include <Rose/BinaryAnalysis/InstructionSemantics2/DispatcherX86.h>

// 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: public Sawyer::Attribute::Storage<> {     // final
#ifdef ROSE_PARTITIONER_MOVE
    BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
#endif

public:
    typedef Sawyer::Callbacks<CfgAdjustmentCallback::Ptr> CfgAdjustmentCallbacks; 
    typedef Sawyer::Callbacks<BasicBlockCallback::Ptr> BasicBlockCallbacks; 
    typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers; 
    typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers; 
    struct Thunk {
        BasicBlock::Ptr bblock;                         
        rose_addr_t target;                             
        Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
    };

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

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
    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<InstructionSemantics2::SymbolicSemantics::SValue>();
        s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
#ifdef ROSE_ENABLE_ASM_AARCH64
        s.template register_type<InstructionSemantics2::DispatcherAarch64>();
#endif
#ifdef ROSE_ENABLE_ASM_AARCH32
        s.template register_type<InstructionSemantics2::DispatcherAarch32>();
#endif
        s.template register_type<InstructionSemantics2::DispatcherX86>();
        s.template register_type<InstructionSemantics2::DispatcherM68k>();
        s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
        s.template register_type<SymbolicExpr::Interior>();
        s.template register_type<SymbolicExpr::Leaf>();
        s.template register_type<YicesSolver>();
        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);
    }

    template<class S>
    void load(S &s, const unsigned version) {
        serializeCommon(s, version);
        rebuildVertexIndices();
    }

    BOOST_SERIALIZATION_SPLIT_MEMBER();
#endif



    //
    //                                  Constructors
    //
public:
    Partitioner();

    Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);

#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

    ~Partitioner();

    bool isDefaultConstructed() const { return instructionProvider_ == NULL; }

    void clear() /*final*/;

    Configuration& configuration() { return config_; }
    const Configuration& configuration() const { return config_; }
    InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
    const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
    MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
    bool addressIsExecutable(rose_addr_t va) const /*final*/ {
        return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
    }

    //
    //                                  Unparsing
    //

    Unparser::BasePtr unparser() const /*final*/;
    void unparser(const Unparser::BasePtr&) /*final*/;
    Unparser::BasePtr insnUnparser() const /*final*/;
    void insnUnparser(const Unparser::BasePtr&) /*final*/;
    void configureInsnUnparser(const Unparser::BasePtr&) const /*final*/;

    void configureInsnPlainUnparser(const Unparser::BasePtr&) const /*final*/;

    std::string unparse(SgAsmInstruction*) const;
    void unparse(std::ostream&, SgAsmInstruction*) const;
    void unparse(std::ostream&, const BasicBlock::Ptr&) const;
    void unparse(std::ostream&, const DataBlock::Ptr&) const;
    void unparse(std::ostream&, const Function::Ptr&) const;
    void unparse(std::ostream&) const;
    std::string unparsePlain(SgAsmInstruction*) const;

    //
    //                                  Partitioner CFG queries
    //
public:
    size_t nBytes() const /*final*/ { return aum_.size(); }

    ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
        return undiscoveredVertex_;
    }
    ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
        return undiscoveredVertex_;
    }
    ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
        return indeterminateVertex_;
    }
    ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
        return indeterminateVertex_;
    }
    ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
        return nonexistingVertex_;
    }
    ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
        return nonexistingVertex_;
    }
    const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }

    const AddressUsageMap& aum() const /*final*/ { return aum_; }

    AddressUsageMap aum(const Function::Ptr&) const /*final*/;

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

    std::set<rose_addr_t> ghostSuccessors() const /*final*/;

    bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
                               const Function::Ptr &function = Function::Ptr()) const /*final*/;
    bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
                               const Function::Ptr &function = Function::Ptr()) const /*final*/;
    bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
                               const Function::Ptr &sourceFunction = Function::Ptr(),
                               const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
    bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
                               const Function::Ptr &sourceFunction = Function::Ptr(),
                               const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
    //
    //                                  Partitioner instruction operations
    //
public:
    size_t nInstructions() const /*final*/;

    AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
        return aum_.findInstruction(startVa);
    }
    AddressUser instructionExists(SgAsmInstruction *insn) const /*final*/ {
        return aum_.findInstruction(insn);
    }
    ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;

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

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

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

    AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;

    SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;

    CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;



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

    bool placeholderExists(rose_addr_t startVa) const /*final*/;

    ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
        if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
            return *found;
        return cfg_.vertices().end();
    }
    ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
        if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
            return *found;
        return cfg_.vertices().end();
    }
    ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;

    BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
    BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
    //
    //                                  Partitioner basic block operations
    //
public:
    bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
    void basicBlockSemanticsAutoDrop(bool b) { settings_.basicBlockSemanticsAutoDrop = b; }
    void basicBlockDropSemantics() const /*final*/;

    size_t nBasicBlocks() const /*final*/;

    std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;

    BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
    BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
    std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;

    std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;

    std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;

    BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;

    AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;

    AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;

    BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
    BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
    BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
    ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
                                                        SgAsmInstruction *insn) /*final*/;

    void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
    void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
    BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
    BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
    BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
                                                Precision::Level precision = Precision::HIGH) const /*final*/;

    std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;

    std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;

    bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;

    bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;

     bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;

    BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
    BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
    void forgetStackDeltas() const /*final*/;
    void forgetStackDeltas(const Function::Ptr&) const /*final*/;
    size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
    void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
    Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;

    Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
    void basicBlockMayReturnReset() const /*final*/;

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 /*final*/;

    DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;

    DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;

    DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;

    void detachDataBlock(const DataBlock::Ptr&) /*final*/;

    DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;

    DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;

    std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;

    std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;

    std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;

    AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;

    std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;



    //
    //                                  Partitioner function operations
    //
public:
    size_t nFunctions() const /*final*/ { return functions_.size(); }

    Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
    Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
    Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
    std::vector<Function::Ptr> functions() const /*final*/;

    std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;

    std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;

    std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;

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

    size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
    size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
    void detachFunction(const Function::Ptr&) /*final*/;

    std::vector<Function::Ptr>
    functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;

    std::vector<Function::Ptr>
    functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;

    std::vector<Function::Ptr>
    functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;

    std::vector<Function::Ptr>
    functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;

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

    std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;

    Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;

    void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;

    std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;

    FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;

    BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;

    void allFunctionStackDelta() const /*final*/;

    Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;

    void allFunctionMayReturn() const /*final*/;

    const CallingConvention::Analysis&
    functionCallingConvention(const Function::Ptr&,
                              const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
        const /*final*/;

    void
    allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
        const /*final*/;

    CallingConvention::Dictionary
    functionCallingConventionDefinitions(const Function::Ptr&,
                                         const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
        const /*final*/;

    void
    allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
                                           CallingConvention::Definition::Ptr()) const /*final*/;

    void fixInterFunctionEdges() /*final*/;
    void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
    bool functionIsNoop(const Function::Ptr&) const /*final*/;

    void allFunctionIsNoop() const /*final*/;

    void forgetFunctionIsNoop() const /*final*/;
    void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
    std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;



    //
    //                                  Callbacks
    //
public:
    CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
    const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
    BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
    const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
public:
    FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
    const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
    std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
    std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa, rose_addr_t &lastSearchedVa /*out*/) /*final*/;
public:
    FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
    const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
    DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;



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

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

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

    static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
    std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
    static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
    std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
    static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
    std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
    static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;

    static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;

    static std::string functionName(const Function::Ptr&) /*final*/;

    void expandIndeterminateCalls();

    Progress::Ptr progress() const /*final*/;
    void progress(const Progress::Ptr&) /*final*/;
    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 /*final*/ { return settings_; }
    void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
    void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
    void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
    bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
    void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
    bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
    void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
    bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
    void addressName(rose_addr_t, const std::string&) /*final*/;
    const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
    const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
    const SourceLocations& sourceLocations() const /*final*/ { return sourceLocations_; }
    SourceLocations& sourceLocations() /*final*/ { return sourceLocations_; }
    void sourceLocations(const SourceLocations &locs) { sourceLocations_ = locs; }
    bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
    void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
    //
    //                                  Instruction semantics
    //
public:
    SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
    void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
    SmtSolverPtr smtSolver() const /*final*/ { return solver_; }

    BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
    BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
    BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;



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



    //
    //                                  Partitioner internal utilities
    //
private:
    void init(Disassembler*, 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.
    BasicBlock::Ptr 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 BasicBlock::Ptr &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, 2);

#endif
#endif