Partitioner2/Engine.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_Engine_H
#define ROSE_BinaryAnalysis_Partitioner2_Engine_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS

#include <Rose/BasicTypes.h>
#include <Rose/BinaryAnalysis/Partitioner2/Exception.h>
#include <Rose/BinaryAnalysis/Partitioner2/Modules.h>
#include <Rose/BinaryAnalysis/SerialIo.h>

#include <Sawyer/DistinctList.h>
#include <Sawyer/SharedObject.h>
#include <Sawyer/SharedPointer.h>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

class Engine: public Sawyer::SharedObject, public Sawyer::SharedFromThis<Engine> {
    //                                  Internal data structures
public:
    using Ptr = EnginePtr;

    //--------------------------------------------------------------------------------------------------------------------------
public:
    struct Settings {
        LoaderSettings loader;                          
        DisassemblerSettings disassembler;              
        PartitionerSettings partitioner;                
        EngineSettings engine;                          
        AstConstructionSettings astConstruction;        
    private:
        friend class boost::serialization::access;

        template<class S>
        void serialize(S &s, unsigned version) {
            s & loader & disassembler & partitioner & engine & astConstruction;
        }

    public:
        ~Settings();
        Settings();
    };

    //--------------------------------------------------------------------------------------------------------------------------
public:
    class Exception: public Partitioner2::Exception {
    public:
        ~Exception() throw ();

        explicit Exception(const std::string&);
    };

    //--------------------------------------------------------------------------------------------------------------------------
public:
    class PositionalArgumentParser {
    public:
        virtual ~PositionalArgumentParser();
        PositionalArgumentParser();

        virtual std::vector<std::string> specimen(const std::vector<std::string>&) const = 0;
    };

    class AllPositionalArguments: public PositionalArgumentParser {
    public:
        virtual std::vector<std::string> specimen(const std::vector<std::string>&) const override;
    };

    class FirstPositionalArguments: public PositionalArgumentParser {
        size_t n_;
    public:
        explicit FirstPositionalArguments(size_t n);
        virtual std::vector<std::string> specimen(const std::vector<std::string>&) const override;
    };

    class GroupedPositionalArguments: public PositionalArgumentParser {
        size_t n_ = 0;
    public:
        GroupedPositionalArguments();
        explicit GroupedPositionalArguments(size_t);
        virtual std::vector<std::string> specimen(const std::vector<std::string>&) const override;
    };

    //--------------------------------------------------------------------------------------------------------------------------
protected:
    // Engine callback for handling instructions added to basic blocks.  This is called when a basic block is discovered,
    // before it's attached to a partitioner, so it shouldn't really be modifying any state in the engine, but rather only
    // preparing the basic block to be processed.
    class BasicBlockFinalizer: public BasicBlockCallback {
        typedef Sawyer::Container::Map<rose_addr_t /*target*/, std::vector<rose_addr_t> /*sources*/> WorkList;
    public:
        ~BasicBlockFinalizer();
    protected:
        BasicBlockFinalizer();
    public:
        static Ptr instance();
        virtual bool operator()(bool chain, const Args &args) override;
    private:
        void fixFunctionReturnEdge(const Args&);
        void fixFunctionCallEdges(const Args&);
        void addPossibleIndeterminateEdge(const Args&);
    };

    //--------------------------------------------------------------------------------------------------------------------------
private:
    // Basic blocks that need to be worked on next. These lists are adjusted whenever a new basic block (or placeholder) is
    // inserted or erased from the CFG.
    class BasicBlockWorkList: public CfgAdjustmentCallback {
        // The following lists are used for adding outgoing E_CALL_RETURN edges to basic blocks based on whether the basic
        // block is a call to a function that might return.  When a new basic block is inserted into the CFG (or a previous
        // block is removed, modified, and re-inserted), the operator() is called and conditionally inserts the block into the
        // "pendingCallReturn" list (if the block is a function call that lacks an E_CALL_RETURN edge and the function is known
        // to return or the analysis was incomplete).
        //
        // When we run out of other ways to create basic blocks, we process the pendingCallReturn list from back to front. If
        // the back block (which gets popped) has a positive may-return result then an E_CALL_RETURN edge is added to the CFG
        // and the normal recursive BB discovery is resumed. Otherwise if the analysis is incomplete the basic block is moved
        // to the processedCallReturn list.  The entire pendingCallReturn list is processed before proceeding.
        //
        // If there is no more pendingCallReturn work to be done, then the processedCallReturn blocks are moved to the
        // finalCallReturn list and finalCallReturn is sorted by approximate CFG height (i.e., leafs first). The contents
        // of the finalCallReturn list is then analyzed and the result (or the default may-return value for failed analyses)
        // is used to decide whether a new CFG edge should be created, possibly adding new basic block addresses to the
        // list of undiscovered blocks.
        //
        Sawyer::Container::DistinctList<rose_addr_t> pendingCallReturn_;   // blocks that might need an E_CALL_RETURN edge
        Sawyer::Container::DistinctList<rose_addr_t> processedCallReturn_; // call sites whose may-return was indeterminate
        Sawyer::Container::DistinctList<rose_addr_t> finalCallReturn_;     // indeterminate call sites awaiting final analysis

