Merge #1219

1219: Add `Optional<T>` type r=CohenArthur a=CohenArthur

This adds a tagged union to try and simulate a sum type. This is safer and more ergonomic
 than one of the two alternatives we're currently using in the compiler:
 
 1. Storing a raw pointer, which can be `nullptr` or valid
 
 This is wildly unsafe, and usable in conjunction with local references, stack
 variables, or pointers managed elsewhere, which can cause crashes, hard to
 debug issues or undefined behavior. Likewise, if you do not check for the
 pointer's validity, this will cause a crash.
 
 2. Storing an extra boolean alongside the object
 
 This causes implementors to use a "dummy object": Either an empty version or
 an error version. But what happens if what you really wanted to store was
 the empty or error version? You can also easily incorporate logic bugs if you
 forget to check for the associated boolean.
 
 The `Optional<T>` type has the same "ergonomic" cost: You need to check
 whether your option is valid or not. However, the main advantage is that it
 is more restrictive: You can only acess the member it contains "safely".
 It is similar to storing a value + an associated boolean, but has the
 advantage of making up only one member in your class.
 You also benefit from some helper methods such as `map()`.
 You also get helper functions and operator overloading to "seamlessly"
 replace raw pointer alternatives.
 
  ```c++
 MyType *raw_pointer = something_that_can_fail();
 if (raw_pointer)
     raw_pointer->method();
  // or
  Optional<MyType> opt = something_that_can_fail2();
  if (opt)
      opt->method();
 
  // equivalent to
 
  if (opt.is_some())
      opt.get().method();
  ```
  
  This will be very useful for parent modules when resolving `super` paths :)

Co-authored-by: Arthur Cohen <arthur.cohen@embecosm.com>

5 files changed, 266 insertions, 2 deletions

diff --git a/gcc/rust/Make-lang.in b/gcc/rust/Make-lang.in
index aa125a1..738cfdf 100644
--- a/gcc/rust/Make-lang.in
+++ b/gcc/rust/Make-lang.in
@@ -291,7 +291,8 @@ RUST_INCLUDES = -I $(srcdir)/rust \
 	-I $(srcdir)/rust/util \
 	-I $(srcdir)/rust/typecheck \
 	-I $(srcdir)/rust/privacy \
-	-I $(srcdir)/rust/lint
+	-I $(srcdir)/rust/lint \
+	-I $(srcdir)/rust/util
 
 # add files that require cross-folder includes - currently rust-lang.o, rust-lex.o
 CFLAGS-rust/rust-lang.o += $(RUST_INCLUDES)
diff --git a/gcc/rust/parse/rust-parse-impl.h b/gcc/rust/parse/rust-parse-impl.h
index e76bdd8..0641e22 100644
--- a/gcc/rust/parse/rust-parse-impl.h
+++ b/gcc/rust/parse/rust-parse-impl.h
@@ -22,7 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 
 #define INCLUDE_ALGORITHM
 #include "rust-diagnostics.h"
-#include "util/rust-make-unique.h"
+#include "rust-make-unique.h"
 
 namespace Rust {
 // Left binding powers of operations.
diff --git a/gcc/rust/rust-lang.cc b/gcc/rust/rust-lang.cc
index 73f9839..dd8c608 100644
--- a/gcc/rust/rust-lang.cc
+++ b/gcc/rust/rust-lang.cc
@@ -37,6 +37,7 @@
 #include "rust-cfg-parser.h"
 #include "rust-privacy-ctx.h"
 #include "rust-ast-resolve-item.h"
+#include "rust-optional.h"
 
 #include <mpfr.h>
 // note: header files must be in this order or else forward declarations don't
@@ -461,6 +462,7 @@ run_rust_tests ()
   rust_privacy_ctx_test ();
   rust_crate_name_validation_test ();
   rust_simple_path_resolve_test ();
+  rust_optional_test ();
 }
 } // namespace selftest
 
diff --git a/gcc/rust/util/rust-make-unique.h b/gcc/rust/util/rust-make-unique.h
index 5f098d2..f33f912 100644
--- a/gcc/rust/util/rust-make-unique.h
+++ b/gcc/rust/util/rust-make-unique.h
@@ -1,6 +1,26 @@
+// Copyright (C) 2020-2022 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_MAKE_UNIQUE_H
 #define RUST_MAKE_UNIQUE_H
 
