gccrs: Add support for ambiguous use declarations

Glob use declarations may lead to ambiguous situation where two
definitions with the same name are imported in a given scope. The
compiler now handles shadowable items inserted after non shadowable
items. An error is now thrown when multiple shadowable items are imported
and used in the same rib.

gcc/rust/ChangeLog:

	* resolve/rust-early-name-resolver-2.0.cc (Early::visit): Adapt
	resolved type to the new API.
	(Early::visit_attributes): Retrieve the node id from the definition.
	* resolve/rust-forever-stack.h: Change the return type of getter
	functions. Those functions now return a definition type instead of a
	node id.
	* resolve/rust-forever-stack.hxx: Change member function implementation
	in the forever stack to accomodate it's API changes.
	* resolve/rust-late-name-resolver-2.0.cc (Late::visit): Use internal
	node id. Emit an error when resolving multiple ambiguous values.
	* resolve/rust-rib.cc (Rib::Definition::Definition): Add a default
	constructor.
	(Rib::Definition::is_ambiguous): Add a new function to determine
	whether a function definition is ambiguous or not.
	(Rib::Definition::to_string): Add a member function to convert a given
	definition to a string.
	(Rib::insert): Add new rules for value insertion in a rib. Insertion
	order does not impact the result anymore: inserting a shadowable value
	after a non shadowable one does not trigger an error anymore. All
	shadowable values inserted in a rib are kepts until being replaced by a
	non shadowable one.
	(Rib::get): Return a definition instead of a node id.
	* resolve/rust-rib.h: Update function prototypes.
	* resolve/rust-toplevel-name-resolver-2.0.cc (TopLevel::handle_use_glob):
	Update return value container to match the new function's prototype.
	(TopLevel::handle_use_dec): Likewise.
	(flatten_glob): Likewise.

Signed-off-by: Pierre-Emmanuel Patry <pierre-emmanuel.patry@embecosm.com>

7 files changed, 142 insertions, 71 deletions

diff --git a/gcc/rust/resolve/rust-early-name-resolver-2.0.cc b/gcc/rust/resolve/rust-early-name-resolver-2.0.cc
index 982c696..af148b0 100644
--- a/gcc/rust/resolve/rust-early-name-resolver-2.0.cc
+++ b/gcc/rust/resolve/rust-early-name-resolver-2.0.cc
@@ -152,9 +152,11 @@ Early::visit (AST::MacroInvocation &invoc)
 
   // https://doc.rust-lang.org/reference/macros-by-example.html#path-based-scope
 
-  tl::optional<NodeId> definition = tl::nullopt;
+  tl::optional<Rib::Definition> definition = tl::nullopt;
   if (path.get_segments ().size () == 1)
-    definition = textual_scope.get (path.get_final_segment ().as_string ());
+    definition
+      = textual_scope.get (path.get_final_segment ().as_string ())
+	  .map ([] (NodeId id) { return Rib::Definition::NonShadowable (id); });
 
   // we won't have changed `definition` from `nullopt` if there are more
   // than one segments in our path
@@ -169,13 +171,13 @@ Early::visit (AST::MacroInvocation &invoc)
       return;
     }
 
-  insert_once (invoc, *definition);
+  insert_once (invoc, definition->get_node_id ());
 
   // now do we need to keep mappings or something? or insert "uses" into our
   // ForeverStack? can we do that? are mappings simpler?
   auto mappings = Analysis::Mappings::get ();
   AST::MacroRulesDefinition *rules_def = nullptr;
-  if (!mappings->lookup_macro_def (definition.value (), &rules_def))
+  if (!mappings->lookup_macro_def (definition->get_node_id (), &rules_def))
     {
       // Macro definition not found, maybe it is not expanded yet.
       return;
@@ -212,8 +214,8 @@ Early::visit_attributes (std::vector<AST::Attribute> &attrs)
 		  continue;
 		}
 
-	      auto pm_def
-		= mappings->lookup_derive_proc_macro_def (definition.value ());
+	      auto pm_def = mappings->lookup_derive_proc_macro_def (
+		definition->get_node_id ());
 
 	      rust_assert (pm_def.has_value ());
 
