Difficulty grokking the sink/callback idiom and some other issues.

[Bobbias]

I've tried to read through the source to get a better understanding of some of this stuff, but my grasp of c++ templates and constexpr is pretty weak. Hell, my grasp of c++ itself isn't great since I've spent more time coding in c# and other languages.

I've got some simple production rules that work fine:

struct cool_identifier  : lexy::token_production {
    static constexpr auto rule =  dsl::identifier(dsl::ascii::alpha_digit_underscore);
    static constexpr auto value = lexy::as_string<std::string>;
};

struct cool_boolean : lexy::token_production {
    struct true_ : lexy::transparent_production
    {
        static constexpr auto rule  = LEXY_LIT("true");
        static constexpr auto value = lexy::constant(true);
    };
    struct false_ : lexy::transparent_production
    {
        static constexpr auto rule  = LEXY_LIT("false");
        static constexpr auto value = lexy::constant(false);
    };

    static constexpr auto rule  = dsl::p<true_> | dsl::p<false_>;
    static constexpr auto value = lexy::forward<bool>;
};

struct cool_integer : lexy::token_production {
    static constexpr auto rule = [] {
        auto digits = dsl::digits<>.sep(dsl::digit_sep_tick).no_leading_zero();
        return dsl::integer<int>(digits);
    }();

    static constexpr auto value = lexy::forward<int>;
};

struct cool_string : lexy::token_production {
    static constexpr auto rule = []{
        auto code_point = (-dsl::unicode::control);
        return dsl::quoted.limit(dsl::ascii::newline)(code_point);
    }();
    static constexpr auto value = lexy::as_string<std::string>;
};

However when I begin building more complicated objects my understanding begins to break down. A simple example would be parsing a function call's list of parameters. I've created a rule for a function call which, after rewriting some code several times, looks like this:

struct function_call_expression : expression {
    std::string identifier;
    std::vector<literal_expression> temp;  // for testing purposes. literal_expression was not a subclass of expression when I wrote this line
    std::vector<expression_pointer> value;
};

... <snip>

struct cool_function_call {
    static constexpr auto whitespace
        = dsl::ascii::space
        | LEXY_LIT("(*") >> dsl::until(LEXY_LIT("*)"))
        | LEXY_LIT("--") >> (dsl::until(dsl::newline) | dsl::eof);


    struct parameter_pack {
        static constexpr auto rule = []{
            auto item = dsl::p<cool_identifier> | dsl::p<cool_string> | dsl::p<cool_boolean>;
            return dsl::parenthesized.list(item, dsl::trailing_sep(dsl::comma));
        }();
        static constexpr auto value = lexy::as_list<std::vector<ast::literal_expression>>;
    };

    static constexpr auto rule = []{
        auto name_field = (LEXY_MEM(identifier) = dsl::p<cool_identifier>);
        auto expression = (LEXY_MEM(temp) = dsl::p<parameter_pack>);
        return name_field + expression;
    }();
    static constexpr auto value = lexy::as_aggregate<ast::function_call_expression>;
}; 

Note: whitespace is here only because I've been using this as my "top level" parser for testing at the moment. And it's not correct, since it fails to parse when -- is not terminated by a newline.

Initially I had trouble even implementing this rule, since cool_identifier and cool_string both return std::string values, but cool_boolean returns bool. My solution was to combine all 3 literal expression types into a single object which stores the result in std::any. This works, but now I'd have to deal with type checking at runtime, which I'd rather avoid.

I began like the calculator example, defining a base ast::expression type and a pointer to it, as well as several ast types for string, integer, and boolean literals. I then tried to use the expression_production in calculator as a reference. The highest binding power operation in COOL is the . operator, so I tried to implement a simple expression parser that only handled that operation, and some literals. I wound up with something that looked roughly like this:

struct boolean_constant_expression : expression {
    explicit boolean_constant_expression(bool value)
    : value(LEXY_MOV(value))
    {}
};

struct function_call_expression : expression {
    std::string identifier;
    std::vector<expression_pointer> value;
};

... etc. <snip>

struct expression : lexy::expression_production {

    struct expected_operand
    {
        static constexpr auto name = "expected operand";
    };

