Introduce placeholder type

This is used in Traits with associated types that can contain TypeBounds
but provides an ability to reuse out type system to check that trait items
are compatible with their respective ImplBlock Items

11 files changed, 126 insertions, 3 deletions

diff --git a/gcc/rust/backend/rust-compile-context.h b/gcc/rust/backend/rust-compile-context.h
index 5d19099..d822937 100644
--- a/gcc/rust/backend/rust-compile-context.h
+++ b/gcc/rust/backend/rust-compile-context.h
@@ -336,6 +336,8 @@ public:
 
   void visit (TyTy::InferType &) override { gcc_unreachable (); }
 
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
+
   void visit (TyTy::ParamType &param) override
   {
     param.resolve ()->accept_vis (*this);
diff --git a/gcc/rust/backend/rust-compile-tyty.h b/gcc/rust/backend/rust-compile-tyty.h
index 8576235..d2890e0 100644
--- a/gcc/rust/backend/rust-compile-tyty.h
+++ b/gcc/rust/backend/rust-compile-tyty.h
@@ -48,6 +48,8 @@ public:
 
   void visit (TyTy::ADTType &) override { gcc_unreachable (); }
 
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
+
   void visit (TyTy::TupleType &type) override
   {
     if (type.num_fields () == 0)
diff --git a/gcc/rust/typecheck/rust-hir-const-fold.h b/gcc/rust/typecheck/rust-hir-const-fold.h
index 90ea595..c71dd39 100644
--- a/gcc/rust/typecheck/rust-hir-const-fold.h
+++ b/gcc/rust/typecheck/rust-hir-const-fold.h
@@ -51,6 +51,8 @@ public:
 
   void visit (TyTy::FnType &) override { gcc_unreachable (); }
 
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
+
   void visit (TyTy::TupleType &type) override
   {
     if (type.num_fields () == 0)
diff --git a/gcc/rust/typecheck/rust-hir-trait-resolve.h b/gcc/rust/typecheck/rust-hir-trait-resolve.h
index 6d926f7..1b83be3 100644
--- a/gcc/rust/typecheck/rust-hir-trait-resolve.h
+++ b/gcc/rust/typecheck/rust-hir-trait-resolve.h
@@ -44,8 +44,9 @@ public:
 
   void visit (HIR::TraitItemType &type) override
   {
-    // associated types are not typed and only support bounds
-    TyTy::BaseType *ty = nullptr;
+    TyTy::BaseType *ty
+      = new TyTy::PlaceholderType (type.get_mappings ().get_hirid ());
+    context->insert_type (type.get_mappings (), ty);
 
     // create trait-item-ref
     Location locus = type.get_locus ();
diff --git a/gcc/rust/typecheck/rust-substitution-mapper.h b/gcc/rust/typecheck/rust-substitution-mapper.h
index 739f1b5..9741dfa 100644
--- a/gcc/rust/typecheck/rust-substitution-mapper.h
+++ b/gcc/rust/typecheck/rust-substitution-mapper.h
@@ -106,6 +106,7 @@ public:
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
   void visit (TyTy::NeverType &) override { gcc_unreachable (); }
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
 
 private:
   SubstMapper (HirId ref, HIR::GenericArgs *generics, Location locus)
@@ -183,6 +184,7 @@ public:
   void visit (TyTy::CharType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
   void visit (TyTy::NeverType &) override { gcc_unreachable (); }
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
 
 private:
   SubstMapperInternal (HirId ref, TyTy::SubstitutionArgumentMappings &mappings)
@@ -238,6 +240,7 @@ public:
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
   void visit (TyTy::NeverType &) override { gcc_unreachable (); }
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
 
 private:
   SubstMapperFromExisting (TyTy::BaseType *concrete, TyTy::BaseType *receiver)
@@ -286,6 +289,7 @@ public:
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
   void visit (TyTy::NeverType &) override { gcc_unreachable (); }
+  void visit (TyTy::PlaceholderType &) override { gcc_unreachable (); }
 
 private:
   GetUsedSubstArgs () : args (TyTy::SubstitutionArgumentMappings::error ()) {}
diff --git a/gcc/rust/typecheck/rust-tyty-call.h b/gcc/rust/typecheck/rust-tyty-call.h
index 2aba298..f6121ca 100644
--- a/gcc/rust/typecheck/rust-tyty-call.h
+++ b/gcc/rust/typecheck/rust-tyty-call.h
@@ -54,6 +54,7 @@ public:
   void visit (ParamType &) override { gcc_unreachable (); }
   void visit (StrType &) override { gcc_unreachable (); }
   void visit (NeverType &) override { gcc_unreachable (); }
+  void visit (PlaceholderType &) override { gcc_unreachable (); }
 
   // tuple-structs
   void visit (ADTType &type) override;
@@ -102,6 +103,7 @@ public:
   void visit (ParamType &) override { gcc_unreachable (); }
   void visit (StrType &) override { gcc_unreachable (); }
   void visit (NeverType &) override { gcc_unreachable (); }
+  void visit (PlaceholderType &) override { gcc_unreachable (); }
 
   // FIXME
   void visit (FnPtr &type) override { gcc_unreachable (); }
diff --git a/gcc/rust/typecheck/rust-tyty-cmp.h b/gcc/rust/typecheck/rust-tyty-cmp.h
index c3a9742..7595e2f 100644
--- a/gcc/rust/typecheck/rust-tyty-cmp.h
+++ b/gcc/rust/typecheck/rust-tyty-cmp.h
@@ -86,6 +86,11 @@ public:
 
   virtual void visit (NeverType &) override { ok = false; }
 
+  virtual void visit (PlaceholderType &) override
+  { // it is ok for types to can eq to a placeholder
+    ok = true;
+  }
+
 protected:
   BaseCmp (BaseType *base)
     : mappings (Analysis::Mappings::get ()),
@@ -832,6 +837,19 @@ private:
   NeverType *base;
 };
 
+class PlaceholderCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  PlaceholderCmp (PlaceholderType *base) : BaseCmp (base), base (base) {}
+
+private:
+  BaseType *get_base () override { return base; }
+
+  PlaceholderType *base;
+};
+
 } // namespace TyTy
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-tyty-rules.h b/gcc/rust/typecheck/rust-tyty-rules.h
index 06bb33f..5db005b 100644
--- a/gcc/rust/typecheck/rust-tyty-rules.h
+++ b/gcc/rust/typecheck/rust-tyty-rules.h
@@ -299,7 +299,21 @@ public:
   virtual void visit (NeverType &type) override
   {
     Location ref_locus = mappings->lookup_location (type.get_ref ());
-    rust_error_at (ref_locus, "expected [%s] got [%s]",
+    Location base_locus = mappings->lookup_location (get_base ()->get_ref ());
+    RichLocation r (ref_locus);
+    r.add_range (base_locus);
+    rust_error_at (r, "expected [%s] got [%s]",
+		   get_base ()->as_string ().c_str (),
+		   type.as_string ().c_str ());
+  }
+
+  virtual void visit (PlaceholderType &type) override
+  {
+    Location ref_locus = mappings->lookup_location (type.get_ref ());
+    Location base_locus = mappings->lookup_location (get_base ()->get_ref ());
+    RichLocation r (ref_locus);
+    r.add_range (base_locus);
+    rust_error_at (r, "expected [%s] got [%s]",
 		   get_base ()->as_string ().c_str (),
 		   type.as_string ().c_str ());
   }
@@ -1165,6 +1179,19 @@ private:
   NeverType *base;
 };
 
+class PlaceholderRules : public BaseRules
+{
+  using Rust::TyTy::BaseRules::visit;
+
+public:
+  PlaceholderRules (PlaceholderType *base) : BaseRules (base), base (base) {}
+
+private:
+  BaseType *get_base () override { return base; }
+
+  PlaceholderType *base;
+};
+
 } // namespace TyTy
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-tyty-visitor.h b/gcc/rust/typecheck/rust-tyty-visitor.h
index 0ed7eef..2bac5fe 100644
--- a/gcc/rust/typecheck/rust-tyty-visitor.h
+++ b/gcc/rust/typecheck/rust-tyty-visitor.h
@@ -45,6 +45,7 @@ public:
   virtual void visit (ParamType &type) = 0;
   virtual void visit (StrType &type) = 0;
   virtual void visit (NeverType &type) = 0;
+  virtual void visit (PlaceholderType &type) = 0;
 };
 
 } // namespace TyTy
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index dd2472c..503d380 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -1495,6 +1495,38 @@ NeverType::clone ()
   return new NeverType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
 
