// 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_H

#define CPP2_PARSE_H

#include "lex.h"

namespace cpp2 {

auto violates_lifetime_safety = false;

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

// Operator categorization

//

//G prefix-operator:

//G one of '!' '-' '+'

//GT parameter-direction

//G

auto is_prefix_operator(token const& tok)

-> bool

{

//if (to_passing_style(tok) != passing_style::invalid) {

// return true;

//}

switch (tok.type()) {

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:

case lexeme::Ellipsis:

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_visit

//

// 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 literal_node;

struct template_argument;

struct primary_expression_node

{

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

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>,

std::unique_ptr<literal_node>

> expr;

// Cache to work around <https://github.com/llvm/llvm-project/issues/73336>.

bool expression_list_is_fold_expression = false;

// API

//

auto is_fold_expression() const

-> bool;

auto is_identifier() const

-> bool;

auto is_id_expression() const

-> bool;

auto is_unqualified_id() const

-> bool;

auto is_expression_list() const

-> bool;

auto get_expression_list() const

-> expression_list_node const*;

auto is_literal() const

-> bool;

auto get_literal() const

-> literal_node const*;

auto template_arguments() const -> std::vector<template_argument> const&;

auto get_token() const -> token const*;

auto to_string() const

-> std::string;

// Internals

//

auto position() const -> source_position;

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

};

struct literal_node {

token const* literal = {};

token const* user_defined_suffix = {};

// API

//

auto get_token() const

-> token const*

{

return literal;

}

auto to_string() const

-> std::string

{

assert (literal);

auto ret = literal->to_string();

if (user_defined_suffix) {

ret += user_defined_suffix->to_string();

}

return ret;

}

// Internals

//

auto position() const

-> source_position

{

assert (literal);

return literal->position();

}

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

{

v.start(*this, depth);

assert (literal);

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

if (user_defined_suffix) {

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

}

v.end(*this, depth);

}

};

struct postfix_expression_node;

struct prefix_expression_node

{

std::vector<token const*> ops;

std::unique_ptr<postfix_expression_node> expr;

// API

//

auto is_fold_expression() const

-> bool;

auto is_identifier() const

-> bool;

auto is_id_expression() const

-> bool;

auto is_unqualified_id() const

-> bool;

auto is_expression_list() const

-> bool;

auto get_expression_list() const

-> expression_list_node const*;

auto get_postfix_expression_node() const

-> postfix_expression_node *

{

assert(expr);

return expr.get();

}

auto is_literal() const

-> bool;

auto get_literal() const

-> literal_node const*;

auto is_result_a_temporary_variable() const -> bool;

auto to_string() const

-> std::string;

// Internals

//

auto position() const -> source_position;

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

};

struct expression_node;

template<

String Name,

typename Term

>

struct binary_expression_node

{

std::unique_ptr<Term> expr;

expression_node const* my_expression = {};

binary_expression_node();

struct term

{

token const* op;

std::unique_ptr<Term> expr;

};

std::vector<term> terms;

// API

//

auto is_fold_expression() const

-> bool

{

// This is a fold-expression if any subexpression

// has an identifier named "..."

auto ret = expr->is_fold_expression();

for (auto& x : terms) {

ret |= x.expr->is_fold_expression();

}

return ret;

}

auto lhs_is_id_expression() const

-> bool

{

return expr->is_id_expression();

}

auto is_standalone_expression() const

-> bool;

auto terms_size() const

-> int

{

return unsafe_narrow<int>(std::ssize(terms));

}

auto is_identifier() const

-> bool

{

return terms.empty() && expr->is_identifier();

}

auto is_id_expression() const

-> bool

{

return terms.empty() && expr->is_id_expression();

}

auto is_unqualified_id() const

-> bool

{

return terms.empty() && expr->is_unqualified_id();

}

auto is_expression_list() const

-> bool

{

return terms.empty() && expr->is_expression_list();

}

auto get_expression_list() const

-> expression_list_node const*

{

if (is_expression_list()) {

return expr->get_expression_list();

}

return {};

}

auto is_literal() const

-> bool

{

return get_literal();

}

auto get_literal() const

-> literal_node const*

{

if (!terms.empty()) {

return nullptr;

}

// Else

return expr->get_literal();

}

// Get left-hand postfix-expression

auto get_postfix_expression_node() const

-> postfix_expression_node *

{

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 *

{

if (!terms.empty()) {

assert(terms.front().expr);

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

}

// else

return {};

}

// "Simple" means binary (size>0) and not chained (size<2)

struct get_lhs_rhs_if_simple_binary_expression_with_ret {

postfix_expression_node* lhs;

Term* rhs;

};

auto get_lhs_rhs_if_simple_binary_expression_with(lexeme op) const

-> get_lhs_rhs_if_simple_binary_expression_with_ret

{

if (

std::ssize(terms) == 1

&& terms[0].op->type() == op

)

{

return {

get_postfix_expression_node(),

terms.front().expr.get()

};

}

// Else

return { nullptr, nullptr };

}

auto is_result_a_temporary_variable() const -> bool {

if constexpr (std::string_view(Name.value) == "assignment") {

assert(expr);

return expr->is_result_a_temporary_variable();

} else {

if (terms.empty()) {

assert(expr);

return expr->is_result_a_temporary_variable();

} else {

return true;

}

}

}

auto to_string() const

-> std::string

{

assert (expr);

auto ret = expr->to_string();

for (auto const& x : terms) {

assert (x.op);

ret += " " + x.op->to_string();

assert (x.expr);

ret += " " + x.expr->to_string();

}

return ret;

}

// Internals

//

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);

}

};

struct is_as_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 assignment_expression_lhs_rhs {

postfix_expression_node* lhs;

logical_or_expression_node* rhs;

};

struct expression_statement_node;

struct expression_node

{

static inline std::vector<expression_node*> current_expressions = {}; // TODO: static ?

std::unique_ptr<assignment_expression_node> expr;

int num_subexpressions = 0;

expression_statement_node const* my_statement = {};

expression_node();

// API

//

auto is_fold_expression() const

-> bool

{

// This is a fold-expression if any subexpression

// has an identifier named "..."

return expr->is_fold_expression();

}

auto is_standalone_expression() const

-> bool;

auto subexpression_count() const

-> int

{

return num_subexpressions;

}

auto is_identifier() const

-> bool

{

return expr->is_identifier();

}

auto is_id_expression() const

-> bool

{

return expr->is_id_expression();

}

auto is_unqualified_id() const

-> bool

{

return expr->is_unqualified_id();

}

auto is_expression_list() const

-> bool

{

return expr->is_expression_list();

}

auto get_expression_list() const

-> expression_list_node const*

{

if (is_expression_list()) {

return expr->get_expression_list();

}

return {};

}

auto is_literal() const

-> bool

{

return get_literal();

}

auto get_literal() const

-> literal_node const*

{

return expr->get_literal();

}

auto get_lhs_rhs_if_simple_assignment() const

-> assignment_expression_lhs_rhs;

auto to_string() const

-> std::string

{

assert (expr);

return expr->to_string();

}

// Internals

//

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);

}

};