    static constexpr auto atom = []{
        auto literal = dsl::p<cool_boolean> | dsl::p<cool_string> | dsl::p<cool_integer>;
        auto identifier = dsl::p<cool_identifier>;
        auto paren_expr = dsl::parenthesized(dsl::p<nested_expression>);
        auto var_or_call = identifier >> dsl::if_(paren_expr); // I don't fully get how this line works either
        return paren_expr | literal | var_or_call | dsl::error<expected_operand>;
    }();

    // All binary operations are left-associative, with the exception of assignment, which is right-associative,
    // and the three comparison operations, which do not associate. 

    constexpr auto op_dispatch = dsl::op(dsl::lit_c<'.'>);
    struct dispatch_op : dsl::infix_op_left {
        static constexpr auto op = op_dispatch;
        using operand = dsl::atom;
    };

    using operation = dispatch_op;

    static constexpr auto value = lexy::fold_inplace<std::unique_ptr<ast::function_call_expression>>(
        [] { return std::make_unique<ast::function_call_expression>(); }, // create an empty object
        [](auto& node, std::string name) { node->name = (LEXY_MOV(name)); }, // when passed a string, assign it to the name
        [](auto& node, ast::expression_pointer opr) { node->operands.push_back(LEXY_MOV(opr)); }) >> // when passed an expression pointer of any type, add it to the vector
        lexy::callback(
        lexy::forward<ast::expression_pointer>, // paren_expr
        lexy::new_<ast::integer_expression, ast::expression_pointer>, // literal
        lexy::new_<ast::string_constant_expression, ast::expression_pointer>, // literal
        lexy::new_<ast::boolean_constant_expression, ast::expression_pointer>, // literal
        lexy::new_<ast::identifier_expression, ast::expression_pointer> // identifier
    );
};

However, this expression code just resulted in a series of very large template errors, which go back to either "missing value callback overload for production" or "missing value callback overload for production; only have sink".

I was thinking that I would be able to use the expression parser here to convert the simple types (int, bool, std::string) into ast nodes of a corresponding type by using lexy::new_ to construct the ast node and return the ast node as the value of the expression.

And when it comes to the more complex operations with multiple nested expressions, or optional lists of expressions I feel like I flat out have no idea how to handle them. For example, a let statement looks like:

expr := ID <- expr
...
     | let ID : TYPE [<- expr] ⟦, ID : TYPE [<- expr]⟧* in expr
...

<- being the assignment operator, and ID : TYPE being a variable declaration. With so much of this being optional, I can't quite wrap my head around how you even handle the optional assignment operations and how to structure an ast node to properly capture this structure. I'm sure as I get to grips with the library this will be easier, but as it stands I'm definitely struggling to figure out both how to use the sink/callback idiom for anything beyond simple cases, and how to separate the grammar from the eventual ast nodes to be produced.

[foonathan]

However, this expression code just resulted in a series of very large template errors, which go back to either "missing value callback overload for production" or "missing value callback overload for production; only have sink".

Yes, you can't use fold_inplace here as you're not having a list. You're only having a list if you use dsl::infix_op_list, so don't need a sink. This means the entire fold_inplace(...) >> stuff is unnecessary, as that just specifies a sink to use.

From a cursory glance, it appears you're missing a callback overload that creates a function call (it will generate an identifier followed by an expression_pointer, that is the "// I don't fully get.." line, which matches an identifier, optionally followed by a parenthesized expression (which btw never matches, as you're already parsing an identifier earlier)), and an overload for op_dispatch which takes an expression_pointer, lexy::op<op_dispatch> and another expression pointer.

If you're having trouble with errors, I recommend that you split everything into separate production as far as possible. For example, a separate production for literals and names, etc. Depending on your compiler, the error message also lists you the production with the missing overload and the types it had (those are passed to _detail::error and e.g. clang gives you the type names).

<- being the assignment operator, and ID : TYPE being a variable declaration. With so much of this being optional, I can't quite wrap my head around how you even handle the optional assignment operations and how to structure an ast node to properly capture this structure.

It's the same principle: you create further derived classes storing the operands, and an overload that constructs them. The trick is that lexy gives you the operators as well.

So for example: ID <- expr would result in a call to the callback with (identifier, op<"<-">, expr).

[foonathan]