+#include <memory>
+
 namespace Rust {
 
 template <typename T, typename... Ts>
diff --git a/gcc/rust/util/rust-optional.h b/gcc/rust/util/rust-optional.h
new file mode 100644
index 0000000..c1b547a
--- /dev/null
+++ b/gcc/rust/util/rust-optional.h
@@ -0,0 +1,241 @@
+// Copyright (C) 2020-2022 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_OPTIONAL_H
+#define RUST_OPTIONAL_H
+
+#include "config.h"
+#include "rust-system.h"
+
+#include "selftest.h"
+
+namespace Rust {
+
+/**
+ * Tagged union to try and simulate a sum type. This is safer and more ergonomic
+ * than one of the two alternatives we're currently using in the compiler:
+ *
+ * 1. Storing a raw pointer, which can be `nullptr` or valid
+ *
+ * This is wildly unsafe, and usable in conjunction with local references, stack
+ * variables, or pointers managed elsewhere, which can cause crashes, hard to
+ * debug issues or undefined behavior. Likewise, if you do not check for the
+ * pointer's validity, this will cause a crash.
+ *
+ * 2. Storing an extra boolean alongside the object
+ *
+ * This causes implementors to use a "dummy object": Either an empty version or
+ * an error version. But what happens if what you really wanted to store was
+ * the empty or error version? You can also easily incorporate logic bugs if you
+ * forget to check for the associated boolean.
+ *
+ * The `Optional<T>` type has the same "ergonomic" cost: You need to check
+ * whether your option is valid or not. However, the main advantage is that it
+ * is more restrictive: You can only acess the member it contains "safely".
+ * It is similar to storing a value + an associated boolean, but has the
+ * advantage of making up only one member in your class.
+ * You also benefit from some helper methods such as `map()`.
+ *
+ * You also get helper functions and operator overloading to "seamlessly"
+ * replace raw pointer alternatives.
+ *
+ * ```c++
+ * MyType *raw_pointer = something_that_can_fail();
+ * if (raw_pointer)
+ *     raw_pointer->method();
+ *
+ * // or
+ *
+ * Optional<MyType> opt = something_that_can_fail2();
+ * if (opt)
+ *     opt->method();
+ *
+ * // equivalent to
+ *
+ * if (opt.is_some())
+ *     opt.get().method();
+ * ```
+ */
+template <typename T> class Optional
+{
+private:
+  struct Empty
+  {
+  };
+
+  enum Kind
+  {
+    Some,
+    None
+  } kind;
+
+  union Content
+  {
+    Empty empty;
+    T value;
+
+    Content () = default;
+  } content;
+
+  Optional<T> (Kind kind, Content content) : kind (kind), content (content) {}
+
+public:
+  Optional (const Optional &other) = default;
+  Optional (Optional &&other) = default;
+
+  static Optional<T> some (T value)
+  {
+    Content content;
+    content.value = value;
+
+    return Optional (Kind::Some, content);
+  }
+
+  static Optional<T> none ()
+  {
+    Content content;
+    content.empty = Empty ();
+
+    return Optional (Kind::None, content);
+  }
+
+  bool is_some () const { return kind == Kind::Some; }
+  bool is_none () const { return !is_some (); }
+
+  /**
+   * Enable boolean-like comparisons.
+   */
+  operator bool () { return is_some (); }
+
+  /**
+   * Enables dereferencing to access the contained value
+   */
+  T &operator* () { return get (); }
+  const T &operator* () const { return get (); }
+  T *operator-> () { return &get (); }
+  const T *operator-> () const { return &get (); }
+
+  const T &get () const
+  {
+    rust_assert (is_some ());
+
+    return content.value;
+  }
+
+  T &get ()
+  {
+    rust_assert (is_some ());
+
+    return content.value;
+  }
+
+  T take ()
+  {
+    rust_assert (is_some ());
+
+    auto to_return = std::move (content.value);
+
+    content.empty = Empty ();
+    kind = Kind::None;
+
+    return to_return;
+  }
+
+  template <typename U> Optional<U> map (std::function<U (T)> functor)
+  {
+    if (is_none ())
+      return Optional::none ();
+
+    auto value = functor (take ());
+
+    return Optional::some (value);
+  }
+};
+
+} // namespace Rust
+
+#ifdef CHECKING_P
+
+static void
+rust_optional_create ()
+{
+  auto opt = Rust::Optional<int>::some (15);
+
+  ASSERT_TRUE (opt.is_some ());
+  ASSERT_EQ (opt.get (), 15);
+
+  Rust::Optional<int> const_opt = Rust::Optional<int>::some (15);
+  const int &value = const_opt.get ();
+
+  ASSERT_EQ (value, 15);
+}
+
+static void
+rust_optional_operators ()
+{
+  auto opt = Rust::Optional<int>::some (15);
+
+  // as bool
+  ASSERT_TRUE (opt);
+
+  // deref
+  ASSERT_EQ (*opt, 15);
+
+  class Methodable
+  {
+  public:
+    int method () { return 15; }
+  };
+
+  auto m_opt = Rust::Optional<Methodable>::some (Methodable ());
+  ASSERT_EQ (m_opt->method (), 15);
+}
+
+static void
+rust_optional_take ()
+{
+  auto opt = Rust::Optional<int>::some (15);
+  auto value = opt.take ();
+
+  ASSERT_EQ (value, 15);
+  ASSERT_TRUE (opt.is_none ());
+}
+
+static void
+rust_optional_map ()
+{
+  auto opt = Rust::Optional<int>::some (15);
+  auto twice = opt.map<int> ([] (int value) { return value * 2; });
+
+  ASSERT_FALSE (opt);
+  ASSERT_TRUE (twice);
+  ASSERT_EQ (*twice, 30);
+}
+
+static void
+rust_optional_test ()
+{
+  rust_optional_create ();
+  rust_optional_operators ();
+  rust_optional_take ();
+  rust_optional_map ();
+}
+
+#endif // !CHECKING_P
+
+#endif // !RUST_OPTIONAL_H