template<

String Name,

typename Term

>

binary_expression_node<Name, Term>::binary_expression_node() {

if (!expression_node::current_expressions.empty()) {

my_expression = expression_node::current_expressions.back();

}

}

template<

String Name,

typename Term

>

auto binary_expression_node<Name, Term>::is_standalone_expression() const

-> bool

{

return

my_expression

&& my_expression->is_standalone_expression()

;

}

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

auto to_passing_style(token const& t) -> passing_style {

if (t.type() == lexeme::Identifier) {

if (t == "in" ) { return passing_style::in; }

if (t == "copy" ) { return passing_style::copy; }

if (t == "inout" ) { return passing_style::inout; }

if (t == "out" ) { return passing_style::out; }

if (t == "move" ) { return passing_style::move; }

if (t == "forward") { return passing_style::forward; }

}

return passing_style::invalid;

}

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_style";

}

}

struct expression_list_node

{

token const* open_paren = {};

token const* close_paren = {};

bool inside_initializer = false;

struct term {

passing_style pass = {};

std::unique_ptr<expression_node> expr;

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

{

v.start(*this, depth);

assert(expr);

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

v.end(*this, depth);

}

};

std::vector< term > expressions;

// API

//

auto is_fold_expression() const

-> bool

{

// This is a fold-expression if any subexpression

// has an identifier named "..."

auto ret = false;

for (auto& x : expressions) {

ret |= x.expr->is_fold_expression();

}

return ret;

}

// Internals

//

auto position() const

-> source_position

{

// Make sure this got set

assert (open_paren);

return open_paren->position();

}

auto visit(auto& v, int depth)

-> void

{

v.start(*this, depth);

for (auto& x : expressions) {

x.visit(v, depth+1);

}

v.end(*this, depth);

}

};

