// Copyright (c) Herb Sutter

// SPDX-License-Identifier: CC-BY-NC-ND-4.0

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

// THE SOFTWARE.

//===========================================================================

// Parser

//===========================================================================

#ifndef __CPP2_PARSE

#define __CPP2_PARSE

#include "lex.h"

#include <memory>

#include <variant>

#include <iostream>

namespace cpp2 {

auto violates_lifetime_safety = false;

//-----------------------------------------------------------------------

// Operator categorization

//

//G prefix-operator:

//G one of not

//G

auto is_prefix_operator(lexeme l) -> bool

{

switch (l) {

break;case lexeme::Not:

case lexeme::Minus:

case lexeme::Plus:

return true;

break;default:

return false;

}

}

//G postfix-operator:

//G one of ++ -- * & ~ $

//G

auto is_postfix_operator(lexeme l) -> bool

{

switch (l) {

break;case lexeme::PlusPlus:

case lexeme::MinusMinus:

case lexeme::Multiply:

case lexeme::Ampersand:

case lexeme::Tilde:

case lexeme::Dollar:

return true;

break;default:

return false;

}

}

//G assignment-operator:

//G one of = *= /= %= += -= >>= <<=

//G

auto is_assignment_operator(lexeme l) -> bool

{

switch (l) {

break;case lexeme::Assignment:

case lexeme::MultiplyEq:

case lexeme::SlashEq:

case lexeme::ModuloEq:

case lexeme::PlusEq:

case lexeme::MinusEq:

case lexeme::RightShiftEq:

case lexeme::LeftShiftEq:

case lexeme::AmpersandEq:

case lexeme::CaretEq:

case lexeme::PipeEq:

return true;

break;default:

return false;

}

}

//-----------------------------------------------------------------------

//

// Parse tree node types

//

//-----------------------------------------------------------------------

//

//-----------------------------------------------------------------------

// try_emit

//

// Helper to visit whatever is in a variant where each

// alternative is a smart pointer

//

template <int I>

auto try_visit(auto& variant, auto& visitor, int depth) -> void {

if (variant.index() == I) {

auto const& s = std::get<I>(variant);

assert (s);

s->visit(visitor, depth+1);

}

}

struct expression_list_node;

struct id_expression_node;

struct declaration_node;

struct inspect_expression_node;

struct primary_expression_node

{

enum active { empty=0, identifier, expression_list, id_expression, declaration, inspect };

std::variant<

std::monostate,

token const*,

std::unique_ptr<expression_list_node>,

std::unique_ptr<id_expression_node>,

std::unique_ptr<declaration_node>,

std::unique_ptr<inspect_expression_node>

> expr;

auto get_token() -> token const*;

auto position() const -> source_position;

auto visit(auto& v, int depth) -> void;

};

struct postfix_expression_node;

struct prefix_expression_node

{

std::vector<token const*> ops;

std::unique_ptr<postfix_expression_node> expr;

auto get_postfix_expression_node() const -> postfix_expression_node const* {

assert(expr);

return expr.get();

}

auto position() const -> source_position;

auto visit(auto& v, int depth) -> void;

};

template<

String Name,

typename Term

>

struct binary_expression_node

{

std::unique_ptr<Term> expr;

struct term

{

token const* op;

std::unique_ptr<Term> expr;

};

std::vector<term> terms;

// Get left-hand postfix-expression

auto get_postfix_expression_node() const -> postfix_expression_node const* {

assert(expr);

return expr->get_postfix_expression_node();

}

// Get first right-hand postfix-expression, if there is one

auto get_second_postfix_expression_node() const -> postfix_expression_node const* {

if (!terms.empty()) {

assert(terms.front().expr);

return terms.front().expr->get_postfix_expression_node();

}

// else

return {};

}

auto position() const -> source_position

{

assert (expr);

return expr->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert (expr);

expr->visit(v, depth+1);

for (auto const& x : terms) {

assert (x.op);

v.start(*x.op, depth+1);

assert (x.expr);

x.expr->visit(v, depth+1);

}

v.end(*this, depth);

}

};

using is_as_expression_node = binary_expression_node< "is-as" , prefix_expression_node >;

using multiplicative_expression_node = binary_expression_node< "multiplicative" , is_as_expression_node >;

using additive_expression_node = binary_expression_node< "additive" , multiplicative_expression_node >;

using shift_expression_node = binary_expression_node< "shift" , additive_expression_node >;

using compare_expression_node = binary_expression_node< "compare" , shift_expression_node >;

using relational_expression_node = binary_expression_node< "relational" , compare_expression_node >;

using equality_expression_node = binary_expression_node< "equality" , relational_expression_node >;

using bit_and_expression_node = binary_expression_node< "bit-and" , equality_expression_node >;

using bit_xor_expression_node = binary_expression_node< "bit-xor" , bit_and_expression_node >;

using bit_or_expression_node = binary_expression_node< "bit-or" , bit_xor_expression_node >;

using logical_and_expression_node = binary_expression_node< "logical-and" , bit_or_expression_node >;

using logical_or_expression_node = binary_expression_node< "logical-or" , logical_and_expression_node >;

using assignment_expression_node = binary_expression_node< "assignment" , logical_or_expression_node >;

struct expression_node

{

std::unique_ptr<assignment_expression_node> expr;

auto position() const -> source_position

{

assert (expr);

return expr->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert (expr);

expr->visit(v, depth+1);

v.end(*this, depth);

}

};

enum class passing_style { in=0, copy, inout, out, move, forward };

auto to_string_view(passing_style pass) -> std::string_view {

switch (pass) {

break;case passing_style::in : return "in";

break;case passing_style::copy : return "copy";

break;case passing_style::inout : return "inout";

break;case passing_style::out : return "out";

break;case passing_style::move : return "move";

break;case passing_style::forward: return "forward";

break;default: return "INVALID passing_tyle";

}

}

struct expression_list_node

{

source_position open_paren = {};

source_position close_paren = {};

bool inside_initializer = false;

struct term {

passing_style pass = {};

std::unique_ptr<expression_node> expr;

};

std::vector< term > expressions;

auto position() const -> source_position

{

// Make sure this got set

assert (open_paren != source_position());

return open_paren;

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

for (auto const& x : expressions) {

assert(x.expr);

x.expr->visit(v, depth+1);

}

v.end(*this, depth);

}

};

struct expression_statement_node

{

std::unique_ptr<expression_node> expr;

bool has_semicolon = false;

auto position() const -> source_position

{

assert (expr);

return expr->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert (expr);

expr->visit(v, depth+1);

v.end(*this, depth);

}

};

struct capture {

postfix_expression_node* capture_expr;

std::string str;

};

using capture_group = std::vector<capture>;

struct postfix_expression_node

{

std::unique_ptr<primary_expression_node> expr;

struct term

{

token const* op;

// This is used if *op is . - can be null

std::unique_ptr<id_expression_node> id_expr;

// These are used if *op is [ or ( - can be null

std::unique_ptr<expression_list_node> expr_list;

token const* op_close;

};

std::vector<term> ops;

capture_group* cap_grp = {};

auto position() const -> source_position

{

assert (expr);

return expr->position();

}

auto visit(auto& v, int depth) -> void;

};

auto prefix_expression_node::position() const -> source_position

{

if (std::ssize(ops) > 0) {

return ops.front()->position();

}

assert (expr);

return expr->position();

}

auto prefix_expression_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

for (auto const& x : ops) {

assert (x);

v.start(*x, depth+1);

}

assert (expr);

expr->visit(v, depth+1);

v.end(*this, depth);

}