+void
+PlaceholderType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+std::string
+PlaceholderType::as_string () const
+{
+  return "<placeholder>";
+}
+
+BaseType *
+PlaceholderType::unify (BaseType *other)
+{
+  PlaceholderRules r (this);
+  return r.unify (other);
+}
+
+bool
+PlaceholderType::can_eq (BaseType *other)
+{
+  PlaceholderCmp r (this);
+  return r.can_eq (other);
+}
+
+BaseType *
+PlaceholderType::clone ()
+{
+  return new PlaceholderType (get_ref (), get_ty_ref (), get_combined_refs ());
+}
+
 // rust-tyty-call.h
 
 void
diff --git a/gcc/rust/typecheck/rust-tyty.h b/gcc/rust/typecheck/rust-tyty.h
index 438c52b..c04c249 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -48,6 +48,7 @@ enum TypeKind
   USIZE,
   ISIZE,
   NEVER,
+  PLACEHOLDER,
   // there are more to add...
   ERROR
 };
@@ -110,6 +111,9 @@ public:
       case TypeKind::NEVER:
 	return "Never";
 
+      case TypeKind::PLACEHOLDER:
+	return "Placeholder";
+
       case TypeKind::ERROR:
 	return "ERROR";
       }
@@ -1474,6 +1478,34 @@ public:
   bool is_unit () const override { return true; }
 };
 
+// used at the type in associated types in traits
+// see: https://doc.rust-lang.org/book/ch19-03-advanced-traits.html
+class PlaceholderType : public BaseType
+{
+public:
+  PlaceholderType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::PLACEHOLDER, refs)
+  {}
+
+  PlaceholderType (HirId ref, HirId ty_ref,
+		   std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::PLACEHOLDER, refs)
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+
+  std::string as_string () const override;
+
+  BaseType *unify (BaseType *other) override;
+  bool can_eq (BaseType *other) override;
+
+  BaseType *clone () final override;
+
+  std::string get_name () const override final { return as_string (); }
+
+  bool is_unit () const override { return true; }
+};
+
 } // namespace TyTy
 } // namespace Rust