Merge #502

502: Trait Obligations building block r=philberty a=philberty

This is a building block for actually enforcing the obligations of a trait.
It includes a query-based lookup of the trait to avoid reloading it so
we only do the hard work once. Then provides the enforcement for
basic functions. Constants, methods and associated types are still
WIP.

Addresses: #440 

Co-authored-by: Philip Herron <philip.herron@embecosm.com>

10 files changed, 653 insertions, 19 deletions

diff --git a/gcc/rust/hir/tree/rust-hir-item.h b/gcc/rust/hir/tree/rust-hir-item.h
index 73c18d5..0cf71e7 100644
--- a/gcc/rust/hir/tree/rust-hir-item.h
+++ b/gcc/rust/hir/tree/rust-hir-item.h
@@ -2423,6 +2423,21 @@ public:
     rust_assert (is_method ());
     return self;
   }
+
+  Identifier get_function_name () const { return function_name; }
+
+  std::vector<std::unique_ptr<GenericParam> > &get_generic_params ()
+  {
+    return generic_params;
+  }
+
+  std::unique_ptr<Type> &get_return_type ()
+  {
+    rust_assert (has_return_type ());
+    return return_type;
+  }
+
+  std::vector<FunctionParam> &get_function_params () { return function_params; }
 };
 
 // Actual trait item function declaration within traits
@@ -2478,7 +2493,15 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
-  std::unique_ptr<Expr> &get_block_expr () { return block_expr; }
+  TraitFunctionDecl &get_decl () { return decl; }
+
+  bool has_block_defined () const { return block_expr != nullptr; }
+
+  std::unique_ptr<Expr> &get_block_expr ()
+  {
+    rust_assert (has_block_defined ());
+    return block_expr;
+  }
 
 protected:
   // Clone function implementation as (not pure) virtual method
@@ -2494,10 +2517,7 @@ class TraitItemConst : public TraitItem
   AST::AttrVec outer_attrs;
   Identifier name;
   std::unique_ptr<Type> type;
-
-  // bool has_expression;
   std::unique_ptr<Expr> expr;
-
   Location locus;
 
 public:
@@ -2543,6 +2563,18 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
+  Identifier get_name () const { return name; }
+
+  bool has_expr () const { return expr != nullptr; }
+
+  std::unique_ptr<Type> &get_type () { return type; }
+
+  std::unique_ptr<Expr> &get_expr ()
+  {
+    rust_assert (has_expr ());
+    return expr;
+  }
+
 protected:
   // Clone function implementation as (not pure) virtual method
   TraitItemConst *clone_trait_item_impl () const override
@@ -2557,12 +2589,8 @@ class TraitItemType : public TraitItem
   AST::AttrVec outer_attrs;
 
   Identifier name;
-
-  // bool has_type_param_bounds;
-  // TypeParamBounds type_param_bounds;
   std::vector<std::unique_ptr<TypeParamBound> >
     type_param_bounds; // inlined form
-
   Location locus;
 
 public:
@@ -2614,6 +2642,13 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
+  Identifier get_name () const { return name; }
+
+  std::vector<std::unique_ptr<TypeParamBound> > &get_type_param_bounds ()
+  {
+    return type_param_bounds;
+  }
+
 protected:
   // Clone function implementation as (not pure) virtual method
   TraitItemType *clone_trait_item_impl () const override
@@ -2661,6 +2696,13 @@ public:
   // Returns whether trait has trait items.
   bool has_trait_items () const { return !trait_items.empty (); }
 
