SymbolicExpressionParser.h

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

#include <Rose/BinaryAnalysis/BasicTypes.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics.h>
#include <Rose/BinaryAnalysis/SymbolicExpression.h>
#include <Rose/Exception.h>
#include <Sawyer/BiMap.h>
#include <Sawyer/CommandLine.h>
#include <Sawyer/Message.h>
#include <Sawyer/SharedPointer.h>

namespace Rose {
namespace BinaryAnalysis {

class SymbolicExpressionParser {
public:

    class SyntaxError: public Rose::Exception {
    public:
        std::string inputName;                          
        unsigned lineNumber;                            
        unsigned columnNumber;                          
        SyntaxError(const std::string &mesg, const std::string &inputName, unsigned lineNumber, unsigned columnNumber);
        ~SyntaxError() throw () {}
        void print(std::ostream&) const;                
    };

    class SubstitutionError: public Rose::Exception {
    public:
        SubstitutionError(const std::string &mesg)
            : Rose::Exception(mesg) {}
        ~SubstitutionError() throw () {}
        void print(std::ostream&) const;
    };


    class Token {
    public:
        enum Type {
            NONE = 0,                                   
            LTPAREN,                                    
            RTPAREN,                                    
            BITVECTOR,                                  
            SYMBOL                                      
        };

    private:
        Type tokenType_;
        std::string lexeme_;                            // lexeme
        SymbolicExpression::Type exprType_;             // type for expression
        Sawyer::Container::BitVector bits_;             // bits representing constant terms
        unsigned lineNumber_, columnNumber_;            // for start of token

    public:
        Token()
            : tokenType_(NONE), lineNumber_(0), columnNumber_(0) {}

        Token(Type tokenType, const SymbolicExpression::Type &exprType, const std::string &lexeme,
              unsigned lineNumber, unsigned columnNumber)
            : tokenType_(tokenType), lexeme_(lexeme), exprType_(exprType),
              lineNumber_(lineNumber), columnNumber_(columnNumber) {
            ASSERT_forbid(BITVECTOR == tokenType);
        }

        Token(const Sawyer::Container::BitVector &bv, const SymbolicExpression::Type &exprType, const std::string &lexeme,
              unsigned lineNumber, unsigned columnNumber)
            : tokenType_(BITVECTOR), lexeme_(lexeme), exprType_(exprType), bits_(bv),
              lineNumber_(lineNumber), columnNumber_(columnNumber) {
            ASSERT_require(exprType.nBits() == bv.size());
        }

        SymbolicExpressionParser::SyntaxError syntaxError(const std::string &mesg, const std::string &name="input") const {
            return SymbolicExpressionParser::SyntaxError(mesg, name, lineNumber_, columnNumber_);
        }

        Type tokenType() const { return tokenType_; }

        const std::string &lexeme() const { return lexeme_; }

        SymbolicExpression::Type exprType() const { return exprType_; }

        const Sawyer::Container::BitVector& bits() const { return bits_; }

        unsigned lineNumber() const { return lineNumber_; }

        unsigned columnNumber() const { return columnNumber_; }
    };


    class TokenStream {
        std::istream &input_;
        std::string name_;
        unsigned lineNumber_, columnNumber_;
        const Token endToken_;
        std::vector<Token> tokens_;
        int readAhead_;

    public:
        explicit TokenStream(std::istream &input, const std::string &name="input",
                             unsigned lineNumber=1, unsigned columnNumber=0)
            : input_(input), name_(name), lineNumber_(lineNumber), columnNumber_(columnNumber), readAhead_(EOF) {
            init();
        }

        const std::string& name() const { return name_; }

        unsigned lineNumber() const { return lineNumber_; }

        unsigned columnNumber() const { return columnNumber_; }

        const Token& operator[](size_t idx);

        void shift(size_t n=1);

        int nextCharacter();

        int consumeCharacter();

        void consumeWhiteSpace();

        int consumeEscapeSequence();

        void consumeInlineComment();

        void consumeWhiteSpaceAndComments();

        std::string consumeTerm();

        SymbolicExpression::Type consumeType();

        Token scan();

    private:
        void init();

        // Try to fill the token vector so it contains tokens up through at least [idx]
        void fillTokenList(size_t idx);
    };


    class Expansion: public Sawyer::SharedObject {
        std::string title_;
        std::string docString_;
    public:
        virtual ~Expansion() {}

        typedef Sawyer::SharedPointer<Expansion> Ptr;

        const std::string& title() const { return title_; }
        void title(const std::string &s) { title_ = s; }
        const std::string& docString() const { return docString_; }
        void docString(const std::string &s) { docString_ = s; }
        virtual SymbolicExpression::Ptr delayedExpansion(const SymbolicExpression::Ptr &src, const SymbolicExpressionParser*) {
            return src;
        }
    };


    class AtomExpansion: public Expansion {
    public:
        typedef Sawyer::SharedPointer<AtomExpansion> Ptr;

        virtual SymbolicExpression::Ptr immediateExpansion(const Token &name) = 0;
    };

    typedef std::vector<AtomExpansion::Ptr> AtomTable;


    class OperatorExpansion: public Expansion {
    public:
        typedef Sawyer::SharedPointer<OperatorExpansion> Ptr;

    protected:
        SmtSolverPtr solver;                            // may be null

        explicit OperatorExpansion(const SmtSolverPtr &solver);

    public:
        virtual ~OperatorExpansion();

        virtual SymbolicExpression::Ptr immediateExpansion(const Token &name, const SymbolicExpression::Nodes &operands) = 0;
    };

    typedef std::vector<OperatorExpansion::Ptr> OperatorTable;


    class RegisterToValue: public AtomExpansion {
    public:
        typedef Sawyer::SharedPointer<RegisterToValue> Ptr;

