ast: Resolver: Flatten use declarations to paths

In order to resolve `SimplePath`s, we have to expand all paths present
in a `UseDeclaration` and resolve them. For example, we want to resolve
two paths with the following statement `use foo::bar::{baz, bul}`:
`foo::bar::baz` and `foo::bar::bul`.
This also removes the prelude inclusion (`use std::prelude::v1::*`)
since we cannot resolve it (yet!)

8 files changed, 403 insertions, 20 deletions

diff --git a/gcc/rust/ast/rust-ast.h b/gcc/rust/ast/rust-ast.h
index fb8982a..69ad6eb 100644
--- a/gcc/rust/ast/rust-ast.h
+++ b/gcc/rust/ast/rust-ast.h
@@ -410,6 +410,8 @@ public:
   {
     return segments;
   }
+
+  std::vector<SimplePathSegment> &get_segments () { return segments; }
 };
 
 // path-to-string inverse comparison operator
diff --git a/gcc/rust/ast/rust-item.h b/gcc/rust/ast/rust-item.h
index 9dc61a8..4bed5af 100644
--- a/gcc/rust/ast/rust-item.h
+++ b/gcc/rust/ast/rust-item.h
@@ -1179,8 +1179,29 @@ class UseTree
   Location locus;
 
 public:
+  enum Kind
+  {
+    Glob,
+    Rebind,
+    List,
+  };
+
   virtual ~UseTree () {}
 
+  // Overload assignment operator to clone
+  UseTree &operator= (UseTree const &other)
+  {
+    locus = other.locus;
+
+    return *this;
+  }
+
+  UseTree (const UseTree &other) = default;
+
+  // move constructors
+  UseTree (UseTree &&other) = default;
+  UseTree &operator= (UseTree &&other) = default;
+
   // Unique pointer custom clone function
   std::unique_ptr<UseTree> clone_use_tree () const
   {
@@ -1188,6 +1209,7 @@ public:
   }
 
   virtual std::string as_string () const = 0;
+  virtual Kind get_kind () const = 0;
 
   Location get_locus () const { return locus; }
 
@@ -1237,6 +1259,14 @@ public:
 
   void accept_vis (ASTVisitor &vis) override;
 
+  Kind get_kind () const override { return Glob; }
+
+  SimplePath get_path () const
+  {
+    rust_assert (has_path ());
+    return path;
+  }
+
   /* TODO: find way to ensure only PATH_PREFIXED glob_type has path - factory
    * methods? */
 protected:
@@ -1318,6 +1348,18 @@ public:
 
   void accept_vis (ASTVisitor &vis) override;
 
+  Kind get_kind () const override { return List; }
+  SimplePath get_path () const
+  {
+    rust_assert (has_path ());
+    return path;
+  }
+
+  const std::vector<std::unique_ptr<UseTree>> &get_trees () const
+  {
+    return trees;
+  }
+
   // TODO: find way to ensure only PATH_PREFIXED path_type has path - factory
   // methods?
 protected:
@@ -1363,6 +1405,20 @@ public:
 
   void accept_vis (ASTVisitor &vis) override;
 
+  Kind get_kind () const override { return Rebind; }
+
+  SimplePath get_path () const
+  {
+    rust_assert (has_path ());
+    return path;
+  }
+
+  const Identifier &get_identifier () const
+  {
+    rust_assert (has_identifier ());
+    return identifier;
+  }
+
   // TODO: find way to ensure only PATH_PREFIXED path_type has path - factory
   // methods?
 protected:
@@ -1420,6 +1476,7 @@ public:
   UseDeclaration &operator= (UseDeclaration &&other) = default;
 
   Location get_locus () const override final { return locus; }
+  const std::unique_ptr<UseTree> &get_tree () const { return use_tree; }
 
   void accept_vis (ASTVisitor &vis) override;
 