+  std::vector<std::unique_ptr<TraitItem> > &get_trait_items ()
+  {
+    return trait_items;
+  }
+
+  Identifier get_name () const { return name; }
+
   // Mega-constructor
   Trait (Analysis::NodeMapping mappings, Identifier name, bool is_unsafe,
 	 std::vector<std::unique_ptr<GenericParam> > generic_params,
diff --git a/gcc/rust/typecheck/rust-hir-trait-ref.h b/gcc/rust/typecheck/rust-hir-trait-ref.h
new file mode 100644
index 0000000..96498a5
--- /dev/null
+++ b/gcc/rust/typecheck/rust-hir-trait-ref.h
@@ -0,0 +1,198 @@
+// Copyright (C) 2021 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_HIR_TRAIT_REF_H
+#define RUST_HIR_TRAIT_REF_H
+
+#include "rust-hir-full.h"
+#include "rust-tyty-visitor.h"
+
+namespace Rust {
+namespace Resolver {
+
+// Data Objects for the associated trait items in a structure we can work with
+// https://doc.rust-lang.org/edition-guide/rust-2018/trait-system/associated-constants.html
+class TraitItemReference
+{
+public:
+  enum TraitItemType
+  {
+    FN,
+    CONST,
+    TYPE,
+    ERROR
+  };
+
+  TraitItemReference (std::string identifier, bool optional, TraitItemType type,
+		      const HIR::TraitItem *hir_trait_item, TyTy::BaseType *ty,
+		      Location locus)
+    : identifier (identifier), optional_flag (optional), type (type),
+      hir_trait_item (hir_trait_item), ty (ty), locus (locus)
+  {}
+
+  TraitItemReference (TraitItemReference const &other)
+    : identifier (other.identifier), optional_flag (other.optional_flag),
+      type (other.type), hir_trait_item (other.hir_trait_item), ty (other.ty),
+      locus (other.locus)
+  {}
+
+  TraitItemReference &operator= (TraitItemReference const &other)
+  {
+    identifier = other.identifier;
+    optional_flag = other.optional_flag;
+    type = other.type;
+    hir_trait_item = other.hir_trait_item;
+    ty = other.ty;
+    locus = other.locus;
+
+    return *this;
+  }
+
+  TraitItemReference (TraitItemReference &&other) = default;
+  TraitItemReference &operator= (TraitItemReference &&other) = default;
+
+  static TraitItemReference error ()
+  {
+    return TraitItemReference ("", false, ERROR, nullptr, nullptr, Location ());
+  }
+
+  static TraitItemReference &error_node ()
+  {
+    static TraitItemReference error = TraitItemReference::error ();
+    return error;
+  }
+
+  bool is_error () const { return type == ERROR; }
+
+  std::string as_string () const
+  {
+    return "(" + trait_item_type_as_string (type) + " " + identifier + " "
+	   + ty->as_string () + ")";
+  }
+
+  static std::string trait_item_type_as_string (TraitItemType ty)
+  {
+    switch (ty)
+      {
+      case FN:
+	return "FN";
+      case CONST:
+	return "CONST";
+      case TYPE:
+	return "TYPE";
+      case ERROR:
+	return "ERROR";
+      }
+    return "ERROR";
+  }
+
+  bool is_optional () const { return optional_flag; }
+
+  std::string get_identifier () const { return identifier; }
+
+  TraitItemType get_trait_item_type () const { return type; }
+
+  const HIR::TraitItem *get_hir_trait_item () const { return hir_trait_item; }
+
+  TyTy::BaseType *get_tyty () const { return ty; }
+
+  Location get_locus () const { return locus; }
+
+private:
+  std::string identifier;
+  bool optional_flag;
+  TraitItemType type;
+  const HIR::TraitItem *hir_trait_item;
+  TyTy::BaseType *ty;
+  Location locus;
+};
+
+class TraitReference
+{
+public:
+  TraitReference (const HIR::Trait *hir_trait_ref,
+		  std::vector<TraitItemReference> item_refs)
+    : hir_trait_ref (hir_trait_ref), item_refs (item_refs)
+  {}
+
+  TraitReference (TraitReference const &other)
+    : hir_trait_ref (other.hir_trait_ref), item_refs (other.item_refs)
+  {}
+
+  TraitReference &operator= (TraitReference const &other)
+  {
+    hir_trait_ref = other.hir_trait_ref;
+    item_refs = other.item_refs;
+
+    return *this;
+  }
+
+  TraitReference (TraitReference &&other) = default;
+  TraitReference &operator= (TraitReference &&other) = default;
+
+  static TraitReference error () { return TraitReference (nullptr, {}); }
+
+  bool is_error () const { return hir_trait_ref == nullptr; }
+
+  Location get_locus () const { return hir_trait_ref->get_locus (); }
+
+  std::string get_name () const
+  {
+    rust_assert (!is_error ());
+    return hir_trait_ref->get_name ();
+  }
+
+  std::string as_string () const
+  {
+    if (is_error ())
+      return "<trait-ref-error-node>";
+
+    std::string item_buf;
+    for (auto &item : item_refs)
+      {
+	item_buf += item.as_string () + ", ";
+      }
+    return "HIR Trait: " + get_name () + "->"
+	   + hir_trait_ref->get_mappings ().as_string () + " [" + item_buf
+	   + "]";
+  }
+
+  const TraitItemReference &
+  lookup_trait_item (const std::string &ident,
+		     TraitItemReference::TraitItemType type) const
+  {
+    for (auto &item : item_refs)
+      {
+	if (item.get_trait_item_type () != type)
+	  continue;
+
+	if (ident.compare (item.get_identifier ()) == 0)
+	  return item;
+      }
+    return TraitItemReference::error_node ();
+  }
+
+private:
+  const HIR::Trait *hir_trait_ref;
+  std::vector<TraitItemReference> item_refs;
+};
+
+} // namespace Resolver
+} // namespace Rust
+
+#endif // RUST_HIR_TRAIT_REF_H
diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.h b/gcc/rust/typecheck/rust-hir-trait-resolve.h
new file mode 100644
index 0000000..2e358d3
--- /dev/null
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.h
@@ -0,0 +1,256 @@
+// Copyright (C) 2021 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_HIR_TRAIT_RESOLVE_H
+#define RUST_HIR_TRAIT_RESOLVE_H
+
+#include "rust-hir-type-check-base.h"
+#include "rust-hir-full.h"
+#include "rust-tyty-visitor.h"
+#include "rust-hir-type-check-type.h"
+#include "rust-hir-trait-ref.h"
+
+namespace Rust {
+namespace Resolver {
+
+class ResolveTraitItemToRef : public TypeCheckBase
+{
+  using Rust::Resolver::TypeCheckBase::visit;
+
+public:
+  static TraitItemReference Resolve (HIR::TraitItem &item)
+  {
+    ResolveTraitItemToRef resolver;
+    item.accept_vis (resolver);
+    return resolver.resolved;
+  }
+
+  void visit (HIR::TraitItemType &type) override
+  {
+    // associated types are not typed and only support bounds
+    TyTy::BaseType *ty = nullptr;
+
+    // create trait-item-ref
+    Location locus = type.get_locus ();
+    bool is_optional = false;
+    std::string identifier = type.get_name ();
+
+    resolved = TraitItemReference (identifier, is_optional,
+				   TraitItemReference::TraitItemType::TYPE,
+				   &type, ty, locus);
+  }
+
+  void visit (HIR::TraitItemConst &cst) override
+  {
+    // attempt to lookup the type of the trait item function
+    TyTy::BaseType *ty = nullptr;
+    if (!context->lookup_type (cst.get_mappings ().get_hirid (), &ty))
+      {
+	auto resolved = TypeCheckType::Resolve (cst.get_type ().get ());
+	if (resolved->get_kind () == TyTy::TypeKind::ERROR)
+	  {
+	    rust_error_at (cst.get_locus (),
+			   "failed to resolve trait constant type");
+	    return;
+	  }
+      }
+
+    // create trait-item-ref
+    Location locus = cst.get_locus ();
+    bool is_optional = cst.has_expr ();
+    std::string identifier = cst.get_name ();
+
+    resolved = TraitItemReference (identifier, is_optional,
+				   TraitItemReference::TraitItemType::CONST,
+				   &cst, ty, locus);
+  }
+
+  void visit (HIR::TraitItemFunc &fn) override
+  {
+    // FIXME this is duplicated in a few places and could be refactored
+
+    // attempt to lookup the type of the trait item function
+    TyTy::BaseType *ty = nullptr;
+    if (!context->lookup_type (fn.get_mappings ().get_hirid (), &ty))
+      {
+	HIR::TraitFunctionDecl &function = fn.get_decl ();
+	std::vector<TyTy::SubstitutionParamMapping> substitutions;
+	if (function.has_generics ())
+	  {
+	    for (auto &generic_param : function.get_generic_params ())
+	      {
+		switch (generic_param.get ()->get_kind ())
+		  {
+		  case HIR::GenericParam::GenericKind::LIFETIME:
+		    // Skipping Lifetime completely until better handling.
+		    break;
+
+		    case HIR::GenericParam::GenericKind::TYPE: {
+		      auto param_type = TypeResolveGenericParam::Resolve (
+			generic_param.get ());
+		      context->insert_type (generic_param->get_mappings (),
+					    param_type);
+
+		      substitutions.push_back (TyTy::SubstitutionParamMapping (
+			static_cast<HIR::TypeParam &> (*generic_param),
+			param_type));
+		    }
+		    break;
+		  }
+	      }
+	  }
+
+	TyTy::BaseType *ret_type = nullptr;
+	if (!function.has_return_type ())
+	  ret_type = new TyTy::TupleType (fn.get_mappings ().get_hirid ());
+	else
+	  {
+	    auto resolved
+	      = TypeCheckType::Resolve (function.get_return_type ().get ());
+	    if (resolved->get_kind () == TyTy::TypeKind::ERROR)
+	      {
+		rust_error_at (fn.get_locus (),
+			       "failed to resolve return type");
+		return;
+	      }
+
+	    ret_type = resolved->clone ();
+	    ret_type->set_ref (
+	      function.get_return_type ()->get_mappings ().get_hirid ());
+	  }
+
+	std::vector<std::pair<HIR::Pattern *, TyTy::BaseType *> > params;
+	for (auto &param : function.get_function_params ())
+	  {
+	    // get the name as well required for later on
+	    auto param_tyty = TypeCheckType::Resolve (param.get_type ());
+	    params.push_back (std::pair<HIR::Pattern *, TyTy::BaseType *> (
+	      param.get_param_name (), param_tyty));
+
+	    context->insert_type (param.get_mappings (), param_tyty);
+	  }
+
+	ty = new TyTy::FnType (fn.get_mappings ().get_hirid (),
+			       function.get_function_name (), false,
+			       std::move (params), ret_type,
+			       std::move (substitutions));
+	context->insert_type (fn.get_mappings (), ty);
+      }
+
+    // create trait-item-ref
+    Location locus = fn.get_locus ();
+    bool is_optional = fn.has_block_defined ();
+    std::string identifier = fn.get_decl ().get_function_name ();
+
+    resolved = TraitItemReference (identifier, is_optional,
+				   TraitItemReference::TraitItemType::FN, &fn,
+				   ty, locus);
+  }
+
+private:
+  ResolveTraitItemToRef ()
+    : TypeCheckBase (), resolved (TraitItemReference::error ())
+  {}
+
+  TraitItemReference resolved;
+};
+
+class TraitResolver : public TypeCheckBase
+{
+  using Rust::Resolver::TypeCheckBase::visit;
+
+public:
+  static TraitReference &Resolve (HIR::TypePath &path)
+  {
+    TraitResolver resolver;
+    return resolver.go (path);
+  }
+
+  static TraitReference &error_node ()
+  {
+    static TraitReference trait_error_node = TraitReference::error ();
+    return trait_error_node;
+  }
+
+private:
+  TraitResolver () : TypeCheckBase () {}
+
+  TraitReference &go (HIR::TypePath &path)
+  {
+    NodeId ref;
+    if (!resolver->lookup_resolved_type (path.get_mappings ().get_nodeid (),
+					 &ref))
+      {
+	rust_fatal_error (path.get_locus (),
+			  "Failed to resolve path to node-id");
+	return error_node ();
+      }
+
+    HirId hir_node = UNKNOWN_HIRID;
+    if (!mappings->lookup_node_to_hir (mappings->get_current_crate (), ref,
+				       &hir_node))
+      {
+	rust_fatal_error (path.get_locus (),
+			  "Failed to resolve path to hir-id");
+	return error_node ();
+      }
+
+    HIR::Item *resolved_item
+      = mappings->lookup_hir_item (mappings->get_current_crate (), hir_node);
+
+    rust_assert (resolved_item != nullptr);
+    resolved_item->accept_vis (*this);
+    rust_assert (trait_reference != nullptr);
+
+    TraitReference &tref = error_node ();
+    if (context->lookup_trait_reference (
+	  trait_reference->get_mappings ().get_defid (), tref))
+      {
+	return tref;
+      }
+
+    std::vector<TraitItemReference> item_refs;
+    for (auto &item : trait_reference->get_trait_items ())
+      {
+	TraitItemReference trait_item_ref
+	  = ResolveTraitItemToRef::Resolve (*item.get ());
+	item_refs.push_back (std::move (trait_item_ref));
+      }
+
+    tref = TraitReference (trait_reference, item_refs);
+    context->insert_trait_reference (
+      trait_reference->get_mappings ().get_defid (), std::move (tref));
+
+    tref = error_node ();
+    bool ok = context->lookup_trait_reference (
+      trait_reference->get_mappings ().get_defid (), tref);
+    rust_assert (ok);
+
+    return tref;
+  }
+
+  HIR::Trait *trait_reference;
+
+public:
+  void visit (HIR::Trait &trait) override { trait_reference = &trait; }
+};
+
+} // namespace Resolver
+} // namespace Rust
+
+#endif // RUST_HIR_TRAIT_RESOLVE_H
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.h b/gcc/rust/typecheck/rust-hir-type-check-expr.h
index bdebfd3..e06b10d 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.h
@@ -915,7 +915,9 @@ public:
 	auto candidates = PathProbeType::Probe (tyseg, seg.get_segment ());
 	if (candidates.size () == 0)
 	  {
-	    rust_error_at (seg.get_locus (), "failed to resolve path segment");
+	    rust_error_at (
+	      seg.get_locus (),
+	      "failed to resolve path segment using an impl Probe");
 	    return;
 	  }
 	else if (candidates.size () > 1)
diff --git a/gcc/rust/typecheck/rust-hir-type-check-implitem.h b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
index 46fee29..75ba095 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-implitem.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-implitem.h
@@ -207,13 +207,13 @@ private:
 
   TyTy::BaseType *self;
   std::vector<TyTy::SubstitutionParamMapping> substitutions;
-}; // namespace Resolver
+};
 
 class TypeCheckImplItem : public TypeCheckBase
 {
+public:
   using Rust::Resolver::TypeCheckBase::visit;
 
-public:
   static void Resolve (HIR::ImplItem *item, TyTy::BaseType *self)
   {
     TypeCheckImplItem resolver (self);
@@ -238,7 +238,7 @@ public:
       }
 
     // need to get the return type from this
-    TyTy::FnType *resolve_fn_type = (TyTy::FnType *) lookup;
+    TyTy::FnType *resolve_fn_type = static_cast<TyTy::FnType *> (lookup);
     auto expected_ret_tyty = resolve_fn_type->get_return_type ();
     context->push_return_type (expected_ret_tyty);
 
@@ -246,7 +246,6 @@ public:
       = TypeCheckExpr::Resolve (function.get_definition ().get (), false);
 
     context->pop_return_type ();
-
     expected_ret_tyty->unify (block_expr_ty);
   }
 