struct unqualified_id_node

{

token const* const_qualifier = {}; // optional

token const* identifier = {}; // required

enum active { empty=0, expression, id_expression };

// These are used only if it's a template-id

source_position open_angle = {};

source_position close_angle = {};

struct term {

source_position comma;

std::variant<

std::monostate,

std::unique_ptr<expression_node>,

std::unique_ptr<id_expression_node>

> arg;

};

std::vector<term> template_args;

auto get_token() -> token const* {

if (template_args.empty()) {

assert (identifier);

return identifier;

}

// else

return {};

}

auto position() const -> source_position

{

assert (identifier);

return identifier->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

if (const_qualifier) {

v.start(*const_qualifier, depth+1);

}

assert (identifier);

v.start(*identifier, depth+1);

if (!template_args.empty()) {

assert(open_angle != source_position{});

assert(close_angle != source_position{});

assert(template_args.front().comma == source_position{});

for (auto& a : template_args) {

try_visit< expression>(a.arg, v, depth+1);

try_visit<id_expression>(a.arg, v, depth+1);

}

}

v.end(*this, depth);

}

};

struct qualified_id_node

{

struct term {

token const* scope_op;

std::unique_ptr<unqualified_id_node> id = nullptr;

term( token const* o ) : scope_op{o} { }

};

std::vector<term> ids;

auto position() const -> source_position

{

assert (!ids.empty());

if (ids.front().scope_op) {

return ids.front().scope_op->position();

}

else {

assert (ids.front().id);

return ids.front().id->position();

}

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

for (auto const& x : ids) {

if (x.scope_op) {

x.scope_op->visit(v, depth+1);

}

assert(x.id);

x.id->visit(v, depth+1);

}

v.end(*this, depth);

}

};

