From f8a7c462736bf886adc8bc3bbf424d534391d3dc Mon Sep 17 00:00:00 2001 From: Karroffel Date: Fri, 30 Sep 2016 21:40:31 +0200 Subject: pattern matching: implemented parser --- modules/gdscript/gd_parser.cpp | 214 ++++++++++++++++++++++++++++++++++++++ modules/gdscript/gd_parser.h | 36 ++++++- modules/gdscript/gd_tokenizer.cpp | 2 + modules/gdscript/gd_tokenizer.h | 1 + 4 files changed, 252 insertions(+), 1 deletion(-) diff --git a/modules/gdscript/gd_parser.cpp b/modules/gdscript/gd_parser.cpp index 8f4f5ef4ca..99e5944f80 100644 --- a/modules/gdscript/gd_parser.cpp +++ b/modules/gdscript/gd_parser.cpp @@ -1567,6 +1567,193 @@ bool GDParser::_recover_from_completion() { return true; } +GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) +{ + + PatternNode *pattern = memnew(PatternNode); + + GDTokenizer::Token token = tokenizer->get_token(); + if (error_set) + return NULL; + + switch (token) { + // all the constants like strings and numbers + case GDTokenizer::TK_CONSTANT: { + Node *value = _parse_and_reduce_expression(pattern, p_static); + if (value->type != GDParser::Node::TYPE_CONSTANT) { + _set_error("Not a constant expression"); + return NULL; + } + pattern->pt_type = GDParser::PatternNode::PT_CONSTANT; + pattern->constant = static_cast(value); + } break; + + case GDTokenizer::TK_BRACKET_OPEN: { + tokenizer->advance(); + pattern->pt_type = GDParser::PatternNode::PT_ARRAY; + while (true) { + + if (tokenizer->get_token() == GDTokenizer::TK_BRACKET_CLOSE) { + tokenizer->advance(); + break; + } + + if (tokenizer->get_token() == GDTokenizer::TK_PERIOD && tokenizer->get_token(1) == GDTokenizer::TK_PERIOD) { + // match everything + tokenizer->advance(2); + pattern->pt_type = GDParser::PatternNode::PT_IGNORE_REST; + if (tokenizer->get_token() == GDTokenizer::TK_COMMA && tokenizer->get_token(1) == GDTokenizer::TK_BRACKET_CLOSE) { + tokenizer->advance(2); + break; + } else if (tokenizer->get_token() == GDTokenizer::TK_BRACKET_CLOSE) { + tokenizer->advance(1); + break; + } else { + _set_error("'..' pattern only allowed at the end of an array pattern"); + return NULL; + } + } + + PatternNode *sub_pattern = _parse_pattern(p_static); + if (!sub_pattern) { + return NULL; + } + + pattern->array.push_back(sub_pattern); + + if (tokenizer->get_token() == GDTokenizer::TK_COMMA) { + tokenizer->advance(); + continue; + } else if (tokenizer->get_token() == GDTokenizer::TK_BRACKET_CLOSE) { + tokenizer->advance(); + break; + } else { + _set_error("Not a valid pattern"); + return NULL; + } + } + } break; + + case GDTokenizer::TK_IDENTIFIER: { + pattern->pt_type = GDParser::PatternNode::PT_BIND; + pattern->bind = tokenizer->get_token_identifier(); + tokenizer->advance(); + } break; + + case GDTokenizer::TK_CURLY_BRACKET_OPEN: { + tokenizer->advance(); + pattern->pt_type = GDParser::PatternNode::PT_DICITIONARY; + while (true) { + + if (tokenizer->get_token() == GDTokenizer::TK_CURLY_BRACKET_CLOSE) { + tokenizer->advance(); + break; + } + + if (tokenizer->get_token() == GDTokenizer::TK_PERIOD && tokenizer->get_token(1) == GDTokenizer::TK_PERIOD) { + // match everything + tokenizer->advance(2); + pattern->pt_type = GDParser::PatternNode::PT_IGNORE_REST; + if (tokenizer->get_token() == GDTokenizer::TK_COMMA && tokenizer->get_token(1) == GDTokenizer::TK_CURLY_BRACKET_CLOSE) { + tokenizer->advance(2); + break; + } else if (tokenizer->get_token() == GDTokenizer::TK_CURLY_BRACKET_CLOSE) { + tokenizer->advance(1); + break; + } else { + _set_error("'..' pattern only allowed at the end of an dictionary pattern"); + return NULL; + } + } + + Node *key = _parse_and_reduce_expression(pattern, p_static); + if (!key) { + _set_error("Not a valid key in pattern"); + return NULL; + } + + if (key->type != GDParser::Node::TYPE_CONSTANT) { + _set_error("Not a constant expression as key"); + return NULL; + } + + if (tokenizer->get_token() == GDTokenizer::TK_COLON) { + tokenizer->advance(); + + PatternNode *value = _parse_pattern(p_static); + if (!value) { + _set_error("Expected pattern in dictionary value"); + return NULL; + } + + pattern->dictionary.insert(static_cast(key), value); + } else { + pattern->dictionary.insert(static_cast(key), NULL); + } + + + if (tokenizer->get_token() == GDTokenizer::TK_COMMA) { + tokenizer->advance(); + continue; + } else if (tokenizer->get_token() == GDTokenizer::TK_CURLY_BRACKET_CLOSE) { + tokenizer->advance(); + break; + } else { + _set_error("Not a valid pattern"); + return NULL; + } + } + } break; + + default: { + _set_error("Not a valid pattern"); + return NULL; + } + } + + return pattern; +} + +void GDParser::_parse_pattern_block(Vector &p_block, bool p_static) +{ + int indent_level = tab_level.back()->get(); + + while (true) { + + while (tokenizer->get_token() == GDTokenizer::TK_NEWLINE && _parse_newline()); + + // GDTokenizer::Token token = tokenizer->get_token(); + if (error_set) + return; + + if (indent_level > tab_level.back()->get()) { + return; // go back a level + } + + if (pending_newline!=-1) { + pending_newline=-1; + } + + PatternBranchNode *branch = memnew(PatternBranchNode); + + branch->pattern = _parse_pattern(p_static); + if (!branch->pattern) { + return; + } + + if(!_enter_indent_block()) { + _set_error("Expected block in pattern branch"); + return; + } + + branch->body = memnew(BlockNode); + + _parse_block(branch->body, p_static); + + p_block.push_back(branch); + } +} + void GDParser::_parse_block(BlockNode *p_block,bool p_static) { int indent_level = tab_level.back()->get(); @@ -1969,6 +2156,33 @@ void GDParser::_parse_block(BlockNode *p_block,bool p_static) { } + } break; + case GDTokenizer::TK_CF_MATCH: { + + tokenizer->advance(); + + ControlFlowNode *match_node = memnew(ControlFlowNode); + match_node->cf_type = ControlFlowNode::CF_MATCH; + + Node *val_to_match = _parse_and_reduce_expression(p_block, p_static); + + if (!val_to_match) { + if (_recover_from_completion()) { + break; + } + return; + } + + match_node->arguments.push_back(val_to_match); + + if (!_enter_indent_block()) { + _set_error("Expected indented pattern matching block after 'match'"); + return; + } + + _parse_pattern_block(match_node->branches, p_static); + + p_block->statements.push_back(match_node); } break; case GDTokenizer::TK_PR_ASSERT: { diff --git a/modules/gdscript/gd_parser.h b/modules/gdscript/gd_parser.h index 75653e0916..f36cb8a732 100644 --- a/modules/gdscript/gd_parser.h +++ b/modules/gdscript/gd_parser.h @@ -257,6 +257,31 @@ public: Vector arguments; OperatorNode() { type=TYPE_OPERATOR; } }; + + + struct PatternNode : public Node { + + enum PatternType { + PT_CONSTANT, + PT_BIND, + PT_DICITIONARY, + PT_ARRAY, + PT_IGNORE_REST + }; + + PatternType pt_type; + + ConstantNode *constant; + StringName bind; + Map dictionary; + Vector array; + + }; + + struct PatternBranchNode : public Node { + PatternNode *pattern; + BlockNode *body; + }; struct ControlFlowNode : public Node { enum CFType { @@ -266,13 +291,15 @@ public: CF_SWITCH, CF_BREAK, CF_CONTINUE, - CF_RETURN + CF_RETURN, + CF_MATCH }; CFType cf_type; Vector arguments; BlockNode *body; BlockNode *body_else; + Vector branches; ControlFlowNode *_else; //used for if ControlFlowNode() { type=TYPE_CONTROL_FLOW; cf_type=CF_IF; body=NULL; body_else=NULL;} @@ -450,6 +477,13 @@ private: Node* _reduce_expression(Node *p_node,bool p_to_const=false); Node* _parse_and_reduce_expression(Node *p_parent,bool p_static,bool p_reduce_const=false,bool p_allow_assign=false); + + // TODO + void _parse_pattern_block(Vector &p_block, bool p_static); + + PatternNode *_parse_pattern(bool p_static); + + void _parse_block(BlockNode *p_block,bool p_static); void _parse_extends(ClassNode *p_class); void _parse_class(ClassNode *p_class); diff --git a/modules/gdscript/gd_tokenizer.cpp b/modules/gdscript/gd_tokenizer.cpp index 2041ec12ad..13ec059f84 100644 --- a/modules/gdscript/gd_tokenizer.cpp +++ b/modules/gdscript/gd_tokenizer.cpp @@ -85,6 +85,7 @@ const char* GDTokenizer::token_names[TK_MAX]={ "continue", "pass", "return", +"match", "func", "class", "extends", @@ -888,6 +889,7 @@ void GDTokenizerText::_advance() { {TK_CF_BREAK,"break"}, {TK_CF_CONTINUE,"continue"}, {TK_CF_RETURN,"return"}, + {TK_CF_MATCH, "match"}, {TK_CF_PASS,"pass"}, {TK_SELF,"self"}, {TK_CONST_PI,"PI"}, diff --git a/modules/gdscript/gd_tokenizer.h b/modules/gdscript/gd_tokenizer.h index b91229ab1e..f67e962ca3 100644 --- a/modules/gdscript/gd_tokenizer.h +++ b/modules/gdscript/gd_tokenizer.h @@ -92,6 +92,7 @@ public: TK_CF_CONTINUE, TK_CF_PASS, TK_CF_RETURN, + TK_CF_MATCH, TK_PR_FUNCTION, TK_PR_CLASS, TK_PR_EXTENDS, -- cgit v1.2.3 From d445f0639fa9eccc44f1f9c153108f9e90981077 Mon Sep 17 00:00:00 2001 From: Karroffel Date: Wed, 5 Oct 2016 18:48:38 +0200 Subject: pattern matcher: Implemented transformations --- modules/gdscript/gd_compiler.cpp | 10 +- modules/gdscript/gd_parser.cpp | 391 ++++++++++++++++++++++++++++++++++++--- modules/gdscript/gd_parser.h | 27 ++- 3 files changed, 393 insertions(+), 35 deletions(-) diff --git a/modules/gdscript/gd_compiler.cpp b/modules/gdscript/gd_compiler.cpp index 2e2cbe7b29..f7765200b9 100644 --- a/modules/gdscript/gd_compiler.cpp +++ b/modules/gdscript/gd_compiler.cpp @@ -980,7 +980,7 @@ int GDCompiler::_parse_expression(CodeGen& codegen,const GDParser::Node *p_expre } break; //TYPE_TYPE, default: { - + ERR_EXPLAIN("Bug in bytecode compiler, unexpected node in parse tree while parsing expression."); ERR_FAIL_V(-1); //unreachable code } break; @@ -1019,7 +1019,13 @@ Error GDCompiler::_parse_block(CodeGen& codegen,const GDParser::BlockNode *p_blo switch(cf->cf_type) { - + case GDParser::ControlFlowNode::CF_MATCH: { + Error err = _parse_block(codegen,cf->match->compiled_block,p_stack_level,p_break_addr,p_continue_addr); + if (err) + return err; + + } break; + case GDParser::ControlFlowNode::CF_IF: { #ifdef DEBUG_ENABLED diff --git a/modules/gdscript/gd_parser.cpp b/modules/gdscript/gd_parser.cpp index 99e5944f80..1ea2dbe872 100644 --- a/modules/gdscript/gd_parser.cpp +++ b/modules/gdscript/gd_parser.cpp @@ -1570,24 +1570,18 @@ bool GDParser::_recover_from_completion() { GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) { - PatternNode *pattern = memnew(PatternNode); + PatternNode *pattern = alloc_node(); GDTokenizer::Token token = tokenizer->get_token(); if (error_set) return NULL; + if (token == GDTokenizer::TK_EOF) { + return NULL; + } + switch (token) { // all the constants like strings and numbers - case GDTokenizer::TK_CONSTANT: { - Node *value = _parse_and_reduce_expression(pattern, p_static); - if (value->type != GDParser::Node::TYPE_CONSTANT) { - _set_error("Not a constant expression"); - return NULL; - } - pattern->pt_type = GDParser::PatternNode::PT_CONSTANT; - pattern->constant = static_cast(value); - } break; - case GDTokenizer::TK_BRACKET_OPEN: { tokenizer->advance(); pattern->pt_type = GDParser::PatternNode::PT_ARRAY; @@ -1601,7 +1595,9 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) if (tokenizer->get_token() == GDTokenizer::TK_PERIOD && tokenizer->get_token(1) == GDTokenizer::TK_PERIOD) { // match everything tokenizer->advance(2); - pattern->pt_type = GDParser::PatternNode::PT_IGNORE_REST; + PatternNode *sub_pattern = alloc_node(); + sub_pattern->pt_type = GDParser::PatternNode::PT_IGNORE_REST; + pattern->array.push_back(sub_pattern); if (tokenizer->get_token() == GDTokenizer::TK_COMMA && tokenizer->get_token(1) == GDTokenizer::TK_BRACKET_CLOSE) { tokenizer->advance(2); break; @@ -1634,7 +1630,8 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) } } break; - case GDTokenizer::TK_IDENTIFIER: { + case GDTokenizer::TK_PR_VAR: { + tokenizer->advance(); pattern->pt_type = GDParser::PatternNode::PT_BIND; pattern->bind = tokenizer->get_token_identifier(); tokenizer->advance(); @@ -1642,7 +1639,7 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) case GDTokenizer::TK_CURLY_BRACKET_OPEN: { tokenizer->advance(); - pattern->pt_type = GDParser::PatternNode::PT_DICITIONARY; + pattern->pt_type = GDParser::PatternNode::PT_DICTIONARY; while (true) { if (tokenizer->get_token() == GDTokenizer::TK_CURLY_BRACKET_CLOSE) { @@ -1653,7 +1650,9 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) if (tokenizer->get_token() == GDTokenizer::TK_PERIOD && tokenizer->get_token(1) == GDTokenizer::TK_PERIOD) { // match everything tokenizer->advance(2); - pattern->pt_type = GDParser::PatternNode::PT_IGNORE_REST; + PatternNode *sub_pattern = alloc_node(); + sub_pattern->pt_type = PatternNode::PT_IGNORE_REST; + pattern->array.push_back(sub_pattern); if (tokenizer->get_token() == GDTokenizer::TK_COMMA && tokenizer->get_token(1) == GDTokenizer::TK_CURLY_BRACKET_CLOSE) { tokenizer->advance(2); break; @@ -1706,15 +1705,24 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) } break; default: { - _set_error("Not a valid pattern"); - return NULL; - } + Node *value = _parse_and_reduce_expression(pattern, p_static); + if (error_set) { + return NULL; + } + if (value->type == Node::TYPE_IDENTIFIER && static_cast(value)->name == "_") { + // wildcard pattern + pattern->pt_type = PatternNode::PT_WILDCARD; + break; + } + pattern->pt_type = PatternNode::PT_CONSTANT; + pattern->constant = value; + } break; } return pattern; } -void GDParser::_parse_pattern_block(Vector &p_block, bool p_static) +void GDParser::_parse_pattern_block(BlockNode *p_block, Vector &p_branches, bool p_static) { int indent_level = tab_level.back()->get(); @@ -1734,7 +1742,7 @@ void GDParser::_parse_pattern_block(Vector &p_block, bool p_ pending_newline=-1; } - PatternBranchNode *branch = memnew(PatternBranchNode); + PatternBranchNode *branch = alloc_node(); branch->pattern = _parse_pattern(p_static); if (!branch->pattern) { @@ -1746,12 +1754,324 @@ void GDParser::_parse_pattern_block(Vector &p_block, bool p_ return; } - branch->body = memnew(BlockNode); + branch->body = alloc_node(); + branch->body->parent_block = p_block; + p_block->sub_blocks.push_back(branch->body); + current_block = branch->body; _parse_block(branch->body, p_static); - p_block.push_back(branch); + current_block = p_block; + + p_branches.push_back(branch); + } +} + +void GDParser::_generate_array_pattern(PatternNode *p_array_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings) +{ + bool open_ended = false; + + if (p_array_pattern->array.size() > 0) { + if (p_array_pattern->array[p_array_pattern->array.size() - 1]->pt_type == PatternNode::PT_IGNORE_REST) { + open_ended = true; + } + } + + // check length + + // typeof(value_to_match) == TYPE_ARRAY && value_to_match.size() >= length + // typeof(value_to_match) == TYPE_ARRAY && value_to_match.size() == length + + { + + // typecheck + BuiltInFunctionNode *typeof_node = alloc_node(); + typeof_node->function = GDFunctions::TYPE_OF; + + OperatorNode *typeof_match_value = alloc_node(); + typeof_match_value->op = OperatorNode::OP_CALL; + typeof_match_value->arguments.push_back(typeof_node); + typeof_match_value->arguments.push_back(p_value_to_match); + + IdentifierNode *typeof_array = alloc_node(); + typeof_array->name = "TYPE_ARRAY"; + + OperatorNode *type_comp = alloc_node(); + type_comp->op = OperatorNode::OP_EQUAL; + type_comp->arguments.push_back(typeof_match_value); + type_comp->arguments.push_back(typeof_array); + + + ConstantNode *length = alloc_node(); + length->value = Variant(open_ended ? p_array_pattern->array.size() - 1 : p_array_pattern->array.size()); + + + OperatorNode *call = alloc_node(); + call->op = OperatorNode::OP_CALL; + call->arguments.push_back(p_value_to_match); + + IdentifierNode *size = alloc_node(); + size->name = "size"; + call->arguments.push_back(size); + + OperatorNode *length_comparison = alloc_node(); + length_comparison->op = open_ended ? OperatorNode::OP_GREATER_EQUAL : OperatorNode::OP_EQUAL; + length_comparison->arguments.push_back(call); + length_comparison->arguments.push_back(length); + + OperatorNode *type_and_length_comparison = alloc_node(); + type_and_length_comparison->op = OperatorNode::OP_AND; + type_and_length_comparison->arguments.push_back(type_comp); + type_and_length_comparison->arguments.push_back(length_comparison); + + p_resulting_node = type_and_length_comparison; + } + + + + for (int i = 0; i < p_array_pattern->array.size(); i++) { + PatternNode *pattern = p_array_pattern->array[i]; + + Node *condition = NULL; + + ConstantNode *index = alloc_node(); + index->value = Variant(i); + + OperatorNode *indexed_value = alloc_node(); + indexed_value->op = OperatorNode::OP_INDEX; + indexed_value->arguments.push_back(p_value_to_match); + indexed_value->arguments.push_back(index); + + _generate_pattern(pattern, indexed_value, condition, p_bindings); + + OperatorNode *and_node = alloc_node(); + and_node->op = OperatorNode::OP_AND; + and_node->arguments.push_back(p_resulting_node); + and_node->arguments.push_back(condition); + + p_resulting_node = and_node; + } +} + +void GDParser::_generate_bind_pattern(PatternNode *p_bind_pattern, Node *p_value_to_match, Map &p_bindings) +{ + p_bindings[p_bind_pattern->bind] = p_value_to_match; +} + +void GDParser::_generate_constant_pattern(PatternNode *p_constant_pattern, Node *p_value_to_match, Node *&p_resulting_node) +{ + BuiltInFunctionNode *typeof_node = alloc_node(); + typeof_node->function = GDFunctions::TYPE_OF; + + OperatorNode *typeof_match_value = alloc_node(); + typeof_match_value->op = OperatorNode::OP_CALL; + typeof_match_value->arguments.push_back(typeof_node); + typeof_match_value->arguments.push_back(p_value_to_match); + + OperatorNode *typeof_pattern_value = alloc_node(); + typeof_pattern_value->op = OperatorNode::OP_CALL; + typeof_pattern_value->arguments.push_back(typeof_node); + typeof_pattern_value->arguments.push_back(p_constant_pattern->constant); + + OperatorNode *type_comp = alloc_node(); + type_comp->op = OperatorNode::OP_EQUAL; + type_comp->arguments.push_back(typeof_match_value); + type_comp->arguments.push_back(typeof_pattern_value); + + OperatorNode *value_comp = alloc_node(); + value_comp->op = OperatorNode::OP_EQUAL; + value_comp->arguments.push_back(p_constant_pattern->constant); + value_comp->arguments.push_back(p_value_to_match); + + + OperatorNode *comparison = alloc_node(); + comparison->op = OperatorNode::OP_AND; + comparison->arguments.push_back(type_comp); + comparison->arguments.push_back(value_comp); + + p_resulting_node = comparison; + +} + + +void GDParser::_generate_dict_pattern(PatternNode *p_dict_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings) +{ + bool open_ended = false; + + if (p_dict_pattern->array.size() > 0) { + open_ended = true; + print_line("open dictionary"); + } + + // check length + + // typeof(value_to_match) == TYPE_DICTIONARY && value_to_match.size() >= length + // typeof(value_to_match) == TYPE_DICTIONARY && value_to_match.size() == length + + + { + + // typecheck + BuiltInFunctionNode *typeof_node = alloc_node(); + typeof_node->function = GDFunctions::TYPE_OF; + + OperatorNode *typeof_match_value = alloc_node(); + typeof_match_value->op = OperatorNode::OP_CALL; + typeof_match_value->arguments.push_back(typeof_node); + typeof_match_value->arguments.push_back(p_value_to_match); + + IdentifierNode *typeof_dictionary = alloc_node(); + typeof_dictionary->name = "TYPE_DICTIONARY"; + + OperatorNode *type_comp = alloc_node(); + type_comp->op = OperatorNode::OP_EQUAL; + type_comp->arguments.push_back(typeof_match_value); + type_comp->arguments.push_back(typeof_dictionary); + + + ConstantNode *length = alloc_node(); + length->value = Variant(open_ended ? p_dict_pattern->dictionary.size() - 1 : p_dict_pattern->dictionary.size()); + + + OperatorNode *call = alloc_node(); + call->op = OperatorNode::OP_CALL; + call->arguments.push_back(p_value_to_match); + + IdentifierNode *size = alloc_node(); + size->name = "size"; + call->arguments.push_back(size); + + OperatorNode *length_comparison = alloc_node(); + length_comparison->op = open_ended ? OperatorNode::OP_GREATER_EQUAL : OperatorNode::OP_EQUAL; + length_comparison->arguments.push_back(call); + length_comparison->arguments.push_back(length); + + OperatorNode *type_and_length_comparison = alloc_node(); + type_and_length_comparison->op = OperatorNode::OP_AND; + type_and_length_comparison->arguments.push_back(type_comp); + type_and_length_comparison->arguments.push_back(length_comparison); + + p_resulting_node = type_and_length_comparison; + } + + + + for (Map::Element *e = p_dict_pattern->dictionary.front(); e; e = e->next()) { + + Node *condition = NULL; + + // chech for has, then for pattern + + IdentifierNode *has = alloc_node(); + has->name = "has"; + + OperatorNode *has_call = alloc_node(); + has_call->op = OperatorNode::OP_CALL; + has_call->arguments.push_back(p_value_to_match); + has_call->arguments.push_back(has); + has_call->arguments.push_back(e->key()); + + + if (e->value()) { + + OperatorNode *indexed_value = alloc_node(); + indexed_value->op = OperatorNode::OP_INDEX; + indexed_value->arguments.push_back(p_value_to_match); + indexed_value->arguments.push_back(e->key()); + + _generate_pattern(e->value(), indexed_value, condition, p_bindings); + + OperatorNode *has_and_pattern = alloc_node(); + has_and_pattern->op = OperatorNode::OP_AND; + has_and_pattern->arguments.push_back(has_call); + has_and_pattern->arguments.push_back(condition); + + condition = has_and_pattern; + + } else { + condition = has_call; + } + + + + + OperatorNode *and_node = alloc_node(); + and_node->op = OperatorNode::OP_AND; + and_node->arguments.push_back(p_resulting_node); + and_node->arguments.push_back(condition); + + p_resulting_node = and_node; } + +} + + +void GDParser::_generate_pattern(PatternNode *p_pattern, Node *p_node_to_match, Node *&p_resulting_node, Map &p_bindings) +{ + switch (p_pattern->pt_type) { + case PatternNode::PT_CONSTANT: { + _generate_constant_pattern(p_pattern, p_node_to_match, p_resulting_node); + } break; + case PatternNode::PT_BIND: { + _generate_bind_pattern(p_pattern, p_node_to_match, p_bindings); + + ConstantNode *true_value = alloc_node(); + true_value->value = Variant(true); + p_resulting_node = true_value; + } break; + case PatternNode::PT_ARRAY: { + _generate_array_pattern(p_pattern, p_node_to_match, p_resulting_node, p_bindings); + } break; + case PatternNode::PT_DICTIONARY: { + _generate_dict_pattern(p_pattern, p_node_to_match, p_resulting_node, p_bindings); + } break; + case PatternNode::PT_WILDCARD: { + // simply generate a `true` + ConstantNode *true_value = alloc_node(); + true_value->value = Variant(true); + p_resulting_node = true_value; + } break; + default: { + + } break; + } +} + +void GDParser::_transform_match_statment(BlockNode *p_block, MatchNode *p_match_statement) +{ + LocalVarNode *val_to_match = alloc_node(); + val_to_match->name = "#match_value"; // use a name that can't be referenced in GDscript + val_to_match->assign = p_match_statement->val_to_match; + + p_block->statements.push_back(val_to_match); + + + IdentifierNode *id = alloc_node(); + id->name=val_to_match->name; + + OperatorNode *op = alloc_node(); + op->op=OperatorNode::OP_ASSIGN; + op->arguments.push_back(id); + op->arguments.push_back(val_to_match->assign); + p_block->statements.push_back(op); + + + + for (int i = 0; i < p_match_statement->branches.size(); i++) { + PatternBranchNode *branch = p_match_statement->branches[i]; + Map bindings; + Node *resulting_node; + _generate_pattern(branch->pattern, id, resulting_node, bindings); + + // TEMP: if's for testing + ControlFlowNode *cf_if = alloc_node(); + cf_if->cf_type = ControlFlowNode::CF_IF; + cf_if->arguments.push_back(resulting_node); + cf_if->body = branch->body; + + p_block->statements.push_back(cf_if); + } + } void GDParser::_parse_block(BlockNode *p_block,bool p_static) { @@ -2161,8 +2481,7 @@ void GDParser::_parse_block(BlockNode *p_block,bool p_static) { tokenizer->advance(); - ControlFlowNode *match_node = memnew(ControlFlowNode); - match_node->cf_type = ControlFlowNode::CF_MATCH; + MatchNode *match_node = alloc_node(); Node *val_to_match = _parse_and_reduce_expression(p_block, p_static); @@ -2173,16 +2492,32 @@ void GDParser::_parse_block(BlockNode *p_block,bool p_static) { return; } - match_node->arguments.push_back(val_to_match); + match_node->val_to_match = val_to_match; if (!_enter_indent_block()) { _set_error("Expected indented pattern matching block after 'match'"); return; } - _parse_pattern_block(match_node->branches, p_static); - - p_block->statements.push_back(match_node); + BlockNode *compiled_branches = alloc_node(); + compiled_branches->parent_block = p_block; + compiled_branches->parent_class = p_block->parent_class; + + p_block->sub_blocks.push_back(compiled_branches); + + _parse_pattern_block(compiled_branches, match_node->branches, p_static); + + _transform_match_statment(compiled_branches, match_node); + + match_node->compiled_block = compiled_branches; + + ControlFlowNode *match_cf_node = alloc_node(); + match_cf_node->cf_type = ControlFlowNode::CF_MATCH; + match_cf_node->match = match_node; + + p_block->statements.push_back(match_cf_node); + + _end_statement(); } break; case GDTokenizer::TK_PR_ASSERT: { diff --git a/modules/gdscript/gd_parser.h b/modules/gdscript/gd_parser.h index f36cb8a732..6ee55b433a 100644 --- a/modules/gdscript/gd_parser.h +++ b/modules/gdscript/gd_parser.h @@ -264,14 +264,15 @@ public: enum PatternType { PT_CONSTANT, PT_BIND, - PT_DICITIONARY, + PT_DICTIONARY, PT_ARRAY, - PT_IGNORE_REST + PT_IGNORE_REST, + PT_WILDCARD }; PatternType pt_type; - ConstantNode *constant; + Node *constant; StringName bind; Map dictionary; Vector array; @@ -282,6 +283,13 @@ public: PatternNode *pattern; BlockNode *body; }; + + struct MatchNode : public Node { + Node *val_to_match; + Vector branches; + + BlockNode *compiled_block; + }; struct ControlFlowNode : public Node { enum CFType { @@ -299,7 +307,8 @@ public: Vector arguments; BlockNode *body; BlockNode *body_else; - Vector branches; + + MatchNode *match; ControlFlowNode *_else; //used for if ControlFlowNode() { type=TYPE_CONTROL_FLOW; cf_type=CF_IF; body=NULL; body_else=NULL;} @@ -479,9 +488,17 @@ private: // TODO - void _parse_pattern_block(Vector &p_block, bool p_static); + void _parse_pattern_block(BlockNode *p_block, Vector &p_branches, bool p_static); PatternNode *_parse_pattern(bool p_static); + void _transform_match_statment(BlockNode *p_block, MatchNode *p_match_statement); + + void _generate_pattern(PatternNode *p_pattern, Node *p_node_to_match, Node *&p_resulting_node, Map &p_bindings); + + void _generate_array_pattern(PatternNode *p_array_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings); + void _generate_bind_pattern(PatternNode *p_bind_pattern, Node *p_value_to_match, Map &p_bindings); + void _generate_constant_pattern(PatternNode *p_constant_pattern, Node *p_value_to_match, Node *&p_resulting_node); + void _generate_dict_pattern(PatternNode *p_dict_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings); void _parse_block(BlockNode *p_block,bool p_static); -- cgit v1.2.3 From e781a7e07ec7388deccd372899ecbea8af7b67f4 Mon Sep 17 00:00:00 2001 From: Karroffel Date: Sun, 16 Oct 2016 13:20:28 +0200 Subject: pattern matcher: Implemented backend changed comments --- modules/gdscript/gd_compiler.cpp | 67 ++++- modules/gdscript/gd_parser.cpp | 571 ++++++++++++++++++++------------------- modules/gdscript/gd_parser.h | 19 +- modules/gdscript/gd_script.cpp | 1 + 4 files changed, 372 insertions(+), 286 deletions(-) diff --git a/modules/gdscript/gd_compiler.cpp b/modules/gdscript/gd_compiler.cpp index f7765200b9..139fdaad0d 100644 --- a/modules/gdscript/gd_compiler.cpp +++ b/modules/gdscript/gd_compiler.cpp @@ -980,7 +980,7 @@ int GDCompiler::_parse_expression(CodeGen& codegen,const GDParser::Node *p_expre } break; //TYPE_TYPE, default: { - + ERR_EXPLAIN("Bug in bytecode compiler, unexpected node in parse tree while parsing expression."); ERR_FAIL_V(-1); //unreachable code } break; @@ -1020,9 +1020,68 @@ Error GDCompiler::_parse_block(CodeGen& codegen,const GDParser::BlockNode *p_blo switch(cf->cf_type) { case GDParser::ControlFlowNode::CF_MATCH: { - Error err = _parse_block(codegen,cf->match->compiled_block,p_stack_level,p_break_addr,p_continue_addr); - if (err) - return err; + GDParser::MatchNode *match = cf->match; + + GDParser::IdentifierNode *id = memnew(GDParser::IdentifierNode); + id->name = "#match_value"; + + // var #match_value + // copied because there is no _parse_statement :( + codegen.add_stack_identifier(id->name, p_stack_level++); + codegen.alloc_stack(p_stack_level); + new_identifiers++; + + GDParser::OperatorNode *op = memnew(GDParser::OperatorNode); + op->op=GDParser::OperatorNode::OP_ASSIGN; + op->arguments.push_back(id); + op->arguments.push_back(match->val_to_match); + + int ret = _parse_expression(codegen, op, p_stack_level); + if (ret < 0) { + return ERR_PARSE_ERROR; + } + + // break address + codegen.opcodes.push_back(GDFunction::OPCODE_JUMP); + codegen.opcodes.push_back(codegen.opcodes.size() + 3); + int break_addr = codegen.opcodes.size(); + codegen.opcodes.push_back(GDFunction::OPCODE_JUMP); + codegen.opcodes.push_back(0); // break addr + + for (int j = 0; j < match->compiled_pattern_branches.size(); j++) { + GDParser::MatchNode::CompiledPatternBranch branch = match->compiled_pattern_branches[j]; + + // jump over continue + // jump unconditionally + // continue address + // compile the condition + int ret = _parse_expression(codegen, branch.compiled_pattern, p_stack_level); + if (ret < 0) { + return ERR_PARSE_ERROR; + } + + codegen.opcodes.push_back(GDFunction::OPCODE_JUMP_IF); + codegen.opcodes.push_back(ret); + codegen.opcodes.push_back(codegen.opcodes.size() + 3); + int continue_addr = codegen.opcodes.size(); + codegen.opcodes.push_back(GDFunction::OPCODE_JUMP); + codegen.opcodes.push_back(0); + + + + Error err = _parse_block(codegen, branch.body, p_stack_level, p_break_addr, continue_addr); + if (err) { + return ERR_PARSE_ERROR; + } + + codegen.opcodes.push_back(GDFunction::OPCODE_JUMP); + codegen.opcodes.push_back(break_addr); + + codegen.opcodes[continue_addr + 1] = codegen.opcodes.size(); + } + + codegen.opcodes[break_addr + 1] = codegen.opcodes.size(); + } break; diff --git a/modules/gdscript/gd_parser.cpp b/modules/gdscript/gd_parser.cpp index 1ea2dbe872..76ddb50435 100644 --- a/modules/gdscript/gd_parser.cpp +++ b/modules/gdscript/gd_parser.cpp @@ -1581,7 +1581,7 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) } switch (token) { - // all the constants like strings and numbers + // dictionary case GDTokenizer::TK_BRACKET_OPEN: { tokenizer->advance(); pattern->pt_type = GDParser::PatternNode::PT_ARRAY; @@ -1629,14 +1629,14 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) } } } break; - + // bind case GDTokenizer::TK_PR_VAR: { tokenizer->advance(); pattern->pt_type = GDParser::PatternNode::PT_BIND; pattern->bind = tokenizer->get_token_identifier(); tokenizer->advance(); } break; - + // array case GDTokenizer::TK_CURLY_BRACKET_OPEN: { tokenizer->advance(); pattern->pt_type = GDParser::PatternNode::PT_DICTIONARY; @@ -1703,7 +1703,7 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) } } } break; - + // all the constants like strings and numbers default: { Node *value = _parse_and_reduce_expression(pattern, p_static); if (error_set) { @@ -1714,6 +1714,12 @@ GDParser::PatternNode *GDParser::_parse_pattern(bool p_static) pattern->pt_type = PatternNode::PT_WILDCARD; break; } + + if (value->type != Node::TYPE_IDENTIFIER && value->type != Node::TYPE_CONSTANT) { + _set_error("Only constant expressions or variables allowed in a pattern"); + return NULL; + } + pattern->pt_type = PatternNode::PT_CONSTANT; pattern->constant = value; } break; @@ -1744,11 +1750,19 @@ void GDParser::_parse_pattern_block(BlockNode *p_block, Vector(); - branch->pattern = _parse_pattern(p_static); - if (!branch->pattern) { + branch->patterns.push_back(_parse_pattern(p_static)); + if (!branch->patterns[0]) { return; } + while (tokenizer->get_token() == GDTokenizer::TK_COMMA) { + tokenizer->advance(); + branch->patterns.push_back(_parse_pattern(p_static)); + if (!branch->patterns[branch->patterns.size() - 1]) { + return; + } + } + if(!_enter_indent_block()) { _set_error("Expected block in pattern branch"); return; @@ -1767,264 +1781,246 @@ void GDParser::_parse_pattern_block(BlockNode *p_block, Vector &p_bindings) -{ - bool open_ended = false; - - if (p_array_pattern->array.size() > 0) { - if (p_array_pattern->array[p_array_pattern->array.size() - 1]->pt_type == PatternNode::PT_IGNORE_REST) { - open_ended = true; - } - } - - // check length - - // typeof(value_to_match) == TYPE_ARRAY && value_to_match.size() >= length - // typeof(value_to_match) == TYPE_ARRAY && value_to_match.size() == length - - { - // typecheck - BuiltInFunctionNode *typeof_node = alloc_node(); - typeof_node->function = GDFunctions::TYPE_OF; - - OperatorNode *typeof_match_value = alloc_node(); - typeof_match_value->op = OperatorNode::OP_CALL; - typeof_match_value->arguments.push_back(typeof_node); - typeof_match_value->arguments.push_back(p_value_to_match); - - IdentifierNode *typeof_array = alloc_node(); - typeof_array->name = "TYPE_ARRAY"; - - OperatorNode *type_comp = alloc_node(); - type_comp->op = OperatorNode::OP_EQUAL; - type_comp->arguments.push_back(typeof_match_value); - type_comp->arguments.push_back(typeof_array); - - - ConstantNode *length = alloc_node(); - length->value = Variant(open_ended ? p_array_pattern->array.size() - 1 : p_array_pattern->array.size()); - - - OperatorNode *call = alloc_node(); - call->op = OperatorNode::OP_CALL; - call->arguments.push_back(p_value_to_match); - - IdentifierNode *size = alloc_node(); - size->name = "size"; - call->arguments.push_back(size); - - OperatorNode *length_comparison = alloc_node(); - length_comparison->op = open_ended ? OperatorNode::OP_GREATER_EQUAL : OperatorNode::OP_EQUAL; - length_comparison->arguments.push_back(call); - length_comparison->arguments.push_back(length); - - OperatorNode *type_and_length_comparison = alloc_node(); - type_and_length_comparison->op = OperatorNode::OP_AND; - type_and_length_comparison->arguments.push_back(type_comp); - type_and_length_comparison->arguments.push_back(length_comparison); - - p_resulting_node = type_and_length_comparison; - } - - - - for (int i = 0; i < p_array_pattern->array.size(); i++) { - PatternNode *pattern = p_array_pattern->array[i]; - - Node *condition = NULL; - - ConstantNode *index = alloc_node(); - index->value = Variant(i); - - OperatorNode *indexed_value = alloc_node(); - indexed_value->op = OperatorNode::OP_INDEX; - indexed_value->arguments.push_back(p_value_to_match); - indexed_value->arguments.push_back(index); - - _generate_pattern(pattern, indexed_value, condition, p_bindings); - - OperatorNode *and_node = alloc_node(); - and_node->op = OperatorNode::OP_AND; - and_node->arguments.push_back(p_resulting_node); - and_node->arguments.push_back(condition); - - p_resulting_node = and_node; - } -} - -void GDParser::_generate_bind_pattern(PatternNode *p_bind_pattern, Node *p_value_to_match, Map &p_bindings) -{ - p_bindings[p_bind_pattern->bind] = p_value_to_match; -} - -void GDParser::_generate_constant_pattern(PatternNode *p_constant_pattern, Node *p_value_to_match, Node *&p_resulting_node) -{ - BuiltInFunctionNode *typeof_node = alloc_node(); - typeof_node->function = GDFunctions::TYPE_OF; - - OperatorNode *typeof_match_value = alloc_node(); - typeof_match_value->op = OperatorNode::OP_CALL; - typeof_match_value->arguments.push_back(typeof_node); - typeof_match_value->arguments.push_back(p_value_to_match); - - OperatorNode *typeof_pattern_value = alloc_node(); - typeof_pattern_value->op = OperatorNode::OP_CALL; - typeof_pattern_value->arguments.push_back(typeof_node); - typeof_pattern_value->arguments.push_back(p_constant_pattern->constant); - - OperatorNode *type_comp = alloc_node(); - type_comp->op = OperatorNode::OP_EQUAL; - type_comp->arguments.push_back(typeof_match_value); - type_comp->arguments.push_back(typeof_pattern_value); - - OperatorNode *value_comp = alloc_node(); - value_comp->op = OperatorNode::OP_EQUAL; - value_comp->arguments.push_back(p_constant_pattern->constant); - value_comp->arguments.push_back(p_value_to_match); - - - OperatorNode *comparison = alloc_node(); - comparison->op = OperatorNode::OP_AND; - comparison->arguments.push_back(type_comp); - comparison->arguments.push_back(value_comp); - - p_resulting_node = comparison; - -} - - -void GDParser::_generate_dict_pattern(PatternNode *p_dict_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings) +void GDParser::_generate_pattern(PatternNode *p_pattern, Node *p_node_to_match, Node *&p_resulting_node, Map &p_bindings) { - bool open_ended = false; - - if (p_dict_pattern->array.size() > 0) { - open_ended = true; - print_line("open dictionary"); - } - - // check length - - // typeof(value_to_match) == TYPE_DICTIONARY && value_to_match.size() >= length - // typeof(value_to_match) == TYPE_DICTIONARY && value_to_match.size() == length - - - { - - // typecheck - BuiltInFunctionNode *typeof_node = alloc_node(); - typeof_node->function = GDFunctions::TYPE_OF; - - OperatorNode *typeof_match_value = alloc_node(); - typeof_match_value->op = OperatorNode::OP_CALL; - typeof_match_value->arguments.push_back(typeof_node); - typeof_match_value->arguments.push_back(p_value_to_match); - - IdentifierNode *typeof_dictionary = alloc_node(); - typeof_dictionary->name = "TYPE_DICTIONARY"; - - OperatorNode *type_comp = alloc_node(); - type_comp->op = OperatorNode::OP_EQUAL; - type_comp->arguments.push_back(typeof_match_value); - type_comp->arguments.push_back(typeof_dictionary); - - - ConstantNode *length = alloc_node(); - length->value = Variant(open_ended ? p_dict_pattern->dictionary.size() - 1 : p_dict_pattern->dictionary.size()); - - - OperatorNode *call = alloc_node(); - call->op = OperatorNode::OP_CALL; - call->arguments.push_back(p_value_to_match); - - IdentifierNode *size = alloc_node(); - size->name = "size"; - call->arguments.push_back(size); - - OperatorNode *length_comparison = alloc_node(); - length_comparison->op = open_ended ? OperatorNode::OP_GREATER_EQUAL : OperatorNode::OP_EQUAL; - length_comparison->arguments.push_back(call); - length_comparison->arguments.push_back(length); - - OperatorNode *type_and_length_comparison = alloc_node(); - type_and_length_comparison->op = OperatorNode::OP_AND; - type_and_length_comparison->arguments.push_back(type_comp); - type_and_length_comparison->arguments.push_back(length_comparison); - - p_resulting_node = type_and_length_comparison; - } - - - - for (Map::Element *e = p_dict_pattern->dictionary.front(); e; e = e->next()) { - - Node *condition = NULL; - - // chech for has, then for pattern - - IdentifierNode *has = alloc_node(); - has->name = "has"; - - OperatorNode *has_call = alloc_node(); - has_call->op = OperatorNode::OP_CALL; - has_call->arguments.push_back(p_value_to_match); - has_call->arguments.push_back(has); - has_call->arguments.push_back(e->key()); + switch (p_pattern->pt_type) { + case PatternNode::PT_CONSTANT: { + // typecheck + BuiltInFunctionNode *typeof_node = alloc_node(); + typeof_node->function = GDFunctions::TYPE_OF; - if (e->value()) { + OperatorNode *typeof_match_value = alloc_node(); + typeof_match_value->op = OperatorNode::OP_CALL; + typeof_match_value->arguments.push_back(typeof_node); + typeof_match_value->arguments.push_back(p_node_to_match); - OperatorNode *indexed_value = alloc_node(); - indexed_value->op = OperatorNode::OP_INDEX; - indexed_value->arguments.push_back(p_value_to_match); - indexed_value->arguments.push_back(e->key()); + OperatorNode *typeof_pattern_value = alloc_node(); + typeof_pattern_value->op = OperatorNode::OP_CALL; + typeof_pattern_value->arguments.push_back(typeof_node); + typeof_pattern_value->arguments.push_back(p_pattern->constant); - _generate_pattern(e->value(), indexed_value, condition, p_bindings); + OperatorNode *type_comp = alloc_node(); + type_comp->op = OperatorNode::OP_EQUAL; + type_comp->arguments.push_back(typeof_match_value); + type_comp->arguments.push_back(typeof_pattern_value); - OperatorNode *has_and_pattern = alloc_node(); - has_and_pattern->op = OperatorNode::OP_AND; - has_and_pattern->arguments.push_back(has_call); - has_and_pattern->arguments.push_back(condition); - condition = has_and_pattern; - - } else { - condition = has_call; - } - - - - - OperatorNode *and_node = alloc_node(); - and_node->op = OperatorNode::OP_AND; - and_node->arguments.push_back(p_resulting_node); - and_node->arguments.push_back(condition); - - p_resulting_node = and_node; - } - -} - - -void GDParser::_generate_pattern(PatternNode *p_pattern, Node *p_node_to_match, Node *&p_resulting_node, Map &p_bindings) -{ - switch (p_pattern->pt_type) { - case PatternNode::PT_CONSTANT: { - _generate_constant_pattern(p_pattern, p_node_to_match, p_resulting_node); + // comare the actual values + OperatorNode *value_comp = alloc_node(); + value_comp->op = OperatorNode::OP_EQUAL; + value_comp->arguments.push_back(p_pattern->constant); + value_comp->arguments.push_back(p_node_to_match); + + + OperatorNode *comparison = alloc_node(); + comparison->op = OperatorNode::OP_AND; + comparison->arguments.push_back(type_comp); + comparison->arguments.push_back(value_comp); + + p_resulting_node = comparison; + } break; case PatternNode::PT_BIND: { - _generate_bind_pattern(p_pattern, p_node_to_match, p_bindings); + p_bindings[p_pattern->bind] = p_node_to_match; + // a bind always matches ConstantNode *true_value = alloc_node(); true_value->value = Variant(true); p_resulting_node = true_value; } break; case PatternNode::PT_ARRAY: { - _generate_array_pattern(p_pattern, p_node_to_match, p_resulting_node, p_bindings); + + bool open_ended = false; + + if (p_pattern->array.size() > 0) { + if (p_pattern->array[p_pattern->array.size() - 1]->pt_type == PatternNode::PT_IGNORE_REST) { + open_ended = true; + } + } + + // typeof(value_to_match) == TYPE_ARRAY && value_to_match.size() >= length + // typeof(value_to_match) == TYPE_ARRAY && value_to_match.size() == length + + { + // typecheck + BuiltInFunctionNode *typeof_node = alloc_node(); + typeof_node->function = GDFunctions::TYPE_OF; + + OperatorNode *typeof_match_value = alloc_node(); + typeof_match_value->op = OperatorNode::OP_CALL; + typeof_match_value->arguments.push_back(typeof_node); + typeof_match_value->arguments.push_back(p_node_to_match); + + IdentifierNode *typeof_array = alloc_node(); + typeof_array->name = "TYPE_ARRAY"; + + OperatorNode *type_comp = alloc_node(); + type_comp->op = OperatorNode::OP_EQUAL; + type_comp->arguments.push_back(typeof_match_value); + type_comp->arguments.push_back(typeof_array); + + + // size + ConstantNode *length = alloc_node(); + length->value = Variant(open_ended ? p_pattern->array.size() - 1 : p_pattern->array.size()); + + OperatorNode *call = alloc_node(); + call->op = OperatorNode::OP_CALL; + call->arguments.push_back(p_node_to_match); + + IdentifierNode *size = alloc_node(); + size->name = "size"; + call->arguments.push_back(size); + + OperatorNode *length_comparison = alloc_node(); + length_comparison->op = open_ended ? OperatorNode::OP_GREATER_EQUAL : OperatorNode::OP_EQUAL; + length_comparison->arguments.push_back(call); + length_comparison->arguments.push_back(length); + + OperatorNode *type_and_length_comparison = alloc_node(); + type_and_length_comparison->op = OperatorNode::OP_AND; + type_and_length_comparison->arguments.push_back(type_comp); + type_and_length_comparison->arguments.push_back(length_comparison); + + p_resulting_node = type_and_length_comparison; + } + + + + for (int i = 0; i < p_pattern->array.size(); i++) { + PatternNode *pattern = p_pattern->array[i]; + + Node *condition = NULL; + + ConstantNode *index = alloc_node(); + index->value = Variant(i); + + OperatorNode *indexed_value = alloc_node(); + indexed_value->op = OperatorNode::OP_INDEX; + indexed_value->arguments.push_back(p_node_to_match); + indexed_value->arguments.push_back(index); + + _generate_pattern(pattern, indexed_value, condition, p_bindings); + + // concatenate all the patterns with && + OperatorNode *and_node = alloc_node(); + and_node->op = OperatorNode::OP_AND; + and_node->arguments.push_back(p_resulting_node); + and_node->arguments.push_back(condition); + + p_resulting_node = and_node; + } + + } break; case PatternNode::PT_DICTIONARY: { - _generate_dict_pattern(p_pattern, p_node_to_match, p_resulting_node, p_bindings); + + bool open_ended = false; + + if (p_pattern->array.size() > 0) { + open_ended = true; + } + + // typeof(value_to_match) == TYPE_DICTIONARY && value_to_match.size() >= length + // typeof(value_to_match) == TYPE_DICTIONARY && value_to_match.size() == length + + + { + // typecheck + BuiltInFunctionNode *typeof_node = alloc_node(); + typeof_node->function = GDFunctions::TYPE_OF; + + OperatorNode *typeof_match_value = alloc_node(); + typeof_match_value->op = OperatorNode::OP_CALL; + typeof_match_value->arguments.push_back(typeof_node); + typeof_match_value->arguments.push_back(p_node_to_match); + + IdentifierNode *typeof_dictionary = alloc_node(); + typeof_dictionary->name = "TYPE_DICTIONARY"; + + OperatorNode *type_comp = alloc_node(); + type_comp->op = OperatorNode::OP_EQUAL; + type_comp->arguments.push_back(typeof_match_value); + type_comp->arguments.push_back(typeof_dictionary); + + // size + ConstantNode *length = alloc_node(); + length->value = Variant(open_ended ? p_pattern->dictionary.size() - 1 : p_pattern->dictionary.size()); + + OperatorNode *call = alloc_node(); + call->op = OperatorNode::OP_CALL; + call->arguments.push_back(p_node_to_match); + + IdentifierNode *size = alloc_node(); + size->name = "size"; + call->arguments.push_back(size); + + OperatorNode *length_comparison = alloc_node(); + length_comparison->op = open_ended ? OperatorNode::OP_GREATER_EQUAL : OperatorNode::OP_EQUAL; + length_comparison->arguments.push_back(call); + length_comparison->arguments.push_back(length); + + OperatorNode *type_and_length_comparison = alloc_node(); + type_and_length_comparison->op = OperatorNode::OP_AND; + type_and_length_comparison->arguments.push_back(type_comp); + type_and_length_comparison->arguments.push_back(length_comparison); + + p_resulting_node = type_and_length_comparison; + } + + + + for (Map::Element *e = p_pattern->dictionary.front(); e; e = e->next()) { + + Node *condition = NULL; + + // chech for has, then for pattern + + IdentifierNode *has = alloc_node(); + has->name = "has"; + + OperatorNode *has_call = alloc_node(); + has_call->op = OperatorNode::OP_CALL; + has_call->arguments.push_back(p_node_to_match); + has_call->arguments.push_back(has); + has_call->arguments.push_back(e->key()); + + + if (e->value()) { + + OperatorNode *indexed_value = alloc_node(); + indexed_value->op = OperatorNode::OP_INDEX; + indexed_value->arguments.push_back(p_node_to_match); + indexed_value->arguments.push_back(e->key()); + + _generate_pattern(e->value(), indexed_value, condition, p_bindings); + + OperatorNode *has_and_pattern = alloc_node(); + has_and_pattern->op = OperatorNode::OP_AND; + has_and_pattern->arguments.push_back(has_call); + has_and_pattern->arguments.push_back(condition); + + condition = has_and_pattern; + + } else { + condition = has_call; + } + + + + // concatenate all the patterns with && + OperatorNode *and_node = alloc_node(); + and_node->op = OperatorNode::OP_AND; + and_node->arguments.push_back(p_resulting_node); + and_node->arguments.push_back(condition); + + p_resulting_node = and_node; + } + } break; + case PatternNode::PT_IGNORE_REST: case PatternNode::PT_WILDCARD: { // simply generate a `true` ConstantNode *true_value = alloc_node(); @@ -2039,37 +2035,70 @@ void GDParser::_generate_pattern(PatternNode *p_pattern, Node *p_node_to_match, void GDParser::_transform_match_statment(BlockNode *p_block, MatchNode *p_match_statement) { - LocalVarNode *val_to_match = alloc_node(); - val_to_match->name = "#match_value"; // use a name that can't be referenced in GDscript - val_to_match->assign = p_match_statement->val_to_match; - - p_block->statements.push_back(val_to_match); - - IdentifierNode *id = alloc_node(); - id->name=val_to_match->name; - - OperatorNode *op = alloc_node(); - op->op=OperatorNode::OP_ASSIGN; - op->arguments.push_back(id); - op->arguments.push_back(val_to_match->assign); - p_block->statements.push_back(op); - - + id->name = "#match_value"; for (int i = 0; i < p_match_statement->branches.size(); i++) { + PatternBranchNode *branch = p_match_statement->branches[i]; - Map bindings; - Node *resulting_node; - _generate_pattern(branch->pattern, id, resulting_node, bindings); - // TEMP: if's for testing - ControlFlowNode *cf_if = alloc_node(); - cf_if->cf_type = ControlFlowNode::CF_IF; - cf_if->arguments.push_back(resulting_node); - cf_if->body = branch->body; + MatchNode::CompiledPatternBranch compiled_branch; + compiled_branch.compiled_pattern = NULL; - p_block->statements.push_back(cf_if); + Map binding; + + for (int j = 0; j < branch->patterns.size(); j++) { + PatternNode *pattern = branch->patterns[j]; + + Map bindings; + Node *resulting_node; + _generate_pattern(pattern, id, resulting_node, bindings); + + if (!binding.empty() && !bindings.empty()) { + _set_error("Multipatterns can't contain bindings"); + return; + } else { + binding = bindings; + } + + if (compiled_branch.compiled_pattern) { + OperatorNode *or_node = alloc_node(); + or_node->op = OperatorNode::OP_OR; + or_node->arguments.push_back(compiled_branch.compiled_pattern); + or_node->arguments.push_back(resulting_node); + + compiled_branch.compiled_pattern = or_node; + } else { + // single pattern | first one + compiled_branch.compiled_pattern = resulting_node; + } + + } + + + // prepare the body ...hehe + for (Map::Element *e = binding.front(); e; e = e->next()) { + LocalVarNode *local_var = alloc_node(); + local_var->name = e->key(); + local_var->assign = e->value(); + + + IdentifierNode *id = alloc_node(); + id->name = local_var->name; + + OperatorNode *op = alloc_node(); + op->op=OperatorNode::OP_ASSIGN; + op->arguments.push_back(id); + op->arguments.push_back(local_var->assign); + + branch->body->statements.push_front(op); + branch->body->statements.push_front(local_var); + } + + compiled_branch.body = branch->body; + + + p_match_statement->compiled_pattern_branches.push_back(compiled_branch); } } @@ -2509,8 +2538,6 @@ void GDParser::_parse_block(BlockNode *p_block,bool p_static) { _transform_match_statment(compiled_branches, match_node); - match_node->compiled_block = compiled_branches; - ControlFlowNode *match_cf_node = alloc_node(); match_cf_node->cf_type = ControlFlowNode::CF_MATCH; match_cf_node->match = match_node; diff --git a/modules/gdscript/gd_parser.h b/modules/gdscript/gd_parser.h index 6ee55b433a..d547593a3f 100644 --- a/modules/gdscript/gd_parser.h +++ b/modules/gdscript/gd_parser.h @@ -280,7 +280,7 @@ public: }; struct PatternBranchNode : public Node { - PatternNode *pattern; + Vector patterns; BlockNode *body; }; @@ -288,7 +288,12 @@ public: Node *val_to_match; Vector branches; - BlockNode *compiled_block; + struct CompiledPatternBranch { + Node *compiled_pattern; + BlockNode *body; + }; + + Vector compiled_pattern_branches; }; struct ControlFlowNode : public Node { @@ -487,19 +492,13 @@ private: Node* _parse_and_reduce_expression(Node *p_parent,bool p_static,bool p_reduce_const=false,bool p_allow_assign=false); - // TODO - void _parse_pattern_block(BlockNode *p_block, Vector &p_branches, bool p_static); + PatternNode *_parse_pattern(bool p_static); + void _parse_pattern_block(BlockNode *p_block, Vector &p_branches, bool p_static); void _transform_match_statment(BlockNode *p_block, MatchNode *p_match_statement); - void _generate_pattern(PatternNode *p_pattern, Node *p_node_to_match, Node *&p_resulting_node, Map &p_bindings); - void _generate_array_pattern(PatternNode *p_array_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings); - void _generate_bind_pattern(PatternNode *p_bind_pattern, Node *p_value_to_match, Map &p_bindings); - void _generate_constant_pattern(PatternNode *p_constant_pattern, Node *p_value_to_match, Node *&p_resulting_node); - void _generate_dict_pattern(PatternNode *p_dict_pattern, Node *p_value_to_match, Node *&p_resulting_node, Map &p_bindings); - void _parse_block(BlockNode *p_block,bool p_static); void _parse_extends(ClassNode *p_class); diff --git a/modules/gdscript/gd_script.cpp b/modules/gdscript/gd_script.cpp index 0ea10950df..4c2064a5ab 100644 --- a/modules/gdscript/gd_script.cpp +++ b/modules/gdscript/gd_script.cpp @@ -1894,6 +1894,7 @@ void GDScriptLanguage::get_reserved_words(List *p_words) const { "for", "pass", "return", + "match", "while", "remote", "sync", -- cgit v1.2.3