@@ -280,12 +279,91 @@ public:
     expected_ret_tyty->unify (block_expr_ty);
   }
 
-private:
+protected:
   TypeCheckImplItem (TyTy::BaseType *self) : TypeCheckBase (), self (self) {}
 
   TyTy::BaseType *self;
 };
 
+class TypeCheckImplItemWithTrait : public TypeCheckImplItem
+{
+  using Rust::Resolver::TypeCheckBase::visit;
+
+public:
+  static const TraitItemReference &Resolve (HIR::ImplItem *item,
+					    TyTy::BaseType *self,
+					    TraitReference &trait_reference)
+  {
+    TypeCheckImplItemWithTrait resolver (self, trait_reference);
+    item->accept_vis (resolver);
+    return resolver.resolved_trait_item;
+  }
+
+  void visit (HIR::ConstantItem &constant) override { gcc_unreachable (); }
+
+  void visit (HIR::TypeAlias &type) override { gcc_unreachable (); }
+
+  void visit (HIR::Method &method) override { gcc_unreachable (); }
+
+  void visit (HIR::Function &function) override
+  {
+    TypeCheckImplItem::visit (function);
+
+    // we get the error checking from the base method here
+    TyTy::BaseType *lookup;
+    if (!context->lookup_type (function.get_mappings ().get_hirid (), &lookup))
+      return;
+
+    if (lookup->get_kind () != TyTy::TypeKind::FNDEF)
+      return;
+
+    TyTy::FnType *fntype = static_cast<TyTy::FnType *> (lookup);
+    const TraitItemReference &trait_item_ref
+      = trait_reference.lookup_trait_item (
+	fntype->get_identifier (), TraitItemReference::TraitItemType::FN);
+
+    // unknown trait item
+    if (trait_item_ref.is_error ())
+      {
+	RichLocation r (function.get_locus ());
+	r.add_range (trait_reference.get_locus ());
+	rust_error_at (r, "method %<%s%> is not a member of trait %<%s%>",
+		       fntype->get_identifier ().c_str (),
+		       trait_reference.get_name ().c_str ());
+	return;
+      }
+
+    // check the types are compatible
+    if (!trait_item_ref.get_tyty ()->can_eq (fntype))
+      {
+	RichLocation r (function.get_locus ());
+	r.add_range (trait_item_ref.get_locus ());
+
+	rust_error_at (
+	  r, "method %<%s%> has an incompatible type for trait %<%s%>",
+	  fntype->get_identifier ().c_str (),
+	  trait_reference.get_name ().c_str ());
+	return;
+      }
+
+    resolved_trait_item = trait_item_ref;
+  }
+
+private:
+  TypeCheckImplItemWithTrait (TyTy::BaseType *self,
+			      TraitReference &trait_reference)
+    : TypeCheckImplItem (self), trait_reference (trait_reference),
+      resolved_trait_item (TraitItemReference::error_node ())
+  {
+    rust_assert (is_trait_impl_block ());
+  }
+
+  bool is_trait_impl_block () const { return !trait_reference.is_error (); }
+
+  TraitReference &trait_reference;
+  TraitItemReference &resolved_trait_item;
+};
+
 } // namespace Resolver
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check-item.h b/gcc/rust/typecheck/rust-hir-type-check-item.h
index 5220101..0126ded 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-item.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-item.h
@@ -24,6 +24,7 @@
 #include "rust-hir-type-check-implitem.h"
 #include "rust-hir-type-check-type.h"
 #include "rust-hir-type-check-stmt.h"