struct id_expression_node

{

source_position pos;

enum active { empty=0, qualified, unqualified };

std::variant<

std::monostate,

std::unique_ptr<qualified_id_node>,

std::unique_ptr<unqualified_id_node>

> id;

auto get_token() -> token const* {

if (id.index() == unqualified) {

return std::get<unqualified>(id)->get_token();

}

// else

return {};

}

auto position() const -> source_position

{

return pos;

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

try_visit<qualified >(id, v, depth);

try_visit<unqualified>(id, v, depth);

v.end(*this, depth);

}

};

auto postfix_expression_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert (expr);

expr->visit(v, depth+1);

for (auto const& x : ops) {

assert (x.op);

v.start(*x.op, depth+1);

if (x.id_expr) {

x.id_expr->visit(v, depth+1);

}

if (x.expr_list) {

x.expr_list->visit(v, depth+1);

}

}

v.end(*this, depth);

}

struct statement_node;

struct compound_statement_node

{

source_position open_brace;

source_position close_brace;

std::vector<std::unique_ptr<statement_node>> statements;

compound_statement_node(source_position o = source_position{}) : open_brace{o} { }

auto position() const -> source_position

{

return open_brace;

}

auto visit(auto& v, int depth) -> void;

};

struct selection_statement_node

{

bool is_constexpr = false;

token const* identifier;

source_position else_pos;

std::unique_ptr<expression_node> expression;

std::unique_ptr<compound_statement_node> true_branch;

std::unique_ptr<compound_statement_node> false_branch;

bool has_source_false_branch = false;

auto position() const -> source_position

{

assert (identifier);

return identifier->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert (identifier);

v.start(*identifier, depth+1);

assert (expression);

expression->visit(v, depth+1);

assert (true_branch);

true_branch->visit(v, depth+1);

if (false_branch) {

false_branch->visit(v, depth+1);

}

v.end(*this, depth);

}

};

struct parameter_declaration_node;

struct iteration_statement_node

{

token const* identifier;

std::unique_ptr<assignment_expression_node> next_expression; // if used, else null

std::unique_ptr<logical_or_expression_node> condition; // used for "do" and "while", else null

std::unique_ptr<compound_statement_node> statement; // used for "do" and "while", else null

std::unique_ptr<expression_node> range; // used for "for", else null

std::unique_ptr<declaration_node> body; // used for "for", else null

auto get_for_parameter() const -> parameter_declaration_node const*;

auto position() const -> source_position

{

assert(identifier);

return identifier->position();

}

auto visit(auto& v, int depth) -> void;

};

struct return_statement_node

{

token const* identifier;

std::unique_ptr<expression_node> expression;

auto position() const -> source_position

{

assert(identifier);

return identifier->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

if (expression) {

expression->visit(v, depth+1);

}

v.end(*this, depth);

}

};