Looking at the code with fresh eyes I'm guessing that the disambiguation happens in the callback selection? I guess name_or_call in the calculator either produces a single name, or a name followed by a bracketed expression, and when the callback list tries to match parameters to constructors that's how it decides?

Yes, exactly. The callback is an overload set, depending on the types it selects different constructors. The only thing that accepts a string and an expression pointer is the constructor expr_call, so that's what's being invoked.

[Bobbias]

Ok, good to know I got that right. Thanks for the clarification.

One more question: in the case of dsl::op<void>(), if I understand correctly, it would drop the lexy::op from the constructor call entirely, resulting in just calling with (operand1, operand2) rather than (operand1, op, operand2)?

[foonathan]

Yes, exactly.

[Bobbias]

Might as well not make another top level post for this.

I'm still having a bit of trouble here. I've lifted the nested_expression parser from the calculator example for use in my project, and I'm trying to use it to build a super simple if expression:

// An expression that is nested inside another expression.
struct nested_expression : lexy::transparent_production
{
    // We change the whitespace rule to allow newlines:
    // as it's nested, the REPL can properly handle continuation lines.
    static constexpr auto whitespace = dsl::ascii::space;
    // The rule itself just recurses back to expression, but with the adjusted whitespace now.
    static constexpr auto rule = dsl::recurse<struct expression>;

    static constexpr auto value = lexy::forward<ast::expression_pointer>;
};

// trying to make this really simple, and add some catch-all callbacks for for debugging purposes
struct expression : lexy::expression_production {
    static constexpr auto atom = dsl::p<cool_boolean> | dsl::p<cool_string> | dsl::p<cool_integer>;
    using operation = dsl::atom;
    static constexpr auto value = lexy::callback(
        lexy::new_<ast::bool_expression, ast::expression_pointer>,
        lexy::new_<ast::integer_expression, ast::expression_pointer>,
        lexy::new_<ast::string_expression, ast::expression_pointer>,
        [](){ return std::make_unique<ast::expression_pointer>(nullptr);},
        [](auto val){ printf("val: {}", val); return std::make_unique<ast::expression_pointer>(nullptr);},
        [](auto val, auto val2){ printf("val: {} val2: {}", val, val2); return std::make_unique<ast::expression_pointer>(nullptr);},
        [](auto val, auto val2, auto val3){ printf("val: {} val2: {}, val3: {}", val, val2, val3); return std::make_unique<ast::expression_pointer>(nullptr);}
    );
};

// struct ast::if_expression {
//     expression_pointer conditional;
//     expression_pointer true_branch;
//     std::optional<expression_pointer> false_branch;
// };
struct cool_if_expression {
    static constexpr auto whitespace
        = dsl::ascii::space
        | LEXY_LIT("(*") >> dsl::until(LEXY_LIT("*)"))
        | LEXY_LIT("--") >> dsl::until(dsl::newline).or_eof();

    static constexpr auto rule = []{
        auto condition_expr = kw_if >> (LEXY_MEM(conditional) = dsl::p<nested_expression>);
        auto then_expr = kw_then >> (LEXY_MEM(true_branch) = dsl::p<nested_expression>);
        auto else_expr = dsl::opt(kw_else >> (LEXY_MEM(false_branch) = dsl::p<nested_expression>));
        return condition_expr + then_expr + else_expr;
    }();
    static constexpr auto value = lexy::as_aggregate<ast::if_expression>;
};

This is a small excerpt of the error:

error: no match for call to '(const lexy::_as_aggregate<ast::if_expression>) (std::remove_reference_t<ast::if_expression&&>, lexy::nullopt)'

If I understand this correctly I'm getting a nullopt result somewhere I didn't anticipate it (either condition_expr or else_expr in cool_if_expression?)

My intention was to parse the if expression such that the keywords are 'thrown out' once I've identified that we are parsing an if expression, and the nested expressions following the if/then/else keywords are parsed, and the values inserted into the ast object.

I'm trying to avoid the need to produce unnecessary values while parsing tokens which only matter during parsing itself. So in the case of an if statement, while the rule needs to parse the keywords, the resulting ast node shouldn't need anything related to the keywords themselves.

[foonathan]

If I understand this correctly I'm getting a nullopt result somewhere I didn't anticipate it

Yes, dsl::opt produces a nullopt if the branch didn't match. Here you don't need that, so you can just use dsl::if_ instead.