diff --git a/gcc/rust/resolve/rust-ast-resolve-item.cc b/gcc/rust/resolve/rust-ast-resolve-item.cc
index 2c383c9..93eca1b 100644
--- a/gcc/rust/resolve/rust-ast-resolve-item.cc
+++ b/gcc/rust/resolve/rust-ast-resolve-item.cc
@@ -17,6 +17,8 @@
 // <http://www.gnu.org/licenses/>.
 
 #include "rust-ast-resolve-item.h"
+#include "rust-ast-resolve-path.h"
+#include "selftest.h"
 
 namespace Rust {
 namespace Resolver {
@@ -133,7 +135,7 @@ ResolveTraitItems::visit (AST::TraitItemMethod &func)
 				       self_param.get_is_mut (),
 				       std::unique_ptr<AST::Pattern> (nullptr));
 
-  std::vector<std::unique_ptr<AST::TypePathSegment> > segments;
+  std::vector<std::unique_ptr<AST::TypePathSegment>> segments;
   segments.push_back (std::unique_ptr<AST::TypePathSegment> (
     new AST::TypePathSegment ("Self", false, self_param.get_locus ())));
 
@@ -694,7 +696,7 @@ ResolveItem::visit (AST::Method &method)
 				       self_param.get_is_mut (),
 				       std::unique_ptr<AST::Pattern> (nullptr));
 
-  std::vector<std::unique_ptr<AST::TypePathSegment> > segments;
+  std::vector<std::unique_ptr<AST::TypePathSegment>> segments;
   segments.push_back (std::unique_ptr<AST::TypePathSegment> (
     new AST::TypePathSegment ("Self", false, self_param.get_locus ())));
 
@@ -902,6 +904,133 @@ ResolveItem::visit (AST::ExternBlock &extern_block)
     }
 }
 
+static void
+flatten_glob (const AST::UseTreeGlob &glob,
+	      std::vector<AST::SimplePath> &paths);
+static void
+flatten_rebind (const AST::UseTreeRebind &glob,
+		std::vector<AST::SimplePath> &paths);
+static void
+flatten_list (const AST::UseTreeList &glob,
+	      std::vector<AST::SimplePath> &paths);
+
+static void
+flatten (const AST::UseTree *tree, std::vector<AST::SimplePath> &paths)
+{
+  switch (tree->get_kind ())
+    {
+      case AST::UseTree::Glob: {
+	auto glob = static_cast<const AST::UseTreeGlob *> (tree);
+	flatten_glob (*glob, paths);
+	break;
+      }
+      case AST::UseTree::Rebind: {
+	auto rebind = static_cast<const AST::UseTreeRebind *> (tree);
+	flatten_rebind (*rebind, paths);
+	break;
+      }
+      case AST::UseTree::List: {
+	auto list = static_cast<const AST::UseTreeList *> (tree);
+	flatten_list (*list, paths);
+	break;
+      }
+      break;
+    }
+}
+
+static void
+flatten_glob (const AST::UseTreeGlob &glob, std::vector<AST::SimplePath> &paths)
+{
+  if (glob.has_path ())
+    paths.emplace_back (glob.get_path ());
+}
+
+static void
+flatten_rebind (const AST::UseTreeRebind &rebind,
+		std::vector<AST::SimplePath> &paths)
+{
+  auto path = rebind.get_path ();
+  if (rebind.has_path ())
+    paths.emplace_back (path);
+
+  // FIXME: Do we want to emplace the rebind here as well?
+  if (rebind.has_identifier ())
+    {
+      auto rebind_path = path;
+      auto new_seg = rebind.get_identifier ();
+
+      // Add the identifier as a new path
+      rebind_path.get_segments ().back ()
+	= AST::SimplePathSegment (new_seg, Location ());
+
+      paths.emplace_back (rebind_path);
+    }
+}
+
+static void
+flatten_list (const AST::UseTreeList &list, std::vector<AST::SimplePath> &paths)
+{
+  auto prefix = AST::SimplePath::create_empty ();
+  if (list.has_path ())
+    prefix = list.get_path ();
+
+  for (const auto &tree : list.get_trees ())
+    {
+      auto sub_paths = std::vector<AST::SimplePath> ();
+      flatten (tree.get (), sub_paths);
+
+      for (auto &sub_path : sub_paths)
+	{
+	  auto new_path = prefix;
+	  std::copy (sub_path.get_segments ().begin (),
+		     sub_path.get_segments ().end (),
+		     std::back_inserter (new_path.get_segments ()));
+
+	  paths.emplace_back (new_path);
+	}
+    }
+}
+
+/**
+ * Flatten a UseDeclaration's UseTree into multiple simple paths to resolve.
+ *
+ * Given the following use declarations:
+ * ```
+ * use some::path::to_resolve; #1
+ * use some::path::to_glob::*; #2
+ * use some::path::{one, two}; #2
+ * ```
+ *
+ * In the first case, we simply want to return a vector with a single
+ * SimplePath:
+ * [some::path::to_resolve]
+ *
+ * In the second case, we want to resolve the glob's "origin path":
+ * [some::path::to_glob]
+ *
+ * Finally in the third case, we want to create two SimplePaths to resolve:
+ * [some::path::one, some::path::two]
+ */
+static std::vector<AST::SimplePath>
+flatten_use_dec_to_paths (const AST::UseDeclaration &use_item)
+{
+  auto paths = std::vector<AST::SimplePath> ();
+
+  const auto &tree = use_item.get_tree ();
+  flatten (tree.get (), paths);
+
+  return paths;
+}
+
+void
+ResolveItem::visit (AST::UseDeclaration &use_item)
+{
+  auto to_resolve = flatten_use_dec_to_paths (use_item);
+
+  for (auto &path : to_resolve)
+    ResolvePath::go (&path, parent);
+}
+
 void
 ResolveImplItems::go (AST::InherentImplItem *item, const CanonicalPath &prefix,
 		      const CanonicalPath &canonical_prefix)