struct alternative_node

{

std::unique_ptr<unqualified_id_node> name;

token const* is_as_keyword;

std::unique_ptr<id_expression_node> id_expression;

source_position equal_sign;

std::unique_ptr<statement_node> statement;

auto position() const -> source_position

{

assert(is_as_keyword);

return is_as_keyword->position();

}

auto visit(auto& v, int depth) -> void;

};

struct inspect_expression_node

{

bool is_constexpr = false;

token const* identifier;

std::unique_ptr<expression_node> expression;

std::unique_ptr<id_expression_node> result_type;

source_position open_brace;

source_position close_brace;

std::vector<std::unique_ptr<alternative_node>> alternatives;

auto position() const -> source_position

{

assert(identifier);

return identifier->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert (identifier);

v.start(*identifier, depth+1);

assert (expression);

expression->visit(v, depth+1);

if (result_type) {

result_type->visit(v, depth+1);

}

for (auto&& alt : alternatives) {

alt->visit(v, depth+1);

}

v.end(*this, depth);

}

};

struct contract_node

{

source_position open_bracket;

token const* kind = {};

std::unique_ptr<id_expression_node> group;

std::unique_ptr<logical_or_expression_node> condition;

token const* message = {};

capture_group captures;

contract_node( source_position pos ) : open_bracket{pos} { }

auto position() const -> source_position

{

return open_bracket;

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert(kind);

kind->visit(v, depth+1);

if (group) {

group->visit(v, depth+1);

}

assert(condition);

condition->visit(v, depth+1);

v.end(*this, depth);

}

};

struct parameter_declaration_list_node;

struct statement_node

{

token const* let;

std::unique_ptr<parameter_declaration_list_node> let_params;

enum active { expression=0, compound, selection, declaration, return_, iteration, contract, inspect };

std::variant<

std::unique_ptr<expression_statement_node>,

std::unique_ptr<compound_statement_node>,

std::unique_ptr<selection_statement_node>,

std::unique_ptr<declaration_node>,

std::unique_ptr<return_statement_node>,

std::unique_ptr<iteration_statement_node>,

std::unique_ptr<contract_node>,

std::unique_ptr<inspect_expression_node>

> statement;

auto position() const -> source_position;

auto visit(auto& v, int depth) -> void;

};

auto alternative_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

if (name) {

v.start(*name, depth+1);

}

assert (is_as_keyword);

v.start(*is_as_keyword, depth+1);

assert (id_expression);

id_expression->visit(v, depth+1);

assert (statement);

statement->visit(v, depth+1);

v.end(*this, depth);

}

auto compound_statement_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

for (auto const& x : statements) {

assert(x);

x->visit(v, depth+1);

}

v.end(*this, depth);

}

struct parameter_declaration_node

{

source_position pos;

passing_style pass = passing_style::in;

enum class modifier { none=0, implicit, virtual_, override_, final_ };

modifier mod = modifier::none;

std::unique_ptr<declaration_node> declaration;

auto position() const -> source_position;

auto visit(auto& v, int depth) -> void;

};

struct parameter_declaration_list_node

{

source_position pos_open_paren;

source_position pos_close_paren;

std::vector<std::unique_ptr<parameter_declaration_node>> parameters;

auto position() const -> source_position

{

return pos_open_paren;

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

for (auto const& x : parameters) {

assert(x);

x->visit(v, depth+1);

}

v.end(*this, depth);

}

};

auto statement_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

if (let) {

let->visit(v, depth+1);

assert(let_params);

let_params->visit(v, depth+1);

}

try_visit<expression >(statement, v, depth);

try_visit<compound >(statement, v, depth);

try_visit<selection >(statement, v, depth);

try_visit<declaration>(statement, v, depth);

try_visit<return_ >(statement, v, depth);

try_visit<iteration >(statement, v, depth);

try_visit<contract >(statement, v, depth);

try_visit<inspect >(statement, v, depth);

v.end(*this, depth);

}

struct function_returns_tag { };

struct function_type_node

