nr2.0: Add basic Rib class

This class adds a basic Rib class for the new name resolution algorithm.
It uses `optional` and `expected` return types in order to try and
improve error handling in these new passes.

gcc/rust/ChangeLog:

	* Make-lang.in: Add `rust-rib.cc` object.
	* resolve/rust-rib.cc: New file.
	* resolve/rust-rib.h: New file.

Co-authored-by: Matthew Jasper <mjjasper1@gmail.com>

3 files changed, 206 insertions, 0 deletions

diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index 5d90863..608b431 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -109,6 +109,7 @@ GRS_OBJS = \
     rust/rust-ast-lower-expr.o \
     rust/rust-ast-lower-type.o \
 	rust/rust-ast-lower-stmt.o \
+	rust/rust-rib.o \
     rust/rust-early-name-resolver.o \
     rust/rust-name-resolver.o \
     rust/rust-ast-resolve.o \
diff --git a/gcc/rust/resolve/rust-rib.cc b/gcc/rust/resolve/rust-rib.cc
new file mode 100644
index 0000000..2cc9f3e
--- /dev/null
+++ b/gcc/rust/resolve/rust-rib.cc
@@ -0,0 +1,70 @@
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include "rust-rib.h"
+
+namespace Rust {
+namespace Resolver2_0 {
+
+DuplicateNameError::DuplicateNameError (std::string name, NodeId existing)
+  : name (name), existing (existing)
+{}
+
+Rib::Rib (Kind kind) : kind (kind) {}
+
+Rib::Rib (Kind kind, std::string identifier, NodeId id)
+  : Rib (kind, {{identifier, id}})
+{}
+
+Rib::Rib (Kind kind, std::unordered_map<std::string, NodeId> values)
+  : kind (kind), values (std::move (values))
+{}
+
+tl::expected<NodeId, DuplicateNameError>
+Rib::insert (std::string name, NodeId id)
+{
+  auto res = values.insert ({name, id});
+  auto inserted_id = res.first->second;
+
+  // if we couldn't insert, the element already exists - exit with an error
+  if (!res.second)
+    return tl::make_unexpected (DuplicateNameError (name, inserted_id));
+
+  // return the NodeId
+  return inserted_id;
+}
+
+tl::optional<NodeId>
+Rib::get (const std::string &name)
+{
+  auto it = values.find (name);
+
+  if (it == values.end ())
+    return {};
+
+  return it->second;
+}
+
+const std::unordered_map<std::string, NodeId> &
+Rib::get_values () const
+{
+  return values;
+}
+
+} // namespace Resolver2_0
+} // namespace Rust
diff --git a/gcc/rust/resolve/rust-rib.h b/gcc/rust/resolve/rust-rib.h
new file mode 100644
index 0000000..ea69cc7
--- /dev/null
+++ b/gcc/rust/resolve/rust-rib.h
@@ -0,0 +1,135 @@
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_RIB_H
+#define RUST_RIB_H
+
+#include "rust-system.h"
+#include "rust-ast.h"
+#include "optional.h"
+#include "expected.h"
+
+namespace Rust {
+namespace Resolver2_0 {
+
+/**
+ * All namespaces that Rust's name resolution needs to handle
+ */
+// TODO: Move to `rust-forever-stack.h`?
+enum class Namespace
+{
+  Values,
+  Types,
+  Labels,
+  Macros,
+  // TODO: Which namespaces are we missing?
+};
+
+/**
+ * Error returned by `Rib::insert` when the key was already present in the Rib's
+ * map. The class contains the previously-inserted NodeId as well as the name of
+ * the node.
+ */
+struct DuplicateNameError
+{
+  // TODO: We might need multiple kinds of errors later down the line
+  DuplicateNameError (std::string name, NodeId existing);
+
+  std::string name;
+  NodeId existing;
+};
+
+/**
+ * A rib is a container of nodes, either declaration or usages, as well as the
+ * identifier each node uses. They are used to delimit lexical scopes, and have
+ * an impact on name resolution - they restrict certain name accesses and serve
+ * as boundaries between scopes.
+
+ * For example, if we are resolving the following *variable* use:
+ *
+ * ```rust
+ * fn outer() {
+ *     let a = 15; // decl
+ *     fn inner() -> i32 {
+ *         a // use
+ *     }
+ * }
+ * ```
+ *
+ * The `Function` rib we will have pushed will restrict the access to `outer`'s
+ * `a` declaration: Variable uses cannot cross function boundaries. On the other
+ * hand, if we were resolving a type usage, this would be perfectly allowed.
+ */
+class Rib
+{
+public:
+  enum class Kind
+  {
+    Normal,
+    Module,
+    Function,
+    ConstantItem, // -> this variant has a boolean
+    TraitOrImpl,
+    /* Any item other than a Module, Function, Constant, Trait or Impl block */
+    Item,
+    Closure,
+    MacroDefinition,
+    /* Ban the use of forward-declared generic parameters in defaults */
+    ForwardTypeParamBan,
+    /* Const generic, as in the following example: fn foo<T, const X: T>() {} */
+    ConstParamType,
+  };
+
+  Rib (Kind kind);
+  Rib (Kind kind, std::string identifier, NodeId id);
+  Rib (Kind kind, std::unordered_map<std::string, NodeId> values);
+
+  // TODO: What's the correctbehavior if the key already exists? What if a decl
+  // and use are in the same rib? Is that possible? Okay based on RibKind?
+
+  /**
+   * Insert a new node in the rib
+   *
+   * @param name The name associated with the AST node
+   * @param id Its NodeId
+   *
+   * @return `DuplicateNameError` if the node is already present in the rib. The
+   *         `DuplicateNameError` class contains the NodeId of the existing
+   * node. Returns the new NodeId on success.
+   */
+  tl::expected<NodeId, DuplicateNameError> insert (std::string name, NodeId id);
+
+  /**
+   * Access an inserted NodeId.
+   *
+   * @return tl::nullopt if the key does not exist, the NodeId otherwise
+   */
+  tl::optional<NodeId> get (const std::string &name);
+
+  /* View all the values stored in the rib */
+  const std::unordered_map<std::string, NodeId> &get_values () const;
+
+private:
+  Kind kind;
+  std::unordered_map<std::string, NodeId> values;
+};
+
+} // namespace Resolver2_0
+} // namespace Rust
+
+#endif // !RUST_RIB_H