@@ -991,3 +1120,167 @@ ResolveExternItem::visit (AST::ExternalStaticItem &item)
 
 } // namespace Resolver
 } // namespace Rust
+
+#if CHECKING_P
+
+namespace selftest {
+
+static void
+rust_flatten_nested_glob (void)
+{
+  auto foo = Rust::AST::SimplePathSegment ("foo", Location ());
+  auto bar = Rust::AST::SimplePathSegment ("bar", Location ());
+  auto foobar = Rust::AST::SimplePath ({foo, bar});
+
+  auto glob
+    = Rust::AST::UseTreeGlob (Rust::AST::UseTreeGlob::PathType::PATH_PREFIXED,
+			      foobar, Location ());
+
+  auto paths = std::vector<Rust::AST::SimplePath> ();
+  Rust::Resolver::flatten_glob (glob, paths);
+
+  ASSERT_TRUE (!paths.empty ());
+  ASSERT_EQ (paths.size (), 1);
+  ASSERT_EQ (paths[0].get_segments ()[0].as_string (), "foo");
+  ASSERT_EQ (paths[0].get_segments ()[1].as_string (), "bar");
+}
+
+static void
+rust_flatten_glob (void)
+{
+  auto frob = Rust::AST::SimplePath::from_str ("frobulator", Location ());
+
+  auto glob
+    = Rust::AST::UseTreeGlob (Rust::AST::UseTreeGlob::PathType::PATH_PREFIXED,
+			      frob, Location ());
+
+  auto paths = std::vector<Rust::AST::SimplePath> ();
+  Rust::Resolver::flatten_glob (glob, paths);
+
+  ASSERT_TRUE (!paths.empty ());
+  ASSERT_EQ (paths.size (), 1);
+  ASSERT_EQ (paths[0], "frobulator");
+}
+
+static void
+rust_flatten_rebind_none (void)
+{
+  auto foo = Rust::AST::SimplePathSegment ("foo", Location ());
+  auto bar = Rust::AST::SimplePathSegment ("bar", Location ());
+  auto foobar = Rust::AST::SimplePath ({foo, bar});
+
+  auto rebind = Rust::AST::UseTreeRebind (Rust::AST::UseTreeRebind::NONE,
+					  foobar, Location ());
+
+  auto paths = std::vector<Rust::AST::SimplePath> ();
+  Rust::Resolver::flatten_rebind (rebind, paths);
+
+  ASSERT_TRUE (!paths.empty ());
+  ASSERT_EQ (paths.size (), 1);
+  ASSERT_EQ (paths[0].get_segments ()[0].as_string (), "foo");
+  ASSERT_EQ (paths[0].get_segments ()[1].as_string (), "bar");
+}
+
+static void
+rust_flatten_rebind (void)
+{
+  auto frob = Rust::AST::SimplePath::from_str ("frobulator", Location ());
+
+  auto rebind = Rust::AST::UseTreeRebind (Rust::AST::UseTreeRebind::IDENTIFIER,
+					  frob, Location (), "saindoux");
+
+  auto paths = std::vector<Rust::AST::SimplePath> ();
+  Rust::Resolver::flatten_rebind (rebind, paths);
+
+  ASSERT_TRUE (!paths.empty ());
+  ASSERT_EQ (paths.size (), 2);
+  ASSERT_EQ (paths[0], "frobulator");
+  ASSERT_EQ (paths[1], "saindoux");
+}
+
+static void
+rust_flatten_rebind_nested (void)
+{
+  auto foo = Rust::AST::SimplePathSegment ("foo", Location ());
+  auto bar = Rust::AST::SimplePathSegment ("bar", Location ());
+  auto baz = Rust::AST::SimplePathSegment ("baz", Location ());
+
+  auto foo_bar_baz = Rust::AST::SimplePath ({foo, bar, baz});
+
+  auto rebind = Rust::AST::UseTreeRebind (Rust::AST::UseTreeRebind::IDENTIFIER,
+					  foo_bar_baz, Location (), "saindoux");
+
+  auto paths = std::vector<Rust::AST::SimplePath> ();
+  Rust::Resolver::flatten_rebind (rebind, paths);
+
+  ASSERT_TRUE (!paths.empty ());
+  ASSERT_EQ (paths.size (), 2);
+  ASSERT_EQ (paths[0].get_segments ()[0].as_string (), "foo");
+  ASSERT_EQ (paths[0].get_segments ()[1].as_string (), "bar");
+  ASSERT_EQ (paths[0].get_segments ()[2].as_string (), "baz");
+  ASSERT_EQ (paths[1].get_segments ()[0].as_string (), "foo");
+  ASSERT_EQ (paths[1].get_segments ()[1].as_string (), "bar");
+  ASSERT_EQ (paths[1].get_segments ()[2].as_string (), "saindoux");
+}
+
+static void
+rust_flatten_list (void)
+{
+  auto foo = Rust::AST::SimplePathSegment ("foo", Location ());
+  auto bar = Rust::AST::SimplePathSegment ("bar", Location ());
+  auto foo_bar = Rust::AST::SimplePath ({foo, bar});
+
+  auto baz = Rust::AST::SimplePath::from_str ("baz", Location ());
+  auto bul = Rust::AST::SimplePath::from_str ("bul", Location ());
+
+  // use foo::bar::{baz, bul};
+
+  auto use0 = std::unique_ptr<Rust::AST::UseTree> (
+    new Rust::AST::UseTreeRebind (Rust::AST::UseTreeRebind::NONE, baz,
+				  Location ()));
+  auto use1 = std::unique_ptr<Rust::AST::UseTree> (
+    new Rust::AST::UseTreeRebind (Rust::AST::UseTreeRebind::NONE, bul,
+				  Location ()));
+
+  auto uses = std::vector<std::unique_ptr<Rust::AST::UseTree>> ();
+  uses.emplace_back (std::move (use0));
+  uses.emplace_back (std::move (use1));
+
+  auto list = Rust::AST::UseTreeList (Rust::AST::UseTreeList::PATH_PREFIXED,
+				      foo_bar, std::move (uses), Location ());
+
+  auto paths = std::vector<Rust::AST::SimplePath> ();
+  Rust::Resolver::flatten_list (list, paths);
+
+  for (auto &path : paths)
+    fprintf (stderr, "%s\n", path.as_string ().c_str ());
+
+  ASSERT_TRUE (!paths.empty ());
+  ASSERT_EQ (paths.size (), 2);
+  ASSERT_EQ (paths[0].get_segments ()[0].as_string (), "foo");
+  ASSERT_EQ (paths[0].get_segments ()[1].as_string (), "bar");
+  ASSERT_EQ (paths[0].get_segments ()[2].as_string (), "baz");
+  ASSERT_EQ (paths[1].get_segments ()[0].as_string (), "foo");
+  ASSERT_EQ (paths[1].get_segments ()[1].as_string (), "bar");
+  ASSERT_EQ (paths[1].get_segments ()[2].as_string (), "bul");
+}
+
+static void
+rust_use_dec_flattening (void)
+{
+  rust_flatten_glob ();
+  rust_flatten_nested_glob ();
+  rust_flatten_rebind_none ();
+  rust_flatten_rebind ();
+  rust_flatten_rebind_nested ();
+  rust_flatten_list ();
+}
+
+void
+rust_simple_path_resolve_test (void)
+{
+  rust_use_dec_flattening ();
+}
+} // namespace selftest
+
+#endif // CHECKING_P
diff --git a/gcc/rust/resolve/rust-ast-resolve-item.h b/gcc/rust/resolve/rust-ast-resolve-item.h
index da5d4e8..e6b11f5 100644
--- a/gcc/rust/resolve/rust-ast-resolve-item.h
+++ b/gcc/rust/resolve/rust-ast-resolve-item.h
@@ -26,6 +26,7 @@
 #include "rust-ast-resolve-type.h"
 #include "rust-ast-resolve-pattern.h"
 #include "rust-ast-resolve-stmt.h"