{

std::unique_ptr<parameter_declaration_list_node> parameters;

bool throws = false;

enum active { empty = 0, id, list };

std::variant<

std::monostate,

std::unique_ptr<id_expression_node>,

std::unique_ptr<parameter_declaration_list_node>

> returns;

std::vector<std::unique_ptr<contract_node>> contracts;

auto position() const -> source_position

{

assert (parameters);

return parameters->position();

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

assert(parameters);

parameters->visit(v, depth+1);

if (returns.index() == id) {

auto& r = std::get<id>(returns);

assert(r);

r->visit(v, depth+1);

}

else if (returns.index() == list) {

auto& r = std::get<list>(returns);

assert(r);

// Inform the visitor that this is a returns list

v.start(function_returns_tag{}, depth);

r->visit(v, depth+1);

v.end(function_returns_tag{}, depth);

}

v.end(*this, depth);

}

};

struct declaration_node

{

source_position pos;

std::unique_ptr<unqualified_id_node> identifier;

token const* pointer_declarator = nullptr;

enum active { function, object };

std::variant<

std::unique_ptr<function_type_node>,

std::unique_ptr<id_expression_node>

> type;

source_position equal_sign = {};

source_position decl_end = {};

std::unique_ptr<statement_node> initializer;

capture_group captures;

// Shorthand for common query

//

auto is(active a) const

{

return type.index() == a;

}

auto position() const -> source_position

{

if (identifier) {

return identifier->position();

}

return pos;

}

auto visit(auto& v, int depth) -> void

{

v.start(*this, depth);

if (identifier) {

identifier->visit(v, depth+1);

}

try_visit<function>(type, v, depth+1);

try_visit<object >(type, v, depth+1);

if (initializer) {

initializer->visit(v, depth+1);

}

v.end(*this, depth);

}

};

auto primary_expression_node::get_token() -> token const*

{

if (expr.index() == identifier) {

return std::get<identifier>(expr);

}

else if (expr.index() == id_expression) {

return std::get<id_expression>(expr)->get_token();

}

// else (because we're deliberately ignoring the other

// options which are more than a single token)

return {};

}

auto primary_expression_node::position() const -> source_position

{

switch (expr.index())

{

break;case empty:

return { 0, 0 };

break;case identifier: {

auto const& s = std::get<identifier>(expr);

assert (s);

return s->position();

}

break;case expression_list: {

auto const& s = std::get<expression_list>(expr);

assert (s);

return s->position();

}

break;case id_expression: {

auto const& s = std::get<id_expression>(expr);

assert (s);

return s->position();

}

break;case declaration: {

auto const& s = std::get<declaration>(expr);

assert (s);

return s->position();

}

break;case inspect: {

auto const& i = std::get<inspect>(expr);

assert (i);

return i->position();

}

break;default:

assert (!"illegal primary_expression_node state");

return { 0, 0 };

}

}

auto primary_expression_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

try_visit<identifier >(expr, v, depth);

try_visit<expression_list>(expr, v, depth);

try_visit<id_expression >(expr, v, depth);

try_visit<declaration >(expr, v, depth);

try_visit<inspect >(expr, v, depth);

v.end(*this, depth);

}

auto iteration_statement_node::get_for_parameter() const -> parameter_declaration_node const* {

assert(*identifier == "for");

auto func = std::get_if<declaration_node::function>(&body->type);

assert(func && *func && std::ssize((**func).parameters->parameters) == 1);

return (**func).parameters->parameters[0].get();

}

auto iteration_statement_node::visit(auto& v, int depth) -> void

{

v.start(*this, depth);

if (statement) {

statement->visit(v, depth+1);

}

if (next_expression) {

next_expression->visit(v, depth+1);

}

if (condition) {

assert(!range && !body);

condition->visit(v, depth+1);

}

else {

assert(range && body);

range->visit(v, depth+1);

body->visit(v, depth+1);

}

v.end(*this, depth);

}

auto statement_node::position() const -> source_position

{

switch (statement.index())

{

break;case expression: {

auto const& s = std::get<expression>(statement);

assert (s);

return s->position();