Add TyTy::BaseType::can_eq method to tyty module

When we are probing paths we dont want to unify types as we are testing
to find something so a can_eq method simialr to unify but does not throw
errors allows for testing if types could be compatible.

3 files changed, 1004 insertions, 11 deletions

diff --git a/gcc/rust/typecheck/rust-tyty-cmp.h b/gcc/rust/typecheck/rust-tyty-cmp.h
new file mode 100644
index 0000000..e2e0d08
--- /dev/null
+++ b/gcc/rust/typecheck/rust-tyty-cmp.h
@@ -0,0 +1,812 @@
+// Copyright (C) 2020 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_TYTY_CMP_H
+#define RUST_TYTY_CMP_H
+
+#include "rust-diagnostics.h"
+#include "rust-tyty.h"
+#include "rust-tyty-visitor.h"
+#include "rust-hir-map.h"
+#include "rust-hir-type-check.h"
+
+namespace Rust {
+namespace TyTy {
+
+class BaseCmp : public TyVisitor
+{
+public:
+  virtual bool can_eq (BaseType *other)
+  {
+    if (other->get_kind () == TypeKind::PARAM)
+      {
+	ParamType *p = static_cast<ParamType *> (other);
+	if (p->can_resolve ())
+	  {
+	    other = p->resolve ();
+	  }
+      }
+
+    other->accept_vis (*this);
+    return ok;
+  }
+
+  virtual void visit (TupleType &) override { ok = false; }
+
+  virtual void visit (ADTType &) override { ok = false; }
+
+  virtual void visit (InferType &) override { ok = false; }
+
+  virtual void visit (FnType &) override { ok = false; }
+
+  virtual void visit (FnPtr &) override { ok = false; }
+
+  virtual void visit (ArrayType &) override { ok = false; }
+
+  virtual void visit (BoolType &) override { ok = false; }
+
+  virtual void visit (IntType &) override { ok = false; }
+
+  virtual void visit (UintType &) override { ok = false; }
+
+  virtual void visit (USizeType &) override { ok = false; }
+
+  virtual void visit (ISizeType &) override { ok = false; }
+
+  virtual void visit (FloatType &) override { ok = false; }
+
+  virtual void visit (ErrorType &) override { ok = false; }
+
+  virtual void visit (CharType &) override { ok = false; }
+
+  virtual void visit (ReferenceType &) override { ok = false; }
+
+  virtual void visit (ParamType &) override
+  {
+    // it is ok for types to can eq to a ParamType
+    ok = true;
+  }
+
+  virtual void visit (StrType &) override { ok = false; }
+
+protected:
+  BaseCmp (BaseType *base)
+    : mappings (Analysis::Mappings::get ()),
+      context (Resolver::TypeCheckContext::get ()), ok (false)
+  {}
+
+  Analysis::Mappings *mappings;
+  Resolver::TypeCheckContext *context;
+
+  bool ok;
+
+private:
+  /* Returns a pointer to the ty that created this rule. */
+  virtual BaseType *get_base () = 0;
+};
+
+class InferCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  InferCmp (InferType *base) : BaseCmp (base), base (base) {}
+
+  void visit (BoolType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (IntType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
+	|| (base->get_infer_kind ()
+	    == TyTy::InferType::InferTypeKind::INTEGRAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (UintType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
+	|| (base->get_infer_kind ()
+	    == TyTy::InferType::InferTypeKind::INTEGRAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (USizeType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
+	|| (base->get_infer_kind ()
+	    == TyTy::InferType::InferTypeKind::INTEGRAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (ISizeType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
+	|| (base->get_infer_kind ()
+	    == TyTy::InferType::InferTypeKind::INTEGRAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (FloatType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL)
+	|| (base->get_infer_kind () == TyTy::InferType::InferTypeKind::FLOAT);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (ArrayType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (ADTType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (TupleType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (InferType &type) override
+  {
+    switch (base->get_infer_kind ())
+      {
+      case InferType::InferTypeKind::GENERAL:
+	ok = true;
+	return;
+
+	case InferType::InferTypeKind::INTEGRAL: {
+	  if (type.get_infer_kind () == InferType::InferTypeKind::INTEGRAL)
+	    {
+	      ok = true;
+	      return;
+	    }
+	  else if (type.get_infer_kind () == InferType::InferTypeKind::GENERAL)
+	    {
+	      ok = true;
+	      return;
+	    }
+	}
+	break;
+
+	case InferType::InferTypeKind::FLOAT: {
+	  if (type.get_infer_kind () == InferType::InferTypeKind::FLOAT)
+	    {
+	      ok = true;
+	      return;
+	    }
+	  else if (type.get_infer_kind () == InferType::InferTypeKind::GENERAL)
+	    {
+	      ok = true;
+	      return;
+	    }
+	}
+	break;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (CharType &type) override
+  {
+    {
+      bool is_valid
+	= (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+      if (is_valid)
+	{
+	  ok = true;
+	  return;
+	}
+
+      BaseCmp::visit (type);
+    }
+  }
+
+  void visit (ReferenceType &type) override
+
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+  void visit (ParamType &type) override
+  {
+    bool is_valid
+      = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+    if (is_valid)
+      {
+	ok = true;
+	return;
+      }
+
+    BaseCmp::visit (type);
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  InferType *base;
+};
+
+class FnCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  FnCmp (FnType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () == InferType::InferTypeKind::GENERAL;
+  }
+
+  void visit (FnType &type) override
+  {
+    if (base->num_params () != type.num_params ())
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    for (size_t i = 0; i < base->num_params (); i++)
+      {
+	auto a = base->param_at (i).second;
+	auto b = type.param_at (i).second;
+
+	auto unified_param = a->unify (b);
+	if (unified_param == nullptr)
+	  {
+	    BaseCmp::visit (type);
+	    return;
+	  }
+      }
+
+    auto unified_return
+      = base->get_return_type ()->unify (type.get_return_type ());
+    if (unified_return == nullptr)
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    ok = true;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  FnType *base;
+};
+
+class FnptrCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  FnptrCmp (FnPtr *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    if (type.get_infer_kind () != InferType::InferTypeKind::GENERAL)
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    ok = true;
+  }
+
+  void visit (FnPtr &type) override
+  {
+    auto this_ret_type = base->get_return_type ();
+    auto other_ret_type = type.get_return_type ();
+    auto unified_result = this_ret_type->unify (other_ret_type);
+    if (unified_result == nullptr
+	|| unified_result->get_kind () == TypeKind::ERROR)
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    if (base->num_params () != type.num_params ())
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    for (size_t i = 0; i < base->num_params (); i++)
+      {
+	auto this_param = base->param_at (i);
+	auto other_param = type.param_at (i);
+	auto unified_param = this_param->unify (other_param);
+	if (unified_param == nullptr
+	    || unified_param->get_kind () == TypeKind::ERROR)
+	  {
+	    BaseCmp::visit (type);
+	    return;
+	  }
+      }
+
+    ok = true;
+  }
+
+  void visit (FnType &type) override
+  {
+    auto this_ret_type = base->get_return_type ();
+    auto other_ret_type = type.get_return_type ();
+    auto unified_result = this_ret_type->unify (other_ret_type);
+    if (unified_result == nullptr
+	|| unified_result->get_kind () == TypeKind::ERROR)
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    if (base->num_params () != type.num_params ())
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    for (size_t i = 0; i < base->num_params (); i++)
+      {
+	auto this_param = base->param_at (i);
+	auto other_param = type.param_at (i).second;
+	auto unified_param = this_param->unify (other_param);
+	if (unified_param == nullptr
+	    || unified_param->get_kind () == TypeKind::ERROR)
+	  {
+	    BaseCmp::visit (type);
+	    return;
+	  }
+      }
+
+    ok = true;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  FnPtr *base;
+};
+
+class ArrayCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  ArrayCmp (ArrayType *base) : BaseCmp (base), base (base) {}
+
+  void visit (ArrayType &type) override
+  {
+    // check base type
+    auto base_resolved
+      = base->get_element_type ()->unify (type.get_element_type ());
+    if (base_resolved == nullptr)
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    // need to check the base types and capacity
+    if (type.get_capacity () != base->get_capacity ())
+      {
+	Location locus = mappings->lookup_location (type.get_ref ());
+	rust_error_at (locus, "mismatch in array capacity");
+	BaseCmp::visit (type);
+	return;
+      }
+
+    ok = true;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  ArrayType *base;
+};
+
+class BoolCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  BoolCmp (BoolType *base) : BaseCmp (base), base (base) {}
+
+  void visit (BoolType &type) override { ok = true; }
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () == InferType::InferTypeKind::GENERAL;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  BoolType *base;
+};
+
+class IntCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  IntCmp (IntType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
+  }
+
+  void visit (IntType &type) override
+  {
+    ok = type.get_int_kind () == base->get_int_kind ();
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  IntType *base;
+};
+
+class UintCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  UintCmp (UintType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
+  }
+
+  void visit (UintType &type) override
+  {
+    ok = type.get_uint_kind () == base->get_uint_kind ();
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  UintType *base;
+};
+
+class FloatCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  FloatCmp (FloatType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () != InferType::InferTypeKind::INTEGRAL;
+  }
+
+  void visit (FloatType &type) override
+  {
+    ok = type.get_float_kind () == base->get_float_kind ();
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  FloatType *base;
+};
+
+class ADTCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  ADTCmp (ADTType *base) : BaseCmp (base), base (base) {}
+
+  void visit (ADTType &type) override
+  {
+    if (base->get_identifier ().compare (type.get_identifier ()) != 0)
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    if (base->num_fields () != type.num_fields ())
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    for (size_t i = 0; i < type.num_fields (); ++i)
+      {
+	TyTy::StructFieldType *base_field = base->get_field (i);
+	TyTy::StructFieldType *other_field = type.get_field (i);
+
+	TyTy::BaseType *this_field_ty = base_field->get_field_type ();
+	TyTy::BaseType *other_field_ty = other_field->get_field_type ();
+
+	if (!this_field_ty->can_eq (other_field_ty))
+	  {
+	    BaseCmp::visit (type);
+	    return;
+	  }
+      }
+
+    ok = true;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  ADTType *base;
+};
+
+class TupleCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  TupleCmp (TupleType *base) : BaseCmp (base), base (base) {}
+
+  void visit (TupleType &type) override
+  {
+    if (base->num_fields () != type.num_fields ())
+      {
+	BaseCmp::visit (type);
+	return;
+      }
+
+    for (size_t i = 0; i < base->num_fields (); i++)
+      {
+	BaseType *bo = base->get_field (i);
+	BaseType *fo = type.get_field (i);
+
+	if (!bo->can_eq (fo))
+	  {
+	    BaseCmp::visit (type);
+	    return;
+	  }
+      }
+
+    ok = true;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  TupleType *base;
+};
+
+class USizeCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  USizeCmp (USizeType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
+  }
+
+  void visit (USizeType &type) override { ok = true; }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  USizeType *base;
+};
+
+class ISizeCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  ISizeCmp (ISizeType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () != InferType::InferTypeKind::FLOAT;
+  }
+
+  void visit (ISizeType &type) override { ok = true; }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  ISizeType *base;
+};
+
+class CharCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  CharCmp (CharType *base) : BaseCmp (base), base (base) {}
+
+  void visit (InferType &type) override
+  {
+    ok = type.get_infer_kind () == InferType::InferTypeKind::GENERAL;
+  }
+
+  void visit (CharType &type) override { ok = true; }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  CharType *base;
+};
+
+class ReferenceCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  ReferenceCmp (ReferenceType *base) : BaseCmp (base), base (base) {}
+
+  void visit (ReferenceType &type) override
+  {
+    auto base_type = base->get_base ();
+    auto other_base_type = type.get_base ();
+
+    ok = base_type->can_eq (other_base_type);
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  ReferenceType *base;
+};
+
+class ParamCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  ParamCmp (ParamType *base) : BaseCmp (base), base (base) {}
+
+  // param types are a placeholder we shouldn't have cases where we unify
+  // against it. eg: struct foo<T> { a: T }; When we invoke it we can do either:
+  //
+  // foo<i32>{ a: 123 }.
+  // Then this enforces the i32 type to be referenced on the
+  // field via an hirid.
+  //
+  // rust also allows for a = foo{a:123}; Where we can use an Inference Variable
+  // to handle the typing of the struct
+  bool can_eq (BaseType *other) override final
+  {
+    if (base->get_ref () == base->get_ty_ref ())
+      return BaseCmp::can_eq (other);
+
+    auto context = Resolver::TypeCheckContext::get ();
+    BaseType *lookup = nullptr;
+    bool ok = context->lookup_type (base->get_ty_ref (), &lookup);
+    rust_assert (ok);
+
+    return lookup->can_eq (other);
+  }
+
+  void visit (ParamType &type) override
+  {
+    ok = base->get_symbol ().compare (type.get_symbol ()) == 0;
+  }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  ParamType *base;
+};
+
+class StrCmp : public BaseCmp
+{
+  // FIXME we will need a enum for the StrType like ByteBuf etc..
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  StrCmp (StrType *base) : BaseCmp (base), base (base) {}
+
+  void visit (StrType &type) override { ok = true; }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  StrType *base;
+};
+
+} // namespace TyTy
+} // namespace Rust
+
+#endif // RUST_TYTY_CMP_H
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index cb0543c..8f2faec 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -22,6 +22,7 @@
 #include "rust-hir-type-check-expr.h"
 #include "rust-hir-type-check-type.h"
 #include "rust-tyty-rules.h"
+#include "rust-tyty-cmp.h"
 #include "rust-hir-map.h"
 #include "rust-substitution-mapper.h"
 
@@ -91,6 +92,13 @@ InferType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+InferType::can_eq (BaseType *other)
+{
+  InferCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 InferType::clone ()
 {
@@ -107,11 +115,13 @@ InferType::default_type (BaseType **type) const
     {
     case GENERAL:
       return false;
+
       case INTEGRAL: {
 	ok = context->lookup_builtin ("i32", type);
 	rust_assert (ok);
 	return ok;
       }
+
       case FLOAT: {
 	ok = context->lookup_builtin ("f64", type);
 	rust_assert (ok);
@@ -139,6 +149,12 @@ ErrorType::unify (BaseType *other)
   return this;
 }
 
+bool
+ErrorType::can_eq (BaseType *other)
+{
+  return get_kind () == other->get_kind ();
+}
+
 BaseType *
 ErrorType::clone ()
 {
@@ -304,6 +320,13 @@ ADTType::unify (BaseType *other)
 }
 
 bool
+ADTType::can_eq (BaseType *other)
+{
+  ADTCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 ADTType::is_equal (const BaseType &other) const
 {
   if (get_kind () != other.get_kind ())
@@ -418,8 +441,7 @@ ADTType::handle_substitions (SubstitutionArgumentMappings subst_mappings)
 	BaseType *concrete
 	  = Resolver::SubstMapperInternal::Resolve (fty, subst_mappings);
 
-	if (concrete == nullptr
-	    || concrete->get_kind () == TyTy::TypeKind::ERROR)
+	if (concrete->get_kind () == TyTy::TypeKind::ERROR)
 	  {
 	    rust_error_at (subst_mappings.get_locus (),
 			   "Failed to resolve field substitution type: %s",
@@ -470,6 +492,13 @@ TupleType::unify (BaseType *other)
 }
 
 bool
+TupleType::can_eq (BaseType *other)
+{
+  TupleCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 TupleType::is_equal (const BaseType &other) const
 {
   if (get_kind () != other.get_kind ())
@@ -524,6 +553,13 @@ FnType::unify (BaseType *other)
 }
 
 bool
+FnType::can_eq (BaseType *other)
+{
+  FnCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 FnType::is_equal (const BaseType &other) const
 {
   if (get_kind () != other.get_kind ())
@@ -713,6 +749,13 @@ FnPtr::unify (BaseType *other)
 }
 
 bool
+FnPtr::can_eq (BaseType *other)
+{
+  FnptrCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 FnPtr::is_equal (const BaseType &other) const
 {
   if (get_kind () != other.get_kind ())
@@ -767,6 +810,13 @@ ArrayType::unify (BaseType *other)
 }
 
 bool
+ArrayType::can_eq (BaseType *other)
+{
+  ArrayCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 ArrayType::is_equal (const BaseType &other) const
 {
   if (get_kind () != other.get_kind ())
@@ -814,6 +864,13 @@ BoolType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+BoolType::can_eq (BaseType *other)
+{
+  BoolCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 BoolType::clone ()
 {
@@ -853,6 +910,13 @@ IntType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+IntType::can_eq (BaseType *other)
+{
+  IntCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 IntType::clone ()
 {
@@ -903,6 +967,13 @@ UintType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+UintType::can_eq (BaseType *other)
+{
+  UintCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 UintType::clone ()
 {
@@ -947,6 +1018,13 @@ FloatType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+FloatType::can_eq (BaseType *other)
+{
+  FloatCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 FloatType::clone ()
 {
@@ -983,6 +1061,13 @@ USizeType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+USizeType::can_eq (BaseType *other)
+{
+  USizeCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 USizeType::clone ()
 {
@@ -1008,6 +1093,13 @@ ISizeType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+ISizeType::can_eq (BaseType *other)
+{
+  ISizeCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 ISizeType::clone ()
 {
@@ -1033,6 +1125,13 @@ CharType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+CharType::can_eq (BaseType *other)
+{
+  CharCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 CharType::clone ()
 {
@@ -1059,6 +1158,13 @@ ReferenceType::unify (BaseType *other)
 }
 
 bool
+ReferenceType::can_eq (BaseType *other)
+{
+  ReferenceCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 ReferenceType::is_equal (const BaseType &other) const
 {
   if (get_kind () != other.get_kind ())
@@ -1110,6 +1216,13 @@ ParamType::unify (BaseType *other)
   return r.unify (other);
 }
 
+bool
+ParamType::can_eq (BaseType *other)
+{
+  ParamCmp r (this);
+  return r.can_eq (other);
+}
+
 BaseType *
 ParamType::clone ()
 {
@@ -1179,6 +1292,13 @@ StrType::unify (BaseType *other)
 }
 
 bool
+StrType::can_eq (BaseType *other)
+{
+  StrCmp r (this);
+  return r.can_eq (other);
+}
+
+bool
 StrType::is_equal (const BaseType &other) const
 {
   return get_kind () == other.get_kind ();
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 9cf75fa..c428c4c 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -75,15 +75,20 @@ public:
 
   virtual std::string get_name () const = 0;
 
-  /* Unify two types. Returns a pointer to the newly-created unified ty, or
-     nullptr if the two ty cannot be unified. The caller is responsible for
-     releasing the memory of the returned ty. */
+  // Unify two types. Returns a pointer to the newly-created unified ty, or
+  // nullptr if the two ty cannot be unified. The caller is responsible for
+  // releasing the memory of the returned ty. using ignore_errors alows for a
+  // can_eq style unification
   virtual BaseType *unify (BaseType *other) = 0;
 
-  /* Check value equality between two ty. Type inference rules are ignored. Two
-     ty are considered equal if they're of the same kind, and
-       1. (For ADTs, arrays, tuples, refs) have the same underlying ty
-       2. (For functions) have the same signature */
+  // similar to unify but does not actually perform type unification but
+  // determines whether they are compatible
+  virtual bool can_eq (BaseType *other) = 0;
+
+  // Check value equality between two ty. Type inference rules are ignored. Two
+  //   ty are considered equal if they're of the same kind, and
+  //     1. (For ADTs, arrays, tuples, refs) have the same underlying ty
+  //     2. (For functions) have the same signature
   virtual bool is_equal (const BaseType &other) const
   {
     return get_kind () == other.get_kind ();
@@ -113,6 +118,8 @@ public:
     return supports_substitutions () && has_subsititions_defined ();
   }
 
+  virtual bool needs_generic_substitutions () const { return false; }
+
   std::string mappings_str () const
   {
     std::string buffer = "Ref: " + std::to_string (get_ref ())
@@ -129,7 +136,11 @@ public:
     return as_string () + ":" + mappings_str ();
   }
 
-  void debug () const { printf ("%s\n", debug_str ().c_str ()); }
+  void debug () const
+  {
+    printf ("[%p] %s\n", static_cast<const void *> (this),
+	    debug_str ().c_str ());
+  }
 
 protected:
   BaseType (HirId ref, HirId ty_ref, TypeKind kind,
@@ -188,6 +199,8 @@ public:
 
   BaseType *unify (BaseType *other) override;
 
+  bool can_eq (BaseType *other) override;
+
   BaseType *clone () final override;
 
   InferTypeKind get_infer_kind () const { return infer_kind; }
@@ -220,6 +233,7 @@ public:
   std::string as_string () const override;
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   BaseType *clone () final override;
 
@@ -246,6 +260,7 @@ public:
   std::string as_string () const override;
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   BaseType *clone () final override;
 
@@ -316,6 +331,7 @@ public:
   std::string as_string () const override;
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -419,6 +435,12 @@ public:
 
   static SubstitutionArg error () { return SubstitutionArg (nullptr, nullptr); }
 
+  bool is_conrete () const
+  {
+    return argument != nullptr && argument->get_kind () != TyTy::TypeKind::ERROR
+	   && argument->get_kind () != TyTy::TypeKind::PARAM;
+  }
+
   std::string as_string () const
   {
     return param->as_string () + ":" + argument->as_string ();
@@ -473,6 +495,19 @@ public:
     return false;
   }
 
+  // is_concrete means if the used args is non error, ie: non empty this will
+  // verify if actual real types have been put in place of are they still
+  // ParamTy
+  bool is_concrete () const
+  {
+    for (auto &mapping : mappings)
+      {
+	if (!mapping.is_conrete ())
+	  return false;
+      }
+    return true;
+  }
+
   Location get_locus () { return locus; }
 
   size_t size () const { return mappings.size (); }
@@ -543,7 +578,8 @@ public:
 
   bool needs_substitution () const
   {
-    return has_substitutions () && used_arguments.is_error ();
+    return has_substitutions ()
+	   && (used_arguments.is_error () || !used_arguments.is_concrete ());
   }
 
   bool was_substituted () const { return !needs_substitution (); }
@@ -622,11 +658,14 @@ public:
   std::string as_string () const override;
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;
 
   size_t num_fields () const { return fields.size (); }
 
+  std::string get_identifier () const { return identifier; }
+
   std::string get_name () const override final
   {
     return identifier + subst_as_string ();
@@ -671,6 +710,11 @@ public:
       }
   }
 
+  bool needs_generic_substitutions () const override final
+  {
+    return needs_substitution ();
+  }
+
   bool supports_substitutions () const override final { return true; }
 
   bool has_subsititions_defined () const override final
@@ -716,6 +760,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -745,6 +790,11 @@ public:
 
   BaseType *clone () final override;
 
+  bool needs_generic_substitutions () const override final
+  {
+    return needs_substitution ();
+  }
+
   bool supports_substitutions () const override final { return true; }
 
   bool has_subsititions_defined () const override final
@@ -788,6 +838,7 @@ public:
   std::string as_string () const override;
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -829,6 +880,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -866,6 +918,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   BaseType *clone () final override;
 };
@@ -898,6 +951,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   IntKind get_int_kind () const { return int_kind; }
 
@@ -937,6 +991,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   UintKind get_uint_kind () const { return uint_kind; }
 
@@ -974,6 +1029,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   FloatKind get_float_kind () const { return float_kind; }
 
@@ -1013,6 +1069,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   BaseType *clone () final override;
 };
@@ -1045,6 +1102,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   BaseType *clone () final override;
 };
@@ -1077,6 +1135,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   BaseType *clone () final override;
 };
@@ -1113,6 +1172,7 @@ public:
   std::string get_name () const override final { return as_string (); }
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;
 
@@ -1150,6 +1210,7 @@ public:
   std::string as_string () const override;
 
   BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
 
   bool is_equal (const BaseType &other) const override;