auto primary_expression_node::is_identifier() const

-> bool

{

return expr.index() == identifier;

}

auto primary_expression_node::is_id_expression() const

-> bool

{

return expr.index() == id_expression;

}

auto primary_expression_node::is_expression_list() const

-> bool

{

return expr.index() == expression_list;

}

auto primary_expression_node::get_expression_list() const

-> expression_list_node const*

{

if (is_expression_list()) {

return std::get<expression_list>(expr).get();

}

return {};

}

auto primary_expression_node::is_literal() const

-> bool

{

return get_literal();

}

auto primary_expression_node::get_literal() const

-> literal_node const*

{

if (auto lit = std::get_if<literal>(&expr)) {

return (*lit).get();

}

// Else

return nullptr;

}

struct expression_statement_node

{

static inline std::vector<expression_statement_node*> current_expression_statements = {}; // TODO: static ?

std::unique_ptr<expression_node> expr;

bool has_semicolon = false;

// API

//

auto subexpression_count() const

-> int

{

assert (expr);

return expr->subexpression_count();

}

auto to_string() const

-> std::string

{

assert (expr);

return expr->to_string();

}

// Internals

//

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);

}

};

auto expression_node::is_standalone_expression() const

-> bool

{

return

my_statement

&& my_statement->subexpression_count() == subexpression_count()

;

}

struct capture {

postfix_expression_node* capture_expr;

std::string cap_sym = {};

std::string str = {};

std::string str_suppressed_move = {};

auto operator==(postfix_expression_node* p) { return capture_expr == p; }

};

struct capture_group {

std::vector<capture> members;

auto add(postfix_expression_node* p)

-> void

{

members.push_back({p});

}

auto remove(postfix_expression_node* p)

-> void;

~capture_group();

};

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 = {};

~postfix_expression_node();

// API

//

auto is_fold_expression() const

-> bool

{

// This is a fold-expression if any subexpression

// has an identifier named "..."

return expr->is_fold_expression();

}

auto is_identifier() const

-> bool

{

return ops.empty() && expr->is_identifier();

}

auto is_id_expression() const

-> bool

{

return ops.empty() && expr->is_id_expression();

}

auto is_unqualified_id() const

-> bool

{

return ops.empty() && expr->is_unqualified_id();

}

auto is_expression_list() const

-> bool

{

return ops.empty() && expr->is_expression_list();

}

auto get_expression_list() const

-> expression_list_node const*

{

if (is_expression_list()) {

return expr->get_expression_list();

}

return {};

}

auto is_literal() const

-> bool

{

return get_literal();

}

auto get_literal() const

-> literal_node const*

{

if (!ops.empty()) {

return nullptr;

}

// Else

return expr->get_literal();

}

auto get_first_token_ignoring_this() const

-> token const*;

auto is_result_a_temporary_variable() const -> bool {

if (ops.empty()) {

return false;

} else {

return (ops.front().op->type() == lexeme::Ampersand

|| ops.front().op->type() == lexeme::Tilde);

}

}

auto to_string() const

-> std::string;

// Internals

//

auto position() const -> source_position

{

assert (expr);

return expr->position();

}

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

};

auto prefix_expression_node::is_fold_expression() const

-> bool

{

// This is a fold-expression if any subexpression

// has an identifier named "..."

return expr->is_fold_expression();

}

auto prefix_expression_node::is_identifier() const

-> bool

{

return ops.empty() && expr->is_identifier();

}

auto prefix_expression_node::is_id_expression() const

-> bool

{

return ops.empty() && expr->is_id_expression();

}

auto prefix_expression_node::is_unqualified_id() const

-> bool

{

return ops.empty() && expr->is_unqualified_id();

}

auto prefix_expression_node::is_expression_list() const

-> bool

{

return ops.empty() && expr->is_expression_list();

}

auto prefix_expression_node::get_expression_list() const

-> expression_list_node const*

{

if (is_expression_list()) {

return expr->get_expression_list();

}

return {};

}

auto prefix_expression_node::is_literal() const

-> bool

{

return get_literal();

}

auto prefix_expression_node::get_literal() const

-> literal_node const*

{

if (!ops.empty()) {

return nullptr;

}

// Else

return expr->get_literal();

}

auto prefix_expression_node::is_result_a_temporary_variable() const -> bool {

if (ops.empty()) {