        Sawyer::Container::DistinctList<rose_addr_t> undiscovered_;        // undiscovered basic block list (last-in-first-out)
        EnginePtr engine_;                                                 // engine to which this callback belongs
        size_t maxSorts_;                                                  // max sorts before using unsorted lists
    public:
        ~BasicBlockWorkList();
    protected:
        BasicBlockWorkList(const EnginePtr &engine, size_t maxSorts);
    public:
        using Ptr = Sawyer::SharedPointer<BasicBlockWorkList>;
        static Ptr instance(const EnginePtr &engine, size_t maxSorts);
        virtual bool operator()(bool chain, const AttachedBasicBlock &args) override;
        virtual bool operator()(bool chain, const DetachedBasicBlock &args) override;
        Sawyer::Container::DistinctList<rose_addr_t>& pendingCallReturn();
        Sawyer::Container::DistinctList<rose_addr_t>& processedCallReturn();
        Sawyer::Container::DistinctList<rose_addr_t>& finalCallReturn();
        Sawyer::Container::DistinctList<rose_addr_t>& undiscovered();
        void moveAndSortCallReturn(const PartitionerConstPtr&);
    };

    //--------------------------------------------------------------------------------------------------------------------------
protected:
    // A work list providing constants from instructions that are part of the CFG.
    class CodeConstants: public CfgAdjustmentCallback {
    public:
        using Ptr = Sawyer::SharedPointer<CodeConstants>;

    private:
        std::set<rose_addr_t> toBeExamined_;            // instructions waiting to be examined
        std::set<rose_addr_t> wasExamined_;             // instructions we've already examined
        rose_addr_t inProgress_;                        // instruction that is currently in progress
        std::vector<rose_addr_t> constants_;            // constants for the instruction in progress

    public:
        ~CodeConstants();
    protected:
        CodeConstants();

    public:
        static Ptr instance();

        // Address of instruction being examined.
        rose_addr_t inProgress();

        // Possibly insert more instructions into the work list when a basic block is added to the CFG
        virtual bool operator()(bool chain, const AttachedBasicBlock &attached) override;

        // Possibly remove instructions from the worklist when a basic block is removed from the CFG
        virtual bool operator()(bool chain, const DetachedBasicBlock &detached) override;

        // Return the next available constant if any.
        Sawyer::Optional<rose_addr_t> nextConstant(const PartitionerConstPtr &partitioner);
    };

    //                                  Data members
private:
    std::string name_;                                  // factory name
    Settings settings_;                                 // Settings for the partitioner.
    SgAsmInterpretation *interp_;                       // interpretation set by loadSpecimen
    Disassembler::BasePtr disassembler_;                // not ref-counted yet, but don't destroy it since user owns it
    MemoryMapPtr map_;                                  // memory map initialized by load()
    BasicBlockWorkList::Ptr basicBlockWorkList_;        // what blocks to work on next
    CodeConstants::Ptr codeFunctionPointers_;           // generates constants that are found in instruction ASTs
    ProgressPtr progress_;                              // optional progress reporting
    std::vector<std::string> specimen_;                 // list of additional command line arguments (often file names)

    //                                  Construction and destruction
public:
    virtual ~Engine();

protected:
    Engine() = delete;
    Engine(const Engine&) = delete;
    Engine& operator=(const Engine&) = delete;

protected:
    Engine(const std::string &name, const Settings &settings);

public:
    // [Robb Matzke 2023-03-03]: deprecated.
    // This used to create a binary engine, so we leave it in place for a while for improved backward compatibility
    static EngineBinaryPtr instance() ROSE_DEPRECATED("use Engine::forge or EngineBinary::instance");

private:
    void init();