+#include "rust-hir-trait-resolve.h"
 #include "rust-tyty-visitor.h"
 
 namespace Rust {
@@ -42,6 +43,14 @@ public:
 
   void visit (HIR::ImplBlock &impl_block) override
   {
+    TraitReference &trait_reference = TraitResolver::error_node ();
+    if (impl_block.has_trait_ref ())
+      {
+	std::unique_ptr<HIR::TypePath> &ref = impl_block.get_trait_ref ();
+	trait_reference = TraitResolver::Resolve (*ref.get ());
+	rust_assert (!trait_reference.is_error ());
+      }
+
     TyTy::BaseType *self = nullptr;
     if (!context->lookup_type (
 	  impl_block.get_type ()->get_mappings ().get_hirid (), &self))
@@ -52,7 +61,13 @@ public:
       }
 
     for (auto &impl_item : impl_block.get_impl_items ())
-      TypeCheckImplItem::Resolve (impl_item.get (), self);
+      {
+	if (trait_reference.is_error ())
+	  TypeCheckImplItem::Resolve (impl_item.get (), self);
+	else
+	  TypeCheckImplItemWithTrait::Resolve (impl_item.get (), self,
+					       trait_reference);
+      }
   }
 
   void visit (HIR::Function &function) override
diff --git a/gcc/rust/typecheck/rust-hir-type-check.h b/gcc/rust/typecheck/rust-hir-type-check.h
index 9bc3f3a..0298068 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.h
+++ b/gcc/rust/typecheck/rust-hir-type-check.h
@@ -22,6 +22,7 @@
 #include "rust-hir-full-decls.h"
 #include "rust-hir-map.h"
 #include "rust-tyty.h"
