path: root/host/lib/rfnoc/nocscript/parser.cpp

//
// Copyright 2015 Ettus Research LLC
//
// SPDX-License-Identifier: GPL-3.0
//

#include "parser.hpp"
#include <uhd/utils/cast.hpp>
#include <boost/spirit/include/lex_lexertl.hpp>
#include <boost/format.hpp>
#include <boost/bind.hpp>
#include <boost/assign.hpp>
#include <boost/make_shared.hpp>
#include <sstream>
#include <stack>

using namespace uhd::rfnoc::nocscript;
namespace lex = boost::spirit::lex;

class parser_impl : public parser
{
  public:
    /******************************************************************
     * Structors TODO make them protected
     *****************************************************************/
    parser_impl(
        function_table::sptr ftable,
        expression_variable::type_getter_type var_type_getter,
        expression_variable::value_getter_type var_value_getter
    ) : _ftable(ftable)
      , _var_type_getter(var_type_getter)
      , _var_value_getter(var_value_getter)
    {
        // nop
    }

    ~parser_impl() {};


    /******************************************************************
     * Parsing
     *****************************************************************/
    //! List of parser tokens
    enum token_ids
    {
        ID_WHITESPACE = lex::min_token_id + 42,
        ID_KEYWORD,
        ID_ARG_SEP,
        ID_PARENS_OPEN,
        ID_PARENS_CLOSE,
        ID_VARIABLE,
        ID_LITERAL_DOUBLE,
        ID_LITERAL_INT,
        ID_LITERAL_HEX,
        ID_LITERAL_STR,
        ID_LITERAL_VECTOR_INT
    };

    //! The Lexer object used for NocScript
    template <typename Lexer>
    struct ns_lexer : lex::lexer<Lexer>
    {
        ns_lexer()
        {
            this->self.add
                ("\\s+",                 ID_WHITESPACE)
                (",",                    ID_ARG_SEP)
                ("[A-Z][A-Z0-9_]*",      ID_KEYWORD)
                ("\\(",                  ID_PARENS_OPEN)
                ("\\)",                  ID_PARENS_CLOSE)
                ("\\$[a-z][a-z0-9_]*",   ID_VARIABLE)
                ("-?\\d+\\.\\d+",        ID_LITERAL_DOUBLE)
                ("-?\\d+",               ID_LITERAL_INT)
                ("0x[0-9A-F]+",          ID_LITERAL_HEX)
                ("\\\"[^\\\"]*\\\"",     ID_LITERAL_STR)
                ("'[^']*'",              ID_LITERAL_STR) // both work
                ("\\[[0-9]\\]",          ID_LITERAL_VECTOR_INT)
            ;
        }
    };

  private:
    struct grammar_props
    {
        function_table::sptr ftable;
        expression_variable::type_getter_type var_type_getter;
        expression_variable::value_getter_type var_value_getter;

        //! Store the last keyword
        std::string function_name;
        std::string error;
        std::stack<expression_container::sptr> expr_stack;

        grammar_props(
            function_table::sptr ftable_,
            expression_variable::type_getter_type var_type_getter_,
            expression_variable::value_getter_type var_value_getter_
        ) : ftable(ftable_), var_type_getter(var_type_getter_), var_value_getter(var_value_getter_),
            function_name("")
        {
            UHD_ASSERT_THROW(expr_stack.empty());
            // Push an empty container to the stack to hold the result
            expr_stack.push(expression_container::make());
        }

        expression::sptr get_result()
        {
            UHD_ASSERT_THROW(expr_stack.size() == 1);
            return expr_stack.top();
        }
    };

    //! This isn't strictly a grammar, as it also includes semantic
    //  actions etc. I'm not going to spend ages thinking of a better
    //  name at this point.
    struct grammar
    {
        // Implementation detail specific to boost::bind (see Boost::Spirit
        // examples)
        typedef bool result_type;

        static const int VALID_COMMA        = 0x1;
        static const int VALID_PARENS_OPEN  = 0x2;
        static const int VALID_PARENS_CLOSE = 0x4;
        static const int VALID_EXPRESSION   = 0x8 + 0x02;
        static const int VALID_OPERATOR      = 0x10;