    //                                  Command-line processing
public:

    virtual std::list<Sawyer::CommandLine::SwitchGroup> commandLineSwitches();

    std::list<Sawyer::CommandLine::SwitchGroup> allCommandLineSwitches();

    virtual std::pair<std::string/*title*/, std::string /*doc*/> specimenNameDocumentation() = 0;

    static std::list<std::pair<std::string /*title*/, std::string /*doc*/>> allSpecimenNameDocumentation();

    virtual void addToParser(Sawyer::CommandLine::Parser&);

    void addAllToParser(Sawyer::CommandLine::Parser&);

    virtual Sawyer::CommandLine::Parser commandLineParser(const std::string &purpose, const std::string &description);

    //                                  Factories
public:
    static void registerFactory(const EnginePtr &factory);

    static bool deregisterFactory(const EnginePtr &factory);

    static std::vector<EnginePtr> registeredFactories();

    //---------------------------------------------------------
    // These operate on specimens
    //---------------------------------------------------------

    static EnginePtr forge(const std::vector<std::string> &specimen);
    static EnginePtr forge(const std::string &specimen);

    //---------------------------------------------------------
    // These operate on arguments as std::vector<std::string>
    //---------------------------------------------------------

    // all args
    static EnginePtr forge(const std::vector<std::string> &arguments, Sawyer::CommandLine::Parser&,
                           const PositionalArgumentParser&, const Settings&);

    // default settings
    static EnginePtr forge(const std::vector<std::string> &arguments, Sawyer::CommandLine::Parser&,
                           const PositionalArgumentParser&);

    // default positional parser
    static EnginePtr forge(const std::vector<std::string> &arguments, Sawyer::CommandLine::Parser&, const Settings&);

    // default positional parser and settings
    static EnginePtr forge(const std::vector<std::string> &arguments, Sawyer::CommandLine::Parser&);

    //---------------------------------------------------------
    // These operate on arguments as argc and argv
    //---------------------------------------------------------

    // all args
    static EnginePtr forge(int argc, char *argv[], Sawyer::CommandLine::Parser&, const PositionalArgumentParser&, const Settings&);

    // default settings
    static EnginePtr forge(int argc, char *argv[], Sawyer::CommandLine::Parser&, const PositionalArgumentParser&);

    // default positional parser
    static EnginePtr forge(int argc, char *argv[], Sawyer::CommandLine::Parser&, const Settings&);

    // default positional parser and settings
    static EnginePtr forge(int argc, char *argv[], Sawyer::CommandLine::Parser&);
    virtual bool matchFactory(const std::vector<std::string> &specimen) const = 0;

    virtual EnginePtr instanceFromFactory(const Settings&) = 0;

    bool isFactory() const;

    //                                  Top-level, do everything functions
public:
    SgAsmBlock* frontend(int argc, char *argv[],
                         const std::string &purpose, const std::string &description);
    virtual SgAsmBlock* frontend(const std::vector<std::string> &args,
                                 const std::string &purpose, const std::string &description) = 0;
    //                                  Basic top-level steps
public:
    virtual void reset();

    Sawyer::CommandLine::ParserResult parseCommandLine(int argc, char *argv[],
                                                       const std::string &purpose, const std::string &description) /*final*/;
    virtual Sawyer::CommandLine::ParserResult parseCommandLine(const std::vector<std::string> &args,
                                                               const std::string &purpose, const std::string &description);
    virtual SgAsmBlock* buildAst(const std::vector<std::string> &fileNames = std::vector<std::string>()) = 0;
    SgAsmBlock *buildAst(const std::string &fileName) /*final*/;
    // [Robb Matzke 2023-03-03]: deprecated
    // Save a partitioner and AST to a file.
    //
    // The specified partitioner and the binary analysis components of the AST are saved into the specified file, which is
    // created if it doesn't exist and truncated if it does exist. The name should end with a ".rba" extension. The file can
    // be loaded by passing its name to the @ref partition function or by calling @ref loadPartitioner.
    virtual void savePartitioner(const PartitionerConstPtr&, const boost::filesystem::path&, SerialIo::Format = SerialIo::BINARY)
        ROSE_DEPRECATED("use Partitioner::saveAsRbaFile");

