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