    private:
        InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops_;

    protected:
        RegisterToValue(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops)
            : ops_(ops) {}

    public:
        static Ptr instance(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&);

        // internal
        SymbolicExpression::Ptr immediateExpansion(const SymbolicExpressionParser::Token&) override;
    };


    class RegisterSubstituter: public AtomExpansion {
    public:
        typedef Sawyer::SharedPointer<RegisterSubstituter> Ptr;

        // internal
        typedef Sawyer::Container::BiMap<RegisterDescriptor, SymbolicExpression::Ptr> RegToVarMap;

    private:
        RegisterDictionaryPtr regdict_;
        RegToVarMap reg2var_;
        InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops_;

    protected:
        RegisterSubstituter(const RegisterDictionaryPtr &regdict)
            : regdict_(regdict) {}

    public:
        static Ptr instance(const RegisterDictionaryPtr&);

        InstructionSemantics::BaseSemantics::RiscOperatorsPtr riscOperators() const {
            return ops_;
        }
        void riscOperators(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops) {
            ops_ = ops;
        }
        // internal
        SymbolicExpression::Ptr immediateExpansion(const SymbolicExpressionParser::Token&) override;
        SymbolicExpression::Ptr delayedExpansion(const SymbolicExpression::Ptr&, const SymbolicExpressionParser*) override;
    };


    class MemorySubstituter: public OperatorExpansion {
    public:
        typedef Sawyer::SharedPointer<MemorySubstituter> Ptr;

        // internal
        typedef Sawyer::Container::Map<SymbolicExpression::Ptr /*placeholder*/, SymbolicExpression::Ptr /*address*/> ExprToMem;

    private:
        ExprToMem exprToMem_;
        InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops_;

    protected:
        MemorySubstituter(const SmtSolver::Ptr &solver /*=NULL*/)
            : OperatorExpansion(solver) {}

    public:
        static Ptr instance(const SmtSolver::Ptr &solver /*=NULL*/);

        InstructionSemantics::BaseSemantics::RiscOperatorsPtr riscOperators() const {
            return ops_;
        }
        void riscOperators(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops) {
            ops_ = ops;
        }
        // internal
        virtual SymbolicExpression::Ptr immediateExpansion(const Token &name, const SymbolicExpression::Nodes &operands) override;
        virtual SymbolicExpression::Ptr delayedExpansion(const SymbolicExpression::Ptr&, const SymbolicExpressionParser*) override;
    };


    class TermPlaceholders: public AtomExpansion {
    public:
        typedef Sawyer::SharedPointer<TermPlaceholders> Ptr;

        typedef Sawyer::Container::BiMap<std::string, SymbolicExpression::Ptr> NameToVarMap;

    private:
        NameToVarMap name2var_;

    protected:
        TermPlaceholders() {}

    public:
        static Ptr instance();

        const NameToVarMap& map() const { return name2var_; }

        // internal
        SymbolicExpression::Ptr immediateExpansion(const SymbolicExpressionParser::Token&) override;
    };


    class SymbolicExprCmdlineParser: public Sawyer::CommandLine::ValueParser {
    protected:
        SymbolicExprCmdlineParser() {}
        SymbolicExprCmdlineParser(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver)
            : Sawyer::CommandLine::ValueParser(valueSaver) {}

    public:
        typedef Sawyer::SharedPointer<SymbolicExprCmdlineParser> Ptr;

        static Ptr instance() {
            return Ptr(new SymbolicExprCmdlineParser);
        }

        static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
            return Ptr(new SymbolicExprCmdlineParser(valueSaver));
        }

        static std::string docString();

    private:
        virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
                                                            const Sawyer::CommandLine::Location &loc) override;
    };

    static SymbolicExprCmdlineParser::Ptr symbolicExprParser(SymbolicExpression::Ptr &storage);
    static SymbolicExprCmdlineParser::Ptr symbolicExprParser(std::vector<SymbolicExpression::Ptr> &storage);
    static SymbolicExprCmdlineParser::Ptr symbolicExprParser();

private:
    AtomTable atomTable_;
    OperatorTable operatorTable_;
    SmtSolverPtr solver_;                               // optional solver for simplifications

public:
    static Sawyer::Message::Facility mlog;

public:
    SymbolicExpressionParser();

    explicit SymbolicExpressionParser(const SmtSolverPtr &solver);

    ~SymbolicExpressionParser();

    // used internally to initialize the diagnostics system
    static void initDiagnostics();

    SymbolicExpression::Ptr parse(const std::string&, const std::string &inputName="string");

    SymbolicExpression::Ptr parse(std::istream &input, const std::string &filename,
                                  unsigned lineNumber=1, unsigned columnNumber=0);

    SymbolicExpression::Ptr parse(TokenStream&);

    void appendAtomExpansion(const AtomExpansion::Ptr&);

    void appendOperatorExpansion(const OperatorExpansion::Ptr&);

    const AtomTable& atomTable() const { return atomTable_; }
    AtomTable& atomTable() { return atomTable_; }
    const OperatorTable& operatorTable() const { return operatorTable_; }
    OperatorTable& operatorTable() { return operatorTable_; }
    std::string docString() const;

    void defineRegisters(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&);
    RegisterSubstituter::Ptr defineRegisters(const RegisterDictionaryPtr&);
    SymbolicExpression::Ptr delayedExpansion(const SymbolicExpression::Ptr&) const;

private:
    void init();
};

std::ostream& operator<<(std::ostream&, const SymbolicExpressionParser::SyntaxError&);
std::ostream& operator<<(std::ostream&, const SymbolicExpressionParser::SubstitutionError&);

} // namespace
} // namespace

#endif
#endif