BugFix: TypePath resolution to handle associated types

TypePath's can be fully resolved at name resolution time for example a
primitive types are single segments which can be resolved. But in the event
of a generic TypeBound path such as: T::A where T is the generic type param
in a function and A is its own associated type this require's the
resolution to be split over the name resolver and type resolver.

Like PathInExpression's the name resolver is able to resolve the root
segment of 'T' but requires a path probe on the type-bounds of T to find
the associated type 'A'.

Fixes #746

11 files changed, 396 insertions, 58 deletions

diff --git a/gcc/rust/hir/tree/rust-hir-path.h b/gcc/rust/hir/tree/rust-hir-path.h
index 13e246f..a04398e 100644
--- a/gcc/rust/hir/tree/rust-hir-path.h
+++ b/gcc/rust/hir/tree/rust-hir-path.h
@@ -420,6 +420,11 @@ public:
   const Analysis::NodeMapping &get_mappings () const { return mappings; }
 
   const PathIdentSegment &get_ident_segment () const { return ident_segment; }
+
+  bool is_generic_segment () const
+  {
+    return get_type () == SegmentType::GENERIC;
+  }
 };
 
 // Segment used in type path with generic args
diff --git a/gcc/rust/resolve/rust-ast-resolve-item.h b/gcc/rust/resolve/rust-ast-resolve-item.h
index 87bf10e..71085f6 100644
--- a/gcc/rust/resolve/rust-ast-resolve-item.h
+++ b/gcc/rust/resolve/rust-ast-resolve-item.h
@@ -591,7 +591,7 @@ public:
 
     // Self is an implicit TypeParam so lets mark it as such
     resolver->get_type_scope ().append_reference_for_def (
-      Self.get_id (), implicit_self->get_node_id ());
+      Self.get_node_id (), implicit_self->get_node_id ());
 
     if (trait.has_type_param_bounds ())
       {
diff --git a/gcc/rust/resolve/rust-ast-resolve-type.h b/gcc/rust/resolve/rust-ast-resolve-type.h
index a6d1da1..2dc7fbf 100644
--- a/gcc/rust/resolve/rust-ast-resolve-type.h
+++ b/gcc/rust/resolve/rust-ast-resolve-type.h
@@ -188,35 +188,6 @@ class ResolveRelativeTypePath : public ResolveTypeToCanonicalPath
   using ResolveTypeToCanonicalPath::visit;
 
 public:
-  static NodeId go (AST::TypePath &path, NodeId parent,
-		    bool canonicalize_type_with_generics)
-  {
-    CanonicalPath canonical_path
-      = ResolveTypeToCanonicalPath::resolve (path,
-					     canonicalize_type_with_generics,
-					     true);
-    if (canonical_path.is_empty ())
-      {
-	rust_error_at (path.get_locus (),
-		       "Failed to resolve canonical path for TypePath");
-	return UNKNOWN_NODEID;
-      }
-
-    auto resolver = Resolver::get ();
-    NodeId resolved_node = UNKNOWN_NODEID;
-
-    // We may need to change how names are resolved, like described in :
-    // https://github.com/rust-lang/rust/blob/1f94abcda6884893d4723304102089198caa0839/compiler/rustc_resolve/src/lib.rs#L1722
-    if (!resolver->get_type_scope ().lookup (canonical_path, &resolved_node))
-      {
-	rust_error_at (path.get_locus (), "failed to resolve TypePath: %s",
-		       canonical_path.get ().c_str ());
-	return UNKNOWN_NODEID;
-      }
-
-    return resolved_node;
-  }
-
   static NodeId go (AST::QualifiedPathInType &path, NodeId parent,
 		    bool canonicalize_type_with_generics)
   {
@@ -316,11 +287,58 @@ public:
 
   void visit (AST::TypePath &path) override
   {
-    resolved_node
-      = ResolveRelativeTypePath::go (path, parent,
-				     canonicalize_type_with_generics);
-    ok = resolved_node != UNKNOWN_NODEID;
-    if (ok)
+    auto canonical_path
+      = ResolveTypeToCanonicalPath::resolve (path,
+					     canonicalize_type_with_generics,
+					     true);
+    if (canonical_path.is_empty ())
+      {
+	rust_error_at (path.get_locus (),
+		       "Failed to resolve canonical path for TypePath");
+	return;
+      }
+
+    ok = !canonical_path.is_empty ();
+
+    // lets try and resolve in one go else leave it up to the type resolver to
+    // figure outer
+
+    if (resolver->get_type_scope ().lookup (canonical_path, &resolved_node))
+      {
+	resolver->insert_resolved_type (path.get_node_id (), resolved_node);
+	resolver->insert_new_definition (path.get_node_id (),
+					 Definition{path.get_node_id (),
+						    parent});
+	return;
+      }
+
+    // lets resolve as many segments as we can and leave it up to the type
+    // resolver otherwise
+    size_t nprocessed = 0;
+    canonical_path.iterate ([&] (const CanonicalPath &seg) -> bool {
+      resolved_node = UNKNOWN_NODEID;
+
+      if (!resolver->get_type_scope ().lookup (seg, &resolved_node))
+	return false;
+
+      resolver->insert_resolved_type (seg.get_node_id (), resolved_node);
+      resolver->insert_new_definition (seg.get_node_id (),
+				       Definition{path.get_node_id (), parent});
+      nprocessed++;
+      return true;
+    });
+
+    if (nprocessed == 0)
+      {
+	rust_error_at (path.get_locus (), "failed to resolve TypePath: %s",
+		       path.as_string ().c_str ());
+	return;
+      }
+
+    // its ok if this fails since the type resolver sometimes will need to
+    // investigate the bounds of a type for the associated type for example see:
+    // https://github.com/Rust-GCC/gccrs/issues/746
+    if (nprocessed == canonical_path.size ())
       {
 	resolver->insert_resolved_type (path.get_node_id (), resolved_node);
 	resolver->insert_new_definition (path.get_node_id (),
diff --git a/gcc/rust/typecheck/rust-hir-type-check-path.cc b/gcc/rust/typecheck/rust-hir-type-check-path.cc
index 8b53e44..0aea8ca 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-path.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-path.cc
@@ -41,6 +41,7 @@ TypeCheckExpr::visit (HIR::QualifiedPathInExpression &expr)
 
       resolve_segments (root_resolved_node_id, expr.get_segments (), 0, root,
 			expr.get_mappings (), expr.get_locus ());
+      return;
     }
 
   // Resolve the trait now
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.cc b/gcc/rust/typecheck/rust-hir-type-check-type.cc
index 7ad6d03..a479581 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.cc
@@ -28,10 +28,26 @@ TypeCheckType::visit (HIR::TypePath &path)
   // lookup the Node this resolves to
   NodeId ref;
   auto nid = path.get_mappings ().get_nodeid ();
-  if (!resolver->lookup_resolved_type (nid, &ref))
+  bool is_fully_resolved = resolver->lookup_resolved_type (nid, &ref);
+
+  TyTy::BaseType *lookup = nullptr;
+  if (!is_fully_resolved)
     {
-      rust_fatal_error (path.get_locus (), "failed to resolve node '%d' to HIR",
-			nid);
+      // this can happen so we need to look up the root then resolve the
+      // remaining segments if possible
+      size_t offset = 0;
+      NodeId resolved_node_id = UNKNOWN_NODEID;
+      TyTy::BaseType *root
+	= resolve_root_path (path, &offset, &resolved_node_id);
+
+      rust_assert (root != nullptr);
+      if (root->get_kind () == TyTy::TypeKind::ERROR)
+	return;
+
+      translated
+	= resolve_segments (resolved_node_id, path.get_mappings ().get_hirid (),
+			    path.get_segments (), offset, root,
+			    path.get_mappings (), path.get_locus ());
       return;
     }
 
@@ -43,7 +59,6 @@ TypeCheckType::visit (HIR::TypePath &path)
       return;
     }
 
-  TyTy::BaseType *lookup = nullptr;
   if (!context->lookup_type (hir_lookup, &lookup))
     {
       rust_error_at (path.get_locus (), "failed to lookup HIR TyTy");
@@ -109,8 +124,12 @@ TypeCheckType::visit (HIR::QualifiedPathInType &path)
 	&root_resolved_node_id);
       rust_assert (ok);
 
-      resolve_segments (root_resolved_node_id, path.get_segments (), 0,
-			translated, path.get_mappings (), path.get_locus ());
+      translated = resolve_segments (root_resolved_node_id,
+				     path.get_mappings ().get_hirid (),
+				     path.get_segments (), 0, translated,
+				     path.get_mappings (), path.get_locus ());
+
+      return;
     }
 
   // Resolve the trait now
@@ -207,18 +226,302 @@ TypeCheckType::visit (HIR::QualifiedPathInType &path)
       return;
     }
 
-  resolve_segments (root_resolved_node_id, path.get_segments (), 0, translated,
-		    path.get_mappings (), path.get_locus ());
+  translated
+    = resolve_segments (root_resolved_node_id,
+			path.get_mappings ().get_hirid (), path.get_segments (),
+			0, translated, path.get_mappings (), path.get_locus ());
 }
 
