scope: Add a scope stack for identifier resolutions

Before accepting an identifier, the parser should check if that
identifier will be available. With this implementation it will be
possible. Take the following code example:

  main(): i32 {
    return my_exit_code;
  }

The parser must return an error informing that *my_exit_code* is not
defined in the example above. The ast scope is a support module for
parser and ast, simplifying identifier resolution.

Once a curly bracket ({) is open the *scope_enter()* is called and when
it is closed (}) we pop the entire stack with *scope_leave()*.

Signed-off-by: Carlos Maniero <carlosmaniero@gmail.com>

4 files changed, 240 insertions, 0 deletions

diff --git a/src/scope.c b/src/scope.c
new file mode 100644
index 0000000..de1295e
--- /dev/null
+++ b/src/scope.c
@@ -0,0 +1,123 @@
+/*
+ * Copyright (C) 2023 Carlos Maniero
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#include "scope.h"
+#include <errno.h>
+#include <stdio.h>
+#include <string.h>
+
+static scope_item_t *
+scope_item_new()
+{
+  scope_item_t *item = malloc(sizeof(scope_item_t));
+  if (item == NULL) {
+    fprintf(stderr, "failed to create scope item: %s\n", strerror(errno));
+    exit(EXIT_FAILURE);
+  }
+  return item;
+}
+
+static void
+scope_item_destroy(scope_item_t *item)
+{
+  free(item);
+}
+
+scope_t *
+scope_new()
+{
+  scope_t *scope = malloc(sizeof(scope_t));
+
+  if (scope == NULL) {
+    fprintf(stderr, "failed to create scope: %s\n", strerror(errno));
+    exit(EXIT_FAILURE);
+  }
+
+  scope->stack = vector_new();
+  scope_enter(scope);
+  return scope;
+}
+
+void
+scope_destroy(scope_t *scope)
+{
+  if (scope->stack->size) {
+    fprintf(stderr,
+            "Stack not cleaned before destroying. This may lead to memory leaks.\n"
+            "Please make sure to call the leave function before destroying it.");
+  }
+
+  for (size_t i = 0; i < scope->stack->size; i++) {
+    vector_destroy(vector_at(scope->stack, i));
+  }
+
+  vector_destroy(scope->stack);
+  free(scope);
+}
+
+void
+scope_enter(scope_t *scope)
+{
+  vector_push_back(scope->stack, vector_new());
+}
+
+void
+scope_leave(scope_t *scope)
+{
+  // FIXME: create a stack data structure to simplify this logic
+  vector_t *new_stack = vector_new();
+
+  for (size_t i = 0; i < scope->stack->size - 1; i++) {
+    vector_push_back(new_stack, vector_at(scope->stack, i));
+  }
+
+  vector_t *current_level = vector_at(scope->stack, scope->stack->size - 1);
+
+  for (size_t i = 0; i < current_level->size; i++) {
+    scope_item_destroy(vector_at(current_level, i));
+  }
+
+  vector_destroy(current_level);
+  vector_t *old_stack = scope->stack;
+  vector_destroy(old_stack);
+  scope->stack = new_stack;
+}
+
+ast_node_t *
+scope_get(scope_t *scope, ast_identifier_t *identifier)
+{
+  for (size_t i = scope->stack->size; i > 0; i--) {
+    vector_t *current_level = vector_at(scope->stack, i - 1);
+
+    for (size_t j = 0; j < current_level->size; j++) {
+      scope_item_t *item = vector_at(current_level, j);
+
+      if (string_view_eq(identifier->name, item->identifier->name)) {
+        return item->node;
+      }
+    }
+  }
+
+  return NULL;
+}
+void
+scope_push(scope_t *scope, ast_identifier_t *identifier, ast_node_t *node)
+{
+  vector_t *current_level = vector_at(scope->stack, scope->stack->size - 1);
+  scope_item_t *item = scope_item_new();
+  *item = (scope_item_t){ .identifier = identifier, .node = node };
+  vector_push_back(current_level, item);
+}
diff --git a/src/scope.h b/src/scope.h
new file mode 100644
index 0000000..bce3567
--- /dev/null
+++ b/src/scope.h
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2023 Carlos Maniero
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#include "ast.h"
+#include "string_view.h"
+#include "vector.h"
+
+typedef struct scope_t
+{
+  vector_t *stack;
+} scope_t;
+
+typedef struct scope_item_t
+{
+  ast_identifier_t *identifier;
+  ast_node_t *node;
+} scope_item_t;
+
+scope_t *
+scope_new();
+
+void
+scope_destroy(scope_t *scope);
+
+void
+scope_enter(scope_t *scope);
+void
+scope_leave(scope_t *scope);
+
+ast_node_t *
+scope_get(scope_t *scope, ast_identifier_t *identifier);
+void
+scope_push(scope_t *scope, ast_identifier_t *identifier, ast_node_t *node);
diff --git a/test/Makefile b/test/Makefile
index 717b430..6d8bfb7 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -30,5 +30,8 @@ lexer_test: munit.o ../build/string_view.o ../build/lexer.o lexer_test.o
 parser_test: munit.o ../build/string_view.o ../build/vector.o ../build/lexer.o ../build/ast.o ../build/parser.o parser_test.o
 	$(CC) $? $(CFLAGS) -o $@
 
+scope_test: munit.o ../build/string_view.o ../build/vector.o ../build/ast.o ../build/scope.o scope_test.o
+	$(CC) $? $(CFLAGS) -o $@
+
 integration_test: munit.o integration_test.o
 	$(CC) $? $(CFLAGS) -o $@
diff --git a/test/scope_test.c b/test/scope_test.c
new file mode 100644
index 0000000..b8ee30e
--- /dev/null
+++ b/test/scope_test.c
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2023 Carlos Maniero
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#define MUNIT_ENABLE_ASSERT_ALIASES
+#include "ast.h"
+#include "munit.h"
+#include "scope.h"
+
+static MunitResult
+test_scope(const MunitParameter params[], void *user_data_or_fixture)
+{
+  ast_node_t first_id_node_1;
+  ast_node_t first_id_node_2;
+  ast_node_t second_id_node;
+
+  ast_identifier_t first_id = { .name = string_view_from_str("first") };
+  ast_identifier_t second_id = { .name = string_view_from_str("second") };
+
+  scope_t *scope = scope_new();
+
+  assert_null(scope_get(scope, &first_id));
+  assert_null(scope_get(scope, &second_id));
+
+  scope_push(scope, &first_id, &first_id_node_1);
+  scope_push(scope, &second_id, &second_id_node);
+
+  assert_ptr_equal((void *)scope_get(scope, &first_id), (void *)&first_id_node_1);
+  assert_ptr_equal((void *)scope_get(scope, &second_id), (void *)&second_id_node);
+
+  scope_enter(scope);
+
+  scope_push(scope, &first_id, &first_id_node_2);
+  assert_ptr_equal((void *)scope_get(scope, &first_id), (void *)&first_id_node_2);
+  assert_ptr_equal((void *)scope_get(scope, &second_id), (void *)&second_id_node);
+
+  scope_leave(scope);
+
+  assert_ptr_equal((void *)scope_get(scope, &first_id), (void *)&first_id_node_1);
+
+  scope_destroy(scope);
+
+  return MUNIT_OK;
+}
+
+static MunitTest tests[] = { { "/test_scope", test_scope, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+                             { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL } };
+
+static const MunitSuite suite = { "/scope_test", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE };
+
+int
+main(int argc, char *argv[])
+{
+  return munit_suite_main(&suite, NULL, argc, argv);
+  return EXIT_SUCCESS;
+}