+#include "rust-hir-trait-ref.h"
 
 namespace Rust {
 namespace Resolver {
@@ -85,14 +86,31 @@ public:
     loop_type_stack.push_back (val);
   }
 
+  void insert_trait_reference (DefId id, TraitReference &&ref)
+  {
+    rust_assert (trait_context.find (id) == trait_context.end ());
+    trait_context.emplace (id, std::move (ref));
+  }
+
+  bool lookup_trait_reference (DefId id, TraitReference &ref)
+  {
+    auto it = trait_context.find (id);
+    if (it == trait_context.end ())
+      return false;
+
+    ref = it->second;
+    return true;
+  }
+
 private:
   TypeCheckContext ();
 
   std::map<NodeId, HirId> node_id_refs;
   std::map<HirId, TyTy::BaseType *> resolved;
-  std::vector<std::unique_ptr<TyTy::BaseType> > builtins;
+  std::vector<std::unique_ptr<TyTy::BaseType>> builtins;
   std::vector<TyTy::BaseType *> return_type_stack;
   std::vector<TyTy::BaseType *> loop_type_stack;
+  std::map<DefId, TraitReference> trait_context;
 };
 
 class TypeResolution
diff --git a/gcc/rust/typecheck/rust-tyty-cmp.h b/gcc/rust/typecheck/rust-tyty-cmp.h
index 1641264..c3a9742 100644
--- a/gcc/rust/typecheck/rust-tyty-cmp.h
+++ b/gcc/rust/typecheck/rust-tyty-cmp.h
@@ -349,7 +349,7 @@ public:
 	auto b = type.param_at (i).second;
 
 	auto unified_param = a->unify (b);