-void
+TyTy::BaseType *
+TypeCheckType::resolve_root_path (HIR::TypePath &path, size_t *offset,
+				  NodeId *root_resolved_node_id)
+{
+  TyTy::BaseType *root_tyty = nullptr;
+  *offset = 0;
+  for (size_t i = 0; i < path.get_num_segments (); i++)
+    {
+      std::unique_ptr<HIR::TypePathSegment> &seg = path.get_segments ().at (i);
+
+      bool have_more_segments = (path.get_num_segments () - 1 != i);
+      bool is_root = *offset == 0;
+      NodeId ast_node_id = seg->get_mappings ().get_nodeid ();
+
+      // then lookup the reference_node_id
+      NodeId ref_node_id = UNKNOWN_NODEID;
+      if (resolver->lookup_resolved_name (ast_node_id, &ref_node_id))
+	{
+	  // these ref_node_ids will resolve to a pattern declaration but we
+	  // are interested in the definition that this refers to get the
+	  // parent id
+	  Definition def;
+	  if (!resolver->lookup_definition (ref_node_id, &def))
+	    {
+	      rust_error_at (path.get_locus (),
+			     "unknown reference for resolved name");
+	      return new TyTy::ErrorType (path.get_mappings ().get_hirid ());
+	    }
+	  ref_node_id = def.parent;
+	}
+      else
+	{
+	  resolver->lookup_resolved_type (ast_node_id, &ref_node_id);
+	}
+
+      // ref_node_id is the NodeId that the segments refers to.
+      if (ref_node_id == UNKNOWN_NODEID)
+	{
+	  if (is_root)
+	    {
+	      rust_error_at (seg->get_locus (),
+			     "failed to type resolve root segment");
+	      return new TyTy::ErrorType (path.get_mappings ().get_hirid ());
+	    }
+	  return root_tyty;
+	}
+
+      // node back to HIR
+      HirId ref;
+      if (!mappings->lookup_node_to_hir (path.get_mappings ().get_crate_num (),
+					 ref_node_id, &ref))
+	{
+	  if (is_root)
+	    {
+	      rust_error_at (seg->get_locus (), "789 reverse lookup failure");
+	      rust_debug_loc (
+		seg->get_locus (),
+		"failure with [%s] mappings [%s] ref_node_id [%u]",
+		seg->as_string ().c_str (),
+		seg->get_mappings ().as_string ().c_str (), ref_node_id);
+
+	      return new TyTy::ErrorType (path.get_mappings ().get_hirid ());
+	    }
+
+	  return root_tyty;
+	}
+
+      auto seg_is_module
+	= (nullptr
+	   != mappings->lookup_module (path.get_mappings ().get_crate_num (),
+				       ref));
+
+      if (seg_is_module)
+	{
+	  // A::B::C::this_is_a_module::D::E::F
+	  //          ^^^^^^^^^^^^^^^^
+	  //          Currently handling this.
+	  if (have_more_segments)
+	    {
+	      (*offset)++;
+	      continue;
+	    }
+
+	  // In the case of :
+	  // A::B::C::this_is_a_module
+	  //          ^^^^^^^^^^^^^^^^
+	  // This is an error, we are not expecting a module.
+	  rust_error_at (seg->get_locus (), "expected value");
+	  return new TyTy::ErrorType (path.get_mappings ().get_hirid ());
+	}
+
+      TyTy::BaseType *lookup = nullptr;
+      if (!context->lookup_type (ref, &lookup))
+	{
+	  if (is_root)
+	    {
+	      rust_error_at (seg->get_locus (),
+			     "failed to resolve root segment");
+	      return new TyTy::ErrorType (path.get_mappings ().get_hirid ());
+	    }
+	  return root_tyty;
+	}
+
+      // if we have a previous segment type
+      if (root_tyty != nullptr)
+	{
+	  // if this next segment needs substitution we must apply the
+	  // previous type arguments
+	  //
+	  // such as: GenericStruct::<_>::new(123, 456)
+	  if (lookup->needs_generic_substitutions ())
+	    {
+	      if (!root_tyty->needs_generic_substitutions ())
+		{
+		  auto used_args_in_prev_segment
+		    = GetUsedSubstArgs::From (root_tyty);
+		  lookup
+		    = SubstMapperInternal::Resolve (lookup,
+						    used_args_in_prev_segment);
+		}
+	    }
+	}
+
+      // turbo-fish segment path::<ty>
+      if (seg->is_generic_segment ())
+	{
+	  HIR::TypePathSegmentGeneric *generic_segment
+	    = static_cast<HIR::TypePathSegmentGeneric *> (seg.get ());
+
+	  if (!lookup->can_substitute ())
+	    {
+	      rust_error_at (seg->get_locus (),
+			     "substitutions not supported for %s",
+			     lookup->as_string ().c_str ());
+	      return new TyTy::ErrorType (lookup->get_ref ());
+	    }
+	  lookup = SubstMapper::Resolve (lookup, path.get_locus (),
+					 &generic_segment->get_generic_args ());
+	}
+
+      *root_resolved_node_id = ref_node_id;
+      *offset = *offset + 1;
+      root_tyty = lookup;
+    }
+
+  return root_tyty;
+}
+
+TyTy::BaseType *
 TypeCheckType::resolve_segments (
-  NodeId root_resolved_node_id,
+  NodeId root_resolved_node_id, HirId expr_id,
   std::vector<std::unique_ptr<HIR::TypePathSegment>> &segments, size_t offset,
   TyTy::BaseType *tyseg, const Analysis::NodeMapping &expr_mappings,
   Location expr_locus)
 {
-  gcc_unreachable ();
+  NodeId resolved_node_id = root_resolved_node_id;
+  TyTy::BaseType *prev_segment = tyseg;
+  for (size_t i = offset; i < segments.size (); i++)
+    {
+      std::unique_ptr<HIR::TypePathSegment> &seg = segments.at (i);
+
+      bool reciever_is_generic
+	= prev_segment->get_kind () == TyTy::TypeKind::PARAM;
+      bool probe_bounds = true;
+      bool probe_impls = !reciever_is_generic;
+      bool ignore_mandatory_trait_items = !reciever_is_generic;
+
+      // probe the path is done in two parts one where we search impls if no
+      // candidate is found then we search extensions from traits
+      auto candidates
+	= PathProbeType::Probe (prev_segment, seg->get_ident_segment (),
+				probe_impls, false,
+				ignore_mandatory_trait_items);
+      if (candidates.size () == 0)
+	{
+	  candidates
+	    = PathProbeType::Probe (prev_segment, seg->get_ident_segment (),
+				    false, probe_bounds,
+				    ignore_mandatory_trait_items);
+
+	  if (candidates.size () == 0)
+	    {
+	      rust_error_at (
+		seg->get_locus (),
+		"failed to resolve path segment using an impl Probe");
+	      return new TyTy::ErrorType (expr_id);
+	    }
+	}
+
+      if (candidates.size () > 1)
+	{
+	  ReportMultipleCandidateError::Report (candidates,
+						seg->get_ident_segment (),
+						seg->get_locus ());
+	  return new TyTy::ErrorType (expr_id);
+	}
+
+      auto &candidate = candidates.at (0);
+      prev_segment = tyseg;
+      tyseg = candidate.ty;
+
+      if (candidate.is_impl_candidate ())
+	{
+	  resolved_node_id
+	    = candidate.item.impl.impl_item->get_impl_mappings ().get_nodeid ();
+	}
+      else
+	{
+	  resolved_node_id
+	    = candidate.item.trait.item_ref->get_mappings ().get_nodeid ();
+
+	  // lookup the associated-impl-trait
+	  HIR::ImplBlock *impl = candidate.item.trait.impl;
+	  if (impl != nullptr)
+	    {
+	      AssociatedImplTrait *lookup_associated = nullptr;
+	      bool found_impl_trait = context->lookup_associated_trait_impl (
+		impl->get_mappings ().get_hirid (), &lookup_associated);
+	      rust_assert (found_impl_trait);
+
+	      lookup_associated->setup_associated_types ();
+
+	      // we need a new ty_ref_id for this trait item
+	      tyseg = tyseg->clone ();
+	      tyseg->set_ty_ref (mappings->get_next_hir_id ());
+	    }
+	}
+
+      if (seg->is_generic_segment ())
+	{
+	  HIR::TypePathSegmentGeneric *generic_segment
+	    = static_cast<HIR::TypePathSegmentGeneric *> (seg.get ());
+
+	  if (!tyseg->can_substitute ())
+	    {
+	      rust_error_at (expr_locus, "substitutions not supported for %s",
+			     tyseg->as_string ().c_str ());
+	      return new TyTy::ErrorType (expr_id);
+	    }
+
+	  tyseg = SubstMapper::Resolve (tyseg, expr_locus,
+					&generic_segment->get_generic_args ());
+	  if (tyseg->get_kind () == TyTy::TypeKind::ERROR)
+	    return new TyTy::ErrorType (expr_id);
+	}
+    }
+
+  context->insert_receiver (expr_mappings.get_hirid (), prev_segment);
+  if (tyseg->needs_generic_substitutions ())
+    {
+      Location locus = segments.back ()->get_locus ();
+      if (!prev_segment->needs_generic_substitutions ())
+	{
+	  auto used_args_in_prev_segment
+	    = GetUsedSubstArgs::From (prev_segment);
+	  if (!used_args_in_prev_segment.is_error ())
+	    tyseg
+	      = SubstMapperInternal::Resolve (tyseg, used_args_in_prev_segment);
+	}
+      else
+	{
+	  tyseg = SubstMapper::InferSubst (tyseg, locus);
+	}
+
+      if (tyseg->get_kind () == TyTy::TypeKind::ERROR)
+	return new TyTy::ErrorType (expr_id);
+    }
+
+  rust_assert (resolved_node_id != UNKNOWN_NODEID);
+
+  // lookup if the name resolver was able to canonically resolve this or not
+  NodeId path_resolved_id = UNKNOWN_NODEID;
+  if (resolver->lookup_resolved_name (expr_mappings.get_nodeid (),
+				      &path_resolved_id))
+    {
+      rust_assert (path_resolved_id == resolved_node_id);
+    }
+  // check the type scope
+  else if (resolver->lookup_resolved_type (expr_mappings.get_nodeid (),
+					   &path_resolved_id))
+    {
+      rust_assert (path_resolved_id == resolved_node_id);
+    }
+  else
+    {
+      resolver->insert_resolved_name (expr_mappings.get_nodeid (),
+				      resolved_node_id);
+    }
+
+  return tyseg;
 }
 
 void
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.h b/gcc/rust/typecheck/rust-hir-type-check-type.h
index 3fdbe30..e0c0e91 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.h
@@ -185,8 +185,11 @@ private:
       }
   }
 