@@ -234,8 +236,8 @@ Early::visit_attributes (std::vector<AST::Attribute> &attrs)
 			     "could not resolve attribute macro invocation");
 	      return;
 	    }
-	  auto pm_def
-	    = mappings->lookup_attribute_proc_macro_def (definition.value ());
+	  auto pm_def = mappings->lookup_attribute_proc_macro_def (
+	    definition->get_node_id ());
 
 	  rust_assert (pm_def.has_value ());
 
diff --git a/gcc/rust/resolve/rust-forever-stack.h b/gcc/rust/resolve/rust-forever-stack.h
index bba5875..3dab45e 100644
--- a/gcc/rust/resolve/rust-forever-stack.h
+++ b/gcc/rust/resolve/rust-forever-stack.h
@@ -480,21 +480,21 @@ public:
    * @param name Name of the identifier to locate in this scope or an outermore
    *        scope
    *
-   * @return a valid option with the NodeId if the identifier is present in the
-   *         current map, an empty one otherwise.
+   * @return a valid option with the Definition if the identifier is present in
+   * the current map, an empty one otherwise.
    */
-  tl::optional<NodeId> get (const Identifier &name);
+  tl::optional<Rib::Definition> get (const Identifier &name);
 
   /**
    * Resolve a path to its definition in the current `ForeverStack`
    *
    * // TODO: Add documentation for `segments`
    *
-   * @return a valid option with the NodeId if the path is present in the
+   * @return a valid option with the Definition if the path is present in the
    *         current map, an empty one otherwise.
    */
   template <typename S>
-  tl::optional<NodeId> resolve_path (const std::vector<S> &segments);
+  tl::optional<Rib::Definition> resolve_path (const std::vector<S> &segments);
 
   // FIXME: Documentation
   tl::optional<Resolver::CanonicalPath> to_canonical_path (NodeId id);
diff --git a/gcc/rust/resolve/rust-forever-stack.hxx b/gcc/rust/resolve/rust-forever-stack.hxx
index 008adff..6b622b8 100644
--- a/gcc/rust/resolve/rust-forever-stack.hxx
+++ b/gcc/rust/resolve/rust-forever-stack.hxx
@@ -90,11 +90,13 @@ ForeverStack<N>::pop ()
   rust_debug ("popping link");
 
   for (const auto &kv : cursor ().rib.get_values ())
-    rust_debug ("current_rib: k: %s, v: %d", kv.first.c_str (), kv.second);
+    rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
+		kv.second.to_string ().c_str ());
 
   if (cursor ().parent.has_value ())
     for (const auto &kv : cursor ().parent.value ().rib.get_values ())
-      rust_debug ("new cursor: k: %s, v: %d", kv.first.c_str (), kv.second);
+      rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
+		  kv.second.to_string ().c_str ());
 
   update_cursor (cursor ().parent.value ());
 }
@@ -222,22 +224,22 @@ ForeverStack<N>::update_cursor (Node &new_cursor)
 }
 
 template <Namespace N>