+#include "config.h"
 
 namespace Rust {
 namespace Resolver {
@@ -81,6 +82,7 @@ public:
   void visit (AST::TraitImpl &impl_block) override;
   void visit (AST::Trait &trait) override;
   void visit (AST::ExternBlock &extern_block) override;
+  void visit (AST::UseDeclaration &) override;
 
 protected:
   void resolve_impl_item (AST::TraitImplItem *item, const CanonicalPath &prefix,
@@ -136,4 +138,13 @@ private:
 } // namespace Resolver
 } // namespace Rust
 
+#if CHECKING_P
+
+namespace selftest {
+extern void
+rust_simple_path_resolve_test (void);
+} // namespace selftest
+
+#endif // CHECKING_P
+
 #endif // RUST_AST_RESOLVE_ITEM_H
diff --git a/gcc/rust/rust-lang.cc b/gcc/rust/rust-lang.cc
index 4584c93..73f9839 100644
--- a/gcc/rust/rust-lang.cc
+++ b/gcc/rust/rust-lang.cc
@@ -36,6 +36,7 @@
 #include "selftest.h"
 #include "rust-cfg-parser.h"
 #include "rust-privacy-ctx.h"
+#include "rust-ast-resolve-item.h"
 
 #include <mpfr.h>
 // note: header files must be in this order or else forward declarations don't
@@ -459,6 +460,7 @@ run_rust_tests ()
   rust_cfg_parser_test ();
   rust_privacy_ctx_test ();
   rust_crate_name_validation_test ();
+  rust_simple_path_resolve_test ();
 }
 } // namespace selftest
 