        // !This function operator gets called for each of the matched tokens.
        template <typename Token>
        bool operator()(Token const& t, grammar_props &P, int &next_valid_state) const
        {
            //! This is totally not how Boost::Spirit is meant to be used,
            // as there's token types etc. But for now let's just convert
            // every token to a string, and then handle it as such.
            std::stringstream sstr;
            sstr << t.value();
            std::string val = sstr.str();
            //std::cout << "VAL: " << val << std::endl;
            //std::cout << "Next valid states:\n"
                    //<< boost::format("VALID_COMMA        [%s]\n") % ((next_valid_state & 0x1) ? "x" : " ")
                    //<< boost::format("VALID_PARENS_OPEN  [%s]\n") % ((next_valid_state & 0x2) ? "x" : " ")
                    //<< boost::format("VALID_PARENS_CLOSE [%s]\n") % ((next_valid_state & 0x4) ? "x" : " ")
                    //<< boost::format("VALID_EXPRESSION   [%s]\n") % ((next_valid_state & (0x8 + 0x02)) ? "x" : " ")
                    //<< boost::format("VALID_OPERATOR      [%s]\n") % ((next_valid_state & 0x10) ? "x" : " ")
                    //<< std::endl;

            switch (t.id()) {

            case ID_WHITESPACE:
                // Ignore
                break;

            case ID_KEYWORD:
                // Ambiguous, could be an operator (AND, OR) or a function name (ADD, MULT...).
                // So first, check which it is:
                if (val == "AND" or val == "OR") {
                    if (not (next_valid_state & VALID_OPERATOR)) {
                        P.error = str(boost::format("Unexpected operator: %s") % val);
                        return false;
                    }
                    next_valid_state = VALID_EXPRESSION;
                    try {
                        if (val == "AND") {
                            P.expr_stack.top()->set_combiner_safe(expression_container::COMBINE_AND);
                        } else if (val == "OR") {
                            P.expr_stack.top()->set_combiner_safe(expression_container::COMBINE_OR);
                        }
                    } catch (const uhd::syntax_error &e) {
                        P.error = str(boost::format("Operator %s is mixing operator types within this container.") % val);
                    }
                    // Right now, we can't have multiple operator types within a container.
                    // We might be able to change that, if there's enough demand. Either
                    // we keep track of multiple operators, or we open a new container.
                    // In the latter case, we'd need a way of keeping track of those containers,
                    // so it's a bit tricky.
                    break;
                }
                // If it's not a keyword, it has to be a function, so check the
                // function table:
                if (not (next_valid_state & VALID_EXPRESSION)) {
                    P.error = str(boost::format("Unexpected expression: %s") % val);
                    return false;
                }
                if (not P.ftable->function_exists(val)) {
                    P.error = str(boost::format("Unknown function: %s") % val);
                    return false;
                }
                P.function_name = val;
                next_valid_state = VALID_PARENS_OPEN;
                break;

            // Every () creates a new container, either a raw container or
            // a function.
            case ID_PARENS_OPEN:
                if (not (next_valid_state & VALID_PARENS_OPEN)) {
                    P.error = str(boost::format("Unexpected parentheses."));
                    return false;
                }
                if (not P.function_name.empty()) {
                    // We've already checked the function name exists
                    P.expr_stack.push(expression_function::make(P.function_name, P.ftable));
                    P.function_name.clear();
                } else {
                    P.expr_stack.push(expression_container::make());
                }
                // Push another empty container to hold the first element/argument
                // in this container:
                P.expr_stack.push(expression_container::make());
                next_valid_state = VALID_EXPRESSION | VALID_PARENS_CLOSE;
                break;

            case ID_PARENS_CLOSE:
            {
                if (not (next_valid_state & VALID_PARENS_CLOSE)) {
                    P.error = str(boost::format("Unexpected parentheses."));
                    return false;
                }
                if (P.expr_stack.size() < 2) {
                    P.error = str(boost::format("Unbalanced closing parentheses."));
                    return false;
                }
                // First pop the last expression inside the parentheses,
                // if it's not empty, add it to the top container (this also avoids
                // adding arguments to functions if none were provided):
                expression_container::sptr c = P.expr_stack.top();
                P.expr_stack.pop();
                if (not c->empty()) {
                    P.expr_stack.top()->add(c);
                }
                // At the end of (), either a function or container is complete,
                // so pop that and add it to its top container:
                expression_container::sptr c2 = P.expr_stack.top();
                P.expr_stack.pop();
                P.expr_stack.top()->add(c2);
                next_valid_state = VALID_OPERATOR | VALID_COMMA | VALID_PARENS_CLOSE;
            }
                break;

            case ID_ARG_SEP:
            {
                if (not (next_valid_state & VALID_COMMA)) {
                    P.error = str(boost::format("Unexpected comma."));
                    return false;
                }
                next_valid_state = VALID_EXPRESSION;
                // If stack size is 1, we're on the base container, which means we
                // simply string stuff.
                if (P.expr_stack.size() == 1) {
                    break;
                }
                // Otherwise, a ',' always means we add the previous expression to
                // the current container:
                expression_container::sptr c = P.expr_stack.top();
                P.expr_stack.pop();
                P.expr_stack.top()->add(c);
                // It also means another expression is following, so create another
                // empty container for that:
                P.expr_stack.push(expression_container::make());
            }
                break;

            // All the atomic expressions just get added to the current container:

            case ID_VARIABLE:
            {
                if (not (next_valid_state & VALID_EXPRESSION)) {
                    P.error = str(boost::format("Unexpected expression."));
                    return false;
                }
                expression_variable::sptr v = expression_variable::make(val, P.var_type_getter, P.var_value_getter);
                P.expr_stack.top()->add(v);
                next_valid_state = VALID_OPERATOR | VALID_COMMA | VALID_PARENS_CLOSE;
            }
                break;

            default:
            // If we get here, we assume it's a literal expression
            {
                if (not (next_valid_state & VALID_EXPRESSION)) {
                    P.error = str(boost::format("Unexpected expression."));
                    return false;
                }
                expression::type_t token_type;
                switch (t.id()) { // A map lookup would be more elegant, but we'd need a nicer C++ for that
                    case ID_LITERAL_DOUBLE: token_type = expression::TYPE_DOUBLE; break;
                    case ID_LITERAL_INT: token_type = expression::TYPE_INT; break;
                    case ID_LITERAL_HEX: token_type = expression::TYPE_INT; break;
                    case ID_LITERAL_STR: token_type = expression::TYPE_STRING; break;
                    case ID_LITERAL_VECTOR_INT: token_type = expression::TYPE_INT_VECTOR; break;
                    default: UHD_THROW_INVALID_CODE_PATH();
                }
                P.expr_stack.top()->add(boost::make_shared<expression_literal>(val, token_type));
                next_valid_state = VALID_OPERATOR | VALID_COMMA | VALID_PARENS_CLOSE;
                break;
            }

            } // end switch
            return true;
        }
    };