-	if (unified_param == nullptr)
+	if (unified_param->get_kind () == TypeKind::ERROR)
 	  {
 	    BaseCmp::visit (type);
 	    return;
@@ -358,7 +358,7 @@ public:
 
     auto unified_return
       = base->get_return_type ()->unify (type.get_return_type ());
-    if (unified_return == nullptr)
+    if (unified_return->get_kind () == TypeKind::ERROR)
       {
 	BaseCmp::visit (type);
 	return;
@@ -477,7 +477,7 @@ public:
     // check base type
     auto base_resolved
       = base->get_element_type ()->unify (type.get_element_type ());
-    if (base_resolved == nullptr)
+    if (base_resolved->get_kind () == TypeKind::ERROR)
       {
 	BaseCmp::visit (type);
 	return;
diff --git a/gcc/testsuite/rust/compile/traits1.rs b/gcc/testsuite/rust/compile/traits1.rs
new file mode 100644
index 0000000..30483b1
--- /dev/null
+++ b/gcc/testsuite/rust/compile/traits1.rs
@@ -0,0 +1,12 @@
+trait Foo {
+    fn Bar() -> i32 {}
+}
+
+struct Baz;
+
+impl Foo for Baz {
+    fn Barrr() {}
+    // { dg-error "method .Barrr. is not a member of trait .Foo." "" { target *-*-* } .-1 }
+}
+
+fn main() {}
diff --git a/gcc/testsuite/rust/compile/traits2.rs b/gcc/testsuite/rust/compile/traits2.rs
new file mode 100644
index 0000000..08e6bd3
--- /dev/null
+++ b/gcc/testsuite/rust/compile/traits2.rs
@@ -0,0 +1,13 @@
+trait Foo {
+    fn Bar() -> i32 {}
+}
+
+struct Baz;
+
+impl Foo for Baz {
+    fn Bar() {}
+    // { dg-error "expected .i32. got .()." "" { target *-*-* } .-1 }
+    // { dg-error "method .Bar. has an incompatible type for trait .Foo." "" { target *-*-* } .-2 }
+}
+
+fn main() {}