diff --git a/gcc/rust/rust-session-manager.cc b/gcc/rust/rust-session-manager.cc
index 845a66a..0b0e5af 100644
--- a/gcc/rust/rust-session-manager.cc
+++ b/gcc/rust/rust-session-manager.cc
@@ -932,23 +932,25 @@ Session::injection (AST::Crate &crate)
 
   // create use tree path
   // prelude is injected_crate_name
-  std::vector<AST::SimplePathSegment> segments
-    = {AST::SimplePathSegment (injected_crate_name, Location ()),
-       AST::SimplePathSegment ("prelude", Location ()),
-       AST::SimplePathSegment ("v1", Location ())};
-  // create use tree and decl
-  std::unique_ptr<AST::UseTreeGlob> use_tree (
-    new AST::UseTreeGlob (AST::UseTreeGlob::PATH_PREFIXED,
-			  AST::SimplePath (std::move (segments)), Location ()));
-  AST::Attribute prelude_attr (AST::SimplePath::from_str ("prelude_import",
-							  Location ()),
-			       nullptr);
-  std::unique_ptr<AST::UseDeclaration> use_decl (
-    new AST::UseDeclaration (std::move (use_tree),
-			     AST::Visibility::create_error (),
-			     {std::move (prelude_attr)}, Location ()));
-
-  crate.items.insert (crate.items.begin (), std::move (use_decl));
+  // FIXME: Once we do want to include the standard library, add the prelude
+  // use item
+  // std::vector<AST::SimplePathSegment> segments
+  //   = {AST::SimplePathSegment (injected_crate_name, Location ()),
+  //      AST::SimplePathSegment ("prelude", Location ()),
+  //      AST::SimplePathSegment ("v1", Location ())};
+  // // create use tree and decl
+  // std::unique_ptr<AST::UseTreeGlob> use_tree (
+  //   new AST::UseTreeGlob (AST::UseTreeGlob::PATH_PREFIXED,
+  //     		  AST::SimplePath (std::move (segments)), Location ()));
+  // AST::Attribute prelude_attr (AST::SimplePath::from_str ("prelude_import",
+  //     						  Location ()),
+  //     		       nullptr);
+  // std::unique_ptr<AST::UseDeclaration> use_decl (
+  //   new AST::UseDeclaration (std::move (use_tree),
+  //     		     AST::Visibility::create_error (),
+  //     		     {std::move (prelude_attr)}, Location ()));
+
+  // crate.items.insert (crate.items.begin (), std::move (use_decl));
 
   /* TODO: potentially add checking attribute crate type? I can't figure out
    * what this does currently comment says "Unconditionally collect crate
diff --git a/gcc/testsuite/rust/compile/torture/cfg_attr.rs b/gcc/testsuite/rust/compile/torture/cfg_attr.rs
index 962d875..d65faf2 100644
--- a/gcc/testsuite/rust/compile/torture/cfg_attr.rs
+++ b/gcc/testsuite/rust/compile/torture/cfg_attr.rs
@@ -1,4 +1,4 @@
-use std::env; // Add one line so gccrs doesn't believe we're parsing a shebang
+mod fake {} // Add one line so gccrs doesn't believe we're parsing a shebang
 
 #[cfg_attr(feature = "somefeature", attribute = "someattr")]
 struct Feature;
diff --git a/gcc/testsuite/rust/compile/use_1.rs b/gcc/testsuite/rust/compile/use_1.rs
new file mode 100644
index 0000000..94b9632
--- /dev/null
+++ b/gcc/testsuite/rust/compile/use_1.rs
@@ -0,0 +1,16 @@
+mod frob {}
+
+use foo::bar::baz; // { dg-error "cannot find simple path segment .foo." }
+use frob::ulator; // { dg-error "cannot find simple path segment .ulator." }
+
+mod sain {
+    mod doux {}
+
+    mod dron {}
+}
+
+use not_sain::*; // { dg-error "cannot find simple path segment .not_sain." }
+
+use sain::*;
+use sain::{doux, dron};
+use sain::{doux, dron, graal}; // { dg-error "cannot find simple path segment .graal." }