-tl::optional<NodeId>
+tl::optional<Rib::Definition>
 ForeverStack<N>::get (const Identifier &name)
 {
-  tl::optional<NodeId> resolved_node = tl::nullopt;
+  tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
 
   // TODO: Can we improve the API? have `reverse_iter` return an optional?
-  reverse_iter ([&resolved_node, &name] (Node &current) {
+  reverse_iter ([&resolved_definition, &name] (Node &current) {
     auto candidate = current.rib.get (name.as_string ());
 
     return candidate.map_or (
-      [&resolved_node] (NodeId found) {
+      [&resolved_definition] (Rib::Definition found) {
 	// for most namespaces, we do not need to care about various ribs - they
 	// are available from all contexts if defined in the current scope, or
 	// an outermore one. so if we do have a candidate, we can return it
 	// directly and stop iterating
-	resolved_node = found;
+	resolved_definition = found;
 
 	return KeepGoing::No;
       },
@@ -245,16 +247,16 @@ ForeverStack<N>::get (const Identifier &name)
       KeepGoing::Yes);
   });
 
-  return resolved_node;
+  return resolved_definition;
 }
 
 template <>
-tl::optional<NodeId> inline ForeverStack<Namespace::Labels>::get (
+tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
   const Identifier &name)
 {
-  tl::optional<NodeId> resolved_node = tl::nullopt;
+  tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
 
-  reverse_iter ([&resolved_node, &name] (Node &current) {
+  reverse_iter ([&resolved_definition, &name] (Node &current) {
     // looking up for labels cannot go through function ribs
     // TODO: What other ribs?
     if (current.rib.kind == Rib::Kind::Function)
@@ -264,15 +266,15 @@ tl::optional<NodeId> inline ForeverStack<Namespace::Labels>::get (
 
     // FIXME: Factor this in a function with the generic `get`
     return candidate.map_or (
-      [&resolved_node] (NodeId found) {
-	resolved_node = found;
+      [&resolved_definition] (Rib::Definition found) {
+	resolved_definition = found;
 
 	return KeepGoing::No;
       },
       KeepGoing::Yes);
   });
 
-  return resolved_node;
+  return resolved_definition;
 }
 
 /* Check if an iterator points to the last element */
@@ -444,7 +446,7 @@ ForeverStack<N>::resolve_segments (
 
 template <Namespace N>
 template <typename S>
-tl::optional<NodeId>
+tl::optional<Rib::Definition>
 ForeverStack<N>::resolve_path (const std::vector<S> &segments)
 {
   // TODO: What to do if segments.empty() ?
@@ -472,8 +474,9 @@ ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
   auto values = starting_point.rib.get_values ();
 
   for (auto &kv : values)
-    if (kv.second.id == to_find)
-      return {{starting_point, kv.first}};
+    for (auto id : kv.second.ids)
+      if (id == to_find)
+	return {{starting_point, kv.first}};
 
   for (auto &child : starting_point.children)
     {
@@ -582,7 +585,7 @@ ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
   stream << next << "rib: {\n";
 
   for (const auto &kv : rib.get_values ())
-    stream << next_next << kv.first << ": " << kv.second.id << "\n";
+    stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
 
   stream << next << "},\n";
 }
diff --git a/gcc/rust/resolve/rust-late-name-resolver-2.0.cc b/gcc/rust/resolve/rust-late-name-resolver-2.0.cc
index d8bd9ac..5c8d976 100644
--- a/gcc/rust/resolve/rust-late-name-resolver-2.0.cc
+++ b/gcc/rust/resolve/rust-late-name-resolver-2.0.cc
@@ -159,7 +159,7 @@ Late::visit (AST::IdentifierExpr &expr)
 {
   // TODO: same thing as visit(PathInExpression) here?
 
-  tl::optional<NodeId> resolved = tl::nullopt;
+  tl::optional<Rib::Definition> resolved = tl::nullopt;
   auto label = ctx.labels.get (expr.get_ident ());
   auto value = ctx.values.get (expr.get_ident ());
 
@@ -179,7 +179,8 @@ Late::visit (AST::IdentifierExpr &expr)
       return;
     }
 
-  ctx.map_usage (Usage (expr.get_node_id ()), Definition (*resolved));
+  ctx.map_usage (Usage (expr.get_node_id ()),
+		 Definition (resolved->get_node_id ()));
 
   // in the old resolver, resolutions are kept in the resolver, not the mappings
   // :/ how do we deal with that?
@@ -200,7 +201,14 @@ Late::visit (AST::PathInExpression &expr)
   if (!value.has_value ())
     rust_unreachable (); // Should have been resolved earlier
 
-  ctx.map_usage (Usage (expr.get_node_id ()), Definition (*value));
+  if (value->is_ambiguous ())
+    {
+      rust_error_at (expr.get_locus (), ErrorCode::E0659, "%qs is ambiguous",
+		     expr.as_string ().c_str ());
+      return;
+    }
+  ctx.map_usage (Usage (expr.get_node_id ()),
+		 Definition (value->get_node_id ()));
 }
 
 void
@@ -213,7 +221,8 @@ Late::visit (AST::TypePath &type)
 
   auto resolved = ctx.types.get (type.get_segments ().back ()->as_string ());
 
-  ctx.map_usage (Usage (type.get_node_id ()), Definition (*resolved));
+  ctx.map_usage (Usage (type.get_node_id ()),
+		 Definition (resolved->get_node_id ()));
 }
 
 } // namespace Resolver2_0
diff --git a/gcc/rust/resolve/rust-rib.cc b/gcc/rust/resolve/rust-rib.cc
index dee3a09..a73e2bd 100644
--- a/gcc/rust/resolve/rust-rib.cc
+++ b/gcc/rust/resolve/rust-rib.cc
@@ -23,9 +23,30 @@ namespace Rust {
 namespace Resolver2_0 {
 
 Rib::Definition::Definition (NodeId id, bool shadowable)
-  : id (id), shadowable (shadowable)
+  : ids ({id}), shadowable (shadowable)
 {}
 
+bool
+Rib::Definition::is_ambiguous () const
+{
+  return shadowable && ids.size () > 1;
+}
+
+std::string
+Rib::Definition::to_string () const
+{
+  std::stringstream out;
+  out << (shadowable ? "(S)" : "(NS)") << "[";
+  std::string sep;
+  for (auto id : ids)
+    {
+      out << sep << id;
+      sep = ",";
+    }
+  out << "]";
+  return out.str ();
+}
+
 Rib::Definition
 Rib::Definition::Shadowable (NodeId id)
 {
@@ -58,28 +79,46 @@ Rib::Rib (Kind kind, std::unordered_map<std::string, NodeId> to_insert)
 tl::expected<NodeId, DuplicateNameError>
 Rib::insert (std::string name, Definition def)
 {
-  auto res = values.insert ({name, def});
-  auto inserted_id = res.first->second.id;
-  auto existed = !res.second;
-
-  // if we couldn't insert, the element already exists - exit with an error,
-  // unless shadowing is allowed
-  if (existed && !def.shadowable)
-    return tl::make_unexpected (DuplicateNameError (name, inserted_id));
-
-  // return the NodeId
-  return inserted_id;
+  auto it = values.find (name);
+  if (it == values.end ())
+    {
+      /* No old value */
+      values[name] = def;
+    }
+  else if (it->second.shadowable && def.shadowable)
+    { /* Both shadowable */
+      auto &current = values[name];
+      for (auto id : def.ids)
+	{
+	  if (std::find (current.ids.cbegin (), current.ids.cend (), id)
+	      == current.ids.cend ())
+	    {
+	      current.ids.push_back (id);
+	    }
+	}
+    }
+  else if (it->second.shadowable)
+    { /* Only old shadowable : replace value */
+      values[name] = def;
+    }
+  else /* Neither are shadowable */
+    {
+      return tl::make_unexpected (
+	DuplicateNameError (name, it->second.ids.back ()));
+    }
+
+  return def.ids.back ();
 }
 
-tl::optional<NodeId>
+tl::optional<Rib::Definition>
 Rib::get (const std::string &name)
 {
   auto it = values.find (name);
 
   if (it == values.end ())
-    return {};
+    return tl::nullopt;
 
-  return it->second.id;
+  return it->second;
 }
 
 const std::unordered_map<std::string, Rib::Definition> &
diff --git a/gcc/rust/resolve/rust-rib.h b/gcc/rust/resolve/rust-rib.h
index 732ad76..3db17b4 100644
--- a/gcc/rust/resolve/rust-rib.h
+++ b/gcc/rust/resolve/rust-rib.h
@@ -114,9 +114,24 @@ public:
     static Definition NonShadowable (NodeId id);
     static Definition Shadowable (NodeId id);
 
-    NodeId id;
+    std::vector<NodeId> ids;
     bool shadowable;
 
+    Definition () = default;
+
+    Definition &operator= (const Definition &) = default;
+    Definition (Definition const &) = default;
+
+    bool is_ambiguous () const;
+
+    NodeId get_node_id ()
+    {
+      rust_assert (!is_ambiguous ());
+      return ids[0];
+    }
+
+    std::string to_string () const;
+
   private:
     Definition (NodeId id, bool shadowable);
   };
@@ -163,7 +178,7 @@ public:
    *
    * @return tl::nullopt if the key does not exist, the NodeId otherwise
    */
-  tl::optional<NodeId> get (const std::string &name);
+  tl::optional<Rib::Definition> get (const std::string &name);
 
   /* View all the values stored in the rib */
   const std::unordered_map<std::string, Definition> &get_values () const;
diff --git a/gcc/rust/resolve/rust-toplevel-name-resolver-2.0.cc b/gcc/rust/resolve/rust-toplevel-name-resolver-2.0.cc
index 7f4169a..6929bdb 100644
--- a/gcc/rust/resolve/rust-toplevel-name-resolver-2.0.cc
+++ b/gcc/rust/resolve/rust-toplevel-name-resolver-2.0.cc
@@ -401,7 +401,8 @@ TopLevel::handle_use_glob (AST::SimplePath glob)
   if (!resolved.has_value ())
     return false;
 
-  auto result = Analysis::Mappings::get ()->lookup_ast_module (*resolved);
+  auto result
+    = Analysis::Mappings::get ()->lookup_ast_module (resolved->get_node_id ());
 
   if (!result.has_value ())
     return false;
@@ -428,7 +429,7 @@ TopLevel::handle_use_dec (AST::SimplePath path)
   auto resolve_and_insert
     = [this, &found, &declared_name, locus] (Namespace ns,
 					     const AST::SimplePath &path) {
-	tl::optional<NodeId> resolved = tl::nullopt;
+	tl::optional<Rib::Definition> resolved = tl::nullopt;
 
 	// FIXME: resolve_path needs to return an `expected<NodeId, Error>` so
 	// that we can improve it with hints or location or w/ever. and maybe
@@ -450,22 +451,22 @@ TopLevel::handle_use_dec (AST::SimplePath path)
 	  }
 
 	// FIXME: Ugly
-	(void) resolved.map (
-	  [this, &found, &declared_name, locus, ns, path] (NodeId id) {
-	    found = true;
-
-	    // what do we do with the id?
-	    insert_or_error_out (declared_name, locus, id, ns);
-	    auto result = node_forwarding.find (id);
-	    if (result != node_forwarding.cend ()
-		&& result->second != path.get_node_id ())
-	      rust_error_at (path.get_locus (), "%<%s%> defined multiple times",
-			     declared_name.c_str ());
-	    else // No previous thing has inserted this into our scope
-	      node_forwarding.insert ({id, path.get_node_id ()});
-
-	    return id;
-	  });
+	(void) resolved.map ([this, &found, &declared_name, locus, ns,
+			      path] (Rib::Definition def) {
+	  found = true;
+
+	  // what do we do with the id?
+	  insert_or_error_out (declared_name, locus, def.get_node_id (), ns);
+	  auto result = node_forwarding.find (def.get_node_id ());
+	  if (result != node_forwarding.cend ()
+	      && result->second != path.get_node_id ())
+	    rust_error_at (path.get_locus (), "%<%s%> defined multiple times",
+			   declared_name.c_str ());
+	  else // No previous thing has inserted this into our scope
+	    node_forwarding.insert ({def.get_node_id (), path.get_node_id ()});
+
+	  return def.get_node_id ();
+	});
       };
 
   // do this for all namespaces (even Labels?)
@@ -587,7 +588,9 @@ flatten_glob (const AST::UseTreeGlob &glob, std::vector<AST::SimplePath> &paths,
 
   // (PE): Get path rib
   auto rib = ctx.values.resolve_path (glob.get_path ().get_segments ())
-	       .and_then ([&] (NodeId id) { return ctx.values.to_rib (id); });
+	       .and_then ([&] (Rib::Definition def) {
+		 return ctx.values.to_rib (def.get_node_id ());
+	       });
   if (rib.has_value ())
     {
       auto value = rib.value ().get_values ();