  public:
    expression::sptr create_expr_tree(const std::string &code)
    {
        // Create empty stack and keyword states
        grammar_props P(_ftable, _var_type_getter, _var_value_getter);
        int next_valid_state = grammar::VALID_EXPRESSION;

        // Create a lexer instance
        ns_lexer<lex::lexertl::lexer<> > lexer_functor;

        // Tokenize the string
        char const* first = code.c_str();
        char const* last = &first[code.size()];
        bool r = lex::tokenize(
            first, last, // Iterators
            lexer_functor, // Lexer
            boost::bind(grammar(), _1, boost::ref(P), boost::ref(next_valid_state)) // Function object
        );

        // Check the parsing worked:
        if (not r or P.expr_stack.size() != 1) {
            std::string rest(first, last);
            throw uhd::syntax_error(str(
                    boost::format("Parsing stopped at: %s\nError message: %s")
                    % rest % P.error
            ));
        }

        // Clear stack and return result
        return P.get_result();
    }

  private:

    function_table::sptr _ftable;
    expression_variable::type_getter_type _var_type_getter;
    expression_variable::value_getter_type _var_value_getter;
};

parser::sptr parser::make(
    function_table::sptr ftable,
    expression_variable::type_getter_type var_type_getter,
    expression_variable::value_getter_type var_value_getter
) {
    return sptr(new parser_impl(
        ftable,
        var_type_getter,
        var_value_getter
    ));
}