    // [Robb Matzke 2023-03-03]: deprecated
    // Load a partitioner and an AST from a file.
    //
    // The specified RBA file is opened and read to create a new @ref Partitioner object and associated AST. The @ref
    // partition function also understands how to open RBA files.
    virtual PartitionerPtr loadPartitioner(const boost::filesystem::path&, SerialIo::Format = SerialIo::BINARY)
        ROSE_DEPRECATED("use Partitioner::instanceFromRbaFile");

    //                                  Command-line parsing
public:
    virtual SgAsmInterpretation* parseContainers(const std::vector<std::string> &fileNames) = 0;
    SgAsmInterpretation* parseContainers(const std::string &fileName) /*final*/;
    virtual MemoryMapPtr loadSpecimens(const std::vector<std::string> &fileNames = std::vector<std::string>()) = 0;
    MemoryMapPtr loadSpecimens(const std::string &fileName) /*final*/;
    virtual PartitionerPtr partition(const std::vector<std::string> &fileNames = std::vector<std::string>()) = 0;
    PartitionerPtr partition(const std::string &fileName) /*final*/;
    virtual void checkSettings();

    //                                  Container parsing
    //
    // top-level: parseContainers
public:
    virtual bool isRbaFile(const std::string&);

    virtual bool isNonContainer(const std::string&) = 0;

    virtual bool areContainersParsed() const = 0;

    //                                  Load specimens
    //
    // top-level: loadSpecimens
public:
    virtual bool areSpecimensLoaded() const;

    virtual void adjustMemoryMap();

    MemoryMapPtr memoryMap() const /*final*/;
    virtual void memoryMap(const MemoryMapPtr&);
    //                                  Disassembler
public:
    virtual Disassembler::BasePtr obtainDisassembler();
    virtual Disassembler::BasePtr obtainDisassembler(const Disassembler::BasePtr &hint);
    //                                  Partitioner high-level functions
    //
    // top-level: partition
public:
    virtual void checkCreatePartitionerPrerequisites() const;

    virtual PartitionerPtr createBarePartitioner();

    virtual PartitionerPtr createPartitioner() = 0;

    virtual void runPartitionerInit(const PartitionerPtr&) = 0;

    virtual void runPartitionerRecursive(const PartitionerPtr&) = 0;

    virtual void runPartitionerFinal(const PartitionerPtr&) = 0;

    virtual void runPartitioner(const PartitionerPtr&);

    //                                  Partitioner mid-level functions
    //
    // These are the functions called by the partitioner high-level stuff.  These are sometimes overridden in subclasses,
    // although it is more likely that the high-level stuff is overridden.
public:
    virtual void labelAddresses(const PartitionerPtr&, const Configuration&);

    virtual std::vector<DataBlockPtr> makeConfiguredDataBlocks(const PartitionerPtr&, const Configuration&);

    virtual std::vector<FunctionPtr> makeConfiguredFunctions(const PartitionerPtr&, const Configuration&);

    virtual void updateAnalysisResults(const PartitionerPtr&);

    //                                  Partitioner low-level functions
    //
    // These are functions that a subclass seldom overrides, and maybe even shouldn't override because of their complexity or
    // the way the interact with one another.
public:


    //                                  Build AST
public:
    // Used internally by ROSE's ::frontend disassemble instructions to build the AST that goes under each SgAsmInterpretation.
    static void disassembleForRoseFrontend(SgAsmInterpretation*);

    //                                  Settings and properties
public:
    const std::string& name() const /*final*/;
    void name(const std::string&);
    const Settings& settings() const /*final*/;
    Settings& settings() /*final*/;
    void settings(const Settings&) /*final*/;
    BasicBlockWorkList::Ptr basicBlockWorkList() const /*final*/;
    void basicBlockWorkList(const BasicBlockWorkList::Ptr&) /*final*/;

    CodeConstants::Ptr codeFunctionPointers() const /*final*/;
    void codeFunctionPointers(const CodeConstants::Ptr&) /*final*/;
    Disassembler::BasePtr disassembler() const;
    virtual void disassembler(const Disassembler::BasePtr&);
    SgAsmInterpretation* interpretation() const /*final*/;
    virtual void interpretation(SgAsmInterpretation*);
    ProgressPtr progress() const /*final*/;
    virtual void progress(const ProgressPtr&);
    const std::vector<std::string>& specimen() const /*final*/;
    virtual void specimen(const std::vector<std::string>&);
    //                                  Internal stuff
protected:
    // Similar to ::frontend but a lot less complicated.
    virtual SgProject* roseFrontendReplacement(const std::vector<boost::filesystem::path> &fileNames) = 0;
};

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

#endif
#endif