-  void resolve_segments (
-    NodeId root_resolved_node_id,
+  TyTy::BaseType *resolve_root_path (HIR::TypePath &path, size_t *offset,
+				     NodeId *root_resolved_node_id);
+
+  TyTy::BaseType *resolve_segments (
+    NodeId root_resolved_node_id, HirId expr_id,
     std::vector<std::unique_ptr<HIR::TypePathSegment>> &segments, size_t offset,
     TyTy::BaseType *tyseg, const Analysis::NodeMapping &expr_mappings,
     Location expr_locus);
diff --git a/gcc/rust/util/rust-canonical-path.h b/gcc/rust/util/rust-canonical-path.h
index b5f8dd7..6b4bfa1 100644
--- a/gcc/rust/util/rust-canonical-path.h
+++ b/gcc/rust/util/rust-canonical-path.h
@@ -95,7 +95,12 @@ public:
   }
 
   // if we have the path A::B::C this will give a callback for each segment
-  // example:
+  // including the prefix, example:
+  //
+  // path:
+  //   A::B::C
+  //
+  // iterate:
   //   A
   //   A::B
   //   A::B::C
@@ -110,6 +115,16 @@ public:
       }
   }
 
+  // if we have the path A::B::C this will give a callback for each segment
+  // example:
+  //
+  // path:
+  //   A::B::C
+  //
+  // iterate:
+  //   A
+  //      B
+  //         C
   void iterate_segs (std::function<bool (const CanonicalPath &)> cb) const
   {
     for (auto &seg : segs)
@@ -123,7 +138,7 @@ public:
 
   size_t size () const { return segs.size (); }
 
-  NodeId get_id () const
+  NodeId get_node_id () const
   {
     rust_assert (!segs.empty ());
     return segs.back ().first;
diff --git a/gcc/testsuite/rust/compile/generic-default1.rs b/gcc/testsuite/rust/compile/generic-default1.rs
index 1b04f7d..0a132bf 100644
--- a/gcc/testsuite/rust/compile/generic-default1.rs
+++ b/gcc/testsuite/rust/compile/generic-default1.rs
@@ -1,5 +1,3 @@
-// { dg-error "unresolved type" "" { target *-*-* } 0 }
-
 struct Foo<A = i321>(A);
 // { dg-error "failed to resolve TypePath: i321" "" { target *-*-* } .-1 }
 
diff --git a/gcc/testsuite/rust/compile/generics5.rs b/gcc/testsuite/rust/compile/generics5.rs
index e70afa8..6c847b5 100644
--- a/gcc/testsuite/rust/compile/generics5.rs
+++ b/gcc/testsuite/rust/compile/generics5.rs
@@ -1,12 +1,9 @@
-// Current errors are too noisy to match specific ones.
-// { dg-error "failed to resolve TypePath: T" "" { target *-*-* } 0 }
-// { dg-error "unresolved type" "" { target *-*-* } 0 }
-
 struct GenericStruct<T>(T, usize);
 
 fn main() {
     let a2;
     a2 = GenericStruct::<i8, T>(1, 456);
+    // { dg-error "failed to resolve TypePath: T" "" { target *-*-* } .-1 }
 
     let b2: i32 = a2.0;
     let c2: usize = a2.1;
diff --git a/gcc/testsuite/rust/compile/generics9.rs b/gcc/testsuite/rust/compile/generics9.rs
index f3fd6b5..3766703 100644
--- a/gcc/testsuite/rust/compile/generics9.rs
+++ b/gcc/testsuite/rust/compile/generics9.rs
@@ -1,6 +1,5 @@
 struct Foo<A, B = (A, B)>(A, B);
 // { dg-error "failed to resolve TypePath: B" "" { target *-*-* } .-1 }
-// { dg-error "unresolved type" "" { target *-*-* } .-2 }
 
 fn main() {
     let a: Foo<bool>;
diff --git a/gcc/testsuite/rust/compile/method2.rs b/gcc/testsuite/rust/compile/method2.rs
index 4a0e784..c8699f7 100644
--- a/gcc/testsuite/rust/compile/method2.rs
+++ b/gcc/testsuite/rust/compile/method2.rs
@@ -13,5 +13,4 @@ fn main() {
     let b;
     b = a.test::<asfasfr>(false);
     // { dg-error "failed to resolve TypePath: asfasfr" "" { target *-*-* } .-1 }
-    // { dg-error "unresolved type" "" { target *-*-* } .-2 }
 }