Introduce limited support for the never type

16 files changed, 169 insertions, 43 deletions

diff --git a/gcc/rust/backend/rust-compile-context.h b/gcc/rust/backend/rust-compile-context.h
index 8866575..2024a6f 100644
--- a/gcc/rust/backend/rust-compile-context.h
+++ b/gcc/rust/backend/rust-compile-context.h
@@ -503,6 +503,11 @@ public:
     translated = compiled_type;
   }
 
+  void visit (TyTy::NeverType &) override
+  {
+    translated = ctx->get_backend ()->void_type ();
+  }
+
 private:
   TyTyResolveCompile (Context *ctx) : ctx (ctx), translated (nullptr) {}
 
diff --git a/gcc/rust/backend/rust-compile-tyty.h b/gcc/rust/backend/rust-compile-tyty.h
index 28db289..ba98ac0 100644
--- a/gcc/rust/backend/rust-compile-tyty.h
+++ b/gcc/rust/backend/rust-compile-tyty.h
@@ -222,6 +222,11 @@ public:
       = backend->named_type ("str", raw_str, Linemap::predeclared_location ());
   }
 
+  void visit (TyTy::NeverType &) override
+  {
+    translated = backend->void_type ();
+  }
+
 private:
   TyTyCompile (::Backend *backend)
     : backend (backend), translated (nullptr),
diff --git a/gcc/rust/backend/rust-compile.cc b/gcc/rust/backend/rust-compile.cc
index d0e0c66..9375dd0 100644
--- a/gcc/rust/backend/rust-compile.cc
+++ b/gcc/rust/backend/rust-compile.cc
@@ -256,7 +256,7 @@ CompileBlock::visit (HIR::BlockExpr &expr)
 	}
     }
 
-  if (expr.has_expr () && expr.tail_expr_reachable ())
+  if (expr.has_expr ())
     {
       // the previous passes will ensure this is a valid return
       // dead code elimination should remove any bad trailing expressions
@@ -410,17 +410,15 @@ HIRCompileBase::compile_function_body (
 	}
     }
 
-  if (function_body->has_expr () && function_body->tail_expr_reachable ())
+  if (function_body->has_expr ())
     {
       // the previous passes will ensure this is a valid return
       // dead code elimination should remove any bad trailing expressions
       Bexpression *compiled_expr
 	= CompileExpr::Compile (function_body->expr.get (), ctx);
 
-      if (has_return_type)
+      if (has_return_type && compiled_expr)
 	{
-	  rust_assert (compiled_expr != nullptr);
-
 	  std::vector<Bexpression *> retstmts;
 	  retstmts.push_back (compiled_expr);
 
diff --git a/gcc/rust/hir/rust-ast-lower.cc b/gcc/rust/hir/rust-ast-lower.cc
index 0bacdd2..86b10d5 100644
--- a/gcc/rust/hir/rust-ast-lower.cc
+++ b/gcc/rust/hir/rust-ast-lower.cc
@@ -90,7 +90,7 @@ ASTLoweringBlock::visit (AST::BlockExpr &expr)
     return true;
   });
 
-  bool tail_reachable = expr.has_tail_expr () && !block_did_terminate;
+  bool tail_reachable = !block_did_terminate;
   if (expr.has_tail_expr () && block_did_terminate)
     {
       // warning unreachable tail expressions
diff --git a/gcc/rust/hir/tree/rust-hir-expr.h b/gcc/rust/hir/tree/rust-hir-expr.h
index 26f36c4d..498c8de 100644
--- a/gcc/rust/hir/tree/rust-hir-expr.h
+++ b/gcc/rust/hir/tree/rust-hir-expr.h
@@ -2511,7 +2511,7 @@ public:
   // Returns whether the block contains an expression
   bool has_expr () const { return expr != nullptr; }
 
-  bool tail_expr_reachable () const { return tail_reachable; }
+  bool is_tail_reachable () const { return tail_reachable; }
 
   BlockExpr (Analysis::NodeMapping mappings,
 	     std::vector<std::unique_ptr<Stmt> > block_statements,
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.h b/gcc/rust/typecheck/rust-hir-type-check-expr.h
index 6b6eed0..c18ad2a 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.h
@@ -145,16 +145,15 @@ public:
 
   void visit (HIR::ReturnExpr &expr) override
   {
-    if (!expr.has_return_expr ())
-      {
-	infered = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
-	return;
-      }
-
     auto fn_return_tyty = context->peek_return_type ();
     rust_assert (fn_return_tyty != nullptr);
 
-    auto expr_ty = TypeCheckExpr::Resolve (expr.get_expr (), false);
+    TyTy::BaseType *expr_ty;
+    if (expr.has_return_expr ())
+      expr_ty = TypeCheckExpr::Resolve (expr.get_expr (), false);
+    else
+      expr_ty = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
+
     if (expr_ty == nullptr)
       {
 	rust_error_at (expr.get_locus (),
@@ -166,6 +165,8 @@ public:
     fn_return_tyty->append_reference (expr_ty->get_ref ());
     for (auto &ref : infered->get_combined_refs ())
       fn_return_tyty->append_reference (ref);
+
+    infered = new TyTy::NeverType (expr.get_mappings ().get_hirid ());
   }
 
   void visit (HIR::CallExpr &expr) override
@@ -622,17 +623,28 @@ public:
     auto else_blk_resolved
       = TypeCheckExpr::Resolve (expr.get_else_block (), inside_loop);
 
-    infered = if_blk_resolved->unify (else_blk_resolved);
+    if (if_blk_resolved->get_kind () == TyTy::NEVER)
+      infered = else_blk_resolved;
+    else if (else_blk_resolved->get_kind () == TyTy::NEVER)
+      infered = if_blk_resolved;
+    else
+      infered = if_blk_resolved->unify (else_blk_resolved);
   }
 
   void visit (HIR::IfExprConseqIf &expr) override
   {
     TypeCheckExpr::Resolve (expr.get_if_condition (), false);
-    auto if_blk = TypeCheckExpr::Resolve (expr.get_if_block (), inside_loop);
-    auto else_blk
+    auto if_blk_resolved
+      = TypeCheckExpr::Resolve (expr.get_if_block (), inside_loop);
+    auto else_blk_resolved
       = TypeCheckExpr::Resolve (expr.get_conseq_if_expr (), inside_loop);
 
-    infered = if_blk->unify (else_blk);
+    if (if_blk_resolved->get_kind () == TyTy::NEVER)
+      infered = else_blk_resolved;
+    else if (else_blk_resolved->get_kind () == TyTy::NEVER)
+      infered = if_blk_resolved;
+    else
+      infered = if_blk_resolved->unify (else_blk_resolved);
   }
 
   void visit (HIR::BlockExpr &expr) override;
@@ -929,7 +941,7 @@ public:
 	context->swap_head_loop_context (unified_ty);
       }
 
-    infered = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
+    infered = new TyTy::NeverType (expr.get_mappings ().get_hirid ());
   }
 
   void visit (HIR::ContinueExpr &expr) override
@@ -941,7 +953,7 @@ public:
 	return;
       }
 
-    infered = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
+    infered = new TyTy::NeverType (expr.get_mappings ().get_hirid ());
   }
 
   void visit (HIR::BorrowExpr &expr) override
diff --git a/gcc/rust/typecheck/rust-hir-type-check-item.h b/gcc/rust/typecheck/rust-hir-type-check-item.h
index 44fe943..1205dce 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-item.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-item.h
@@ -82,7 +82,8 @@ public:
 
     context->pop_return_type ();
 
-    expected_ret_tyty->unify (block_expr_ty);
+    if (block_expr_ty->get_kind () != TyTy::NEVER)
+      expected_ret_tyty->unify (block_expr_ty);
   }
 
 private:
diff --git a/gcc/rust/typecheck/rust-hir-type-check.cc b/gcc/rust/typecheck/rust-hir-type-check.cc
index f1503be..aece188 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check.cc
@@ -123,14 +123,7 @@ TypeResolution::Resolve (HIR::Crate &crate)
 void
 TypeCheckExpr::visit (HIR::BlockExpr &expr)
 {
-  TyTy::BaseType *block_tyty
-    = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
-
   expr.iterate_stmts ([&] (HIR::Stmt *s) mutable -> bool {
-    bool is_final_stmt = expr.is_final_stmt (s);
-    bool has_final_expr = expr.has_expr () && expr.tail_expr_reachable ();
-    bool stmt_is_final_expr = is_final_stmt && !has_final_expr;
-
     auto resolved = TypeCheckStmt::Resolve (s, inside_loop);
     if (resolved == nullptr)
       {
@@ -138,12 +131,7 @@ TypeCheckExpr::visit (HIR::BlockExpr &expr)
 	return false;
       }
 
-    if (stmt_is_final_expr)
-      {
-	delete block_tyty;
-	block_tyty = resolved;
-      }
-    else if (s->is_unit_check_needed () && !resolved->is_unit ())
+    if (s->is_unit_check_needed () && !resolved->is_unit ())
       {
 	auto unit = new TyTy::TupleType (s->get_mappings ().get_hirid ());
 	resolved = unit->unify (resolved);
@@ -153,14 +141,13 @@ TypeCheckExpr::visit (HIR::BlockExpr &expr)
   });
 
   if (expr.has_expr ())
-    {
-      delete block_tyty;
-
-      block_tyty
-	= TypeCheckExpr::Resolve (expr.get_final_expr ().get (), inside_loop);
-    }
-
-  infered = block_tyty->clone ();
+    infered
+      = TypeCheckExpr::Resolve (expr.get_final_expr ().get (), inside_loop)
+	  ->clone ();
+  else if (expr.is_tail_reachable ())
+    infered = new TyTy::TupleType (expr.get_mappings ().get_hirid ());
+  else
+    infered = new TyTy::NeverType (expr.get_mappings ().get_hirid ());
 }
 
 // RUST_HIR_TYPE_CHECK_STRUCT_FIELD
diff --git a/gcc/rust/typecheck/rust-substitution-mapper.h b/gcc/rust/typecheck/rust-substitution-mapper.h
index bc20e4b..4cd06bb 100644
--- a/gcc/rust/typecheck/rust-substitution-mapper.h
+++ b/gcc/rust/typecheck/rust-substitution-mapper.h
@@ -99,6 +99,7 @@ public:
   void visit (TyTy::ReferenceType &) override { gcc_unreachable (); }
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
+  void visit (TyTy::NeverType &) override { gcc_unreachable (); }
 
 private:
   SubstMapper (HirId ref, HIR::GenericArgs *generics, Location locus)
@@ -157,6 +158,7 @@ public:
   void visit (TyTy::ReferenceType &) override { gcc_unreachable (); }
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
+  void visit (TyTy::NeverType &) override { gcc_unreachable (); }
 
 private:
   SubstMapperInternal (HirId ref, TyTy::SubstitutionArgumentMappings &mappings)
@@ -211,6 +213,7 @@ public:
   void visit (TyTy::ReferenceType &) override { gcc_unreachable (); }
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
+  void visit (TyTy::NeverType &) override { gcc_unreachable (); }
 
 private:
   SubstMapperFromExisting (TyTy::BaseType *concrete, TyTy::BaseType *receiver)
@@ -258,6 +261,7 @@ public:
   void visit (TyTy::ReferenceType &) override { gcc_unreachable (); }
   void visit (TyTy::ParamType &) override { gcc_unreachable (); }
   void visit (TyTy::StrType &) override { gcc_unreachable (); }
+  void visit (TyTy::NeverType &) override { gcc_unreachable (); }
 
 private:
   GetUsedSubstArgs () : args (TyTy::SubstitutionArgumentMappings::error ()) {}
diff --git a/gcc/rust/typecheck/rust-tycheck-dump.h b/gcc/rust/typecheck/rust-tycheck-dump.h
index 953770e..2ab8abb 100644
--- a/gcc/rust/typecheck/rust-tycheck-dump.h
+++ b/gcc/rust/typecheck/rust-tycheck-dump.h
@@ -107,7 +107,7 @@ public:
       return true;
     });
 
-    if (expr.has_expr () && expr.tail_expr_reachable ())
+    if (expr.has_expr ())
       {
 	dump += indent ();
 	expr.expr->accept_vis (*this);
diff --git a/gcc/rust/typecheck/rust-tyty-call.h b/gcc/rust/typecheck/rust-tyty-call.h
index 4171da5..2aba298 100644
--- a/gcc/rust/typecheck/rust-tyty-call.h
+++ b/gcc/rust/typecheck/rust-tyty-call.h
@@ -53,6 +53,7 @@ public:
   void visit (ReferenceType &type) override { gcc_unreachable (); }
   void visit (ParamType &) override { gcc_unreachable (); }
   void visit (StrType &) override { gcc_unreachable (); }
+  void visit (NeverType &) override { gcc_unreachable (); }
 
   // tuple-structs
   void visit (ADTType &type) override;
@@ -100,6 +101,7 @@ public:
   void visit (ReferenceType &type) override { gcc_unreachable (); }
   void visit (ParamType &) override { gcc_unreachable (); }
   void visit (StrType &) override { gcc_unreachable (); }
+  void visit (NeverType &) 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 b195e5c..1641264 100644
--- a/gcc/rust/typecheck/rust-tyty-cmp.h
+++ b/gcc/rust/typecheck/rust-tyty-cmp.h
@@ -84,6 +84,8 @@ public:
 
   virtual void visit (StrType &) override { ok = false; }
 
+  virtual void visit (NeverType &) override { ok = false; }
+
 protected:
   BaseCmp (BaseType *base)
     : mappings (Analysis::Mappings::get ()),
@@ -815,6 +817,21 @@ private:
   StrType *base;
 };
 
+class NeverCmp : public BaseCmp
+{
+  using Rust::TyTy::BaseCmp::visit;
+
+public:
+  NeverCmp (NeverType *base) : BaseCmp (base), base (base) {}
+
+  void visit (NeverType &type) override { ok = true; }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  NeverType *base;
+};
+
 } // namespace TyTy
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-tyty-rules.h b/gcc/rust/typecheck/rust-tyty-rules.h
index 03fe0d8..6f7e663 100644
--- a/gcc/rust/typecheck/rust-tyty-rules.h
+++ b/gcc/rust/typecheck/rust-tyty-rules.h
@@ -293,6 +293,14 @@ public:
 		   type.as_string ().c_str ());
   }
 
+  virtual void visit (NeverType &type) override
+  {
+    Location ref_locus = mappings->lookup_location (type.get_ref ());
+    rust_error_at (ref_locus, "expected [%s] got [%s]",
+		   get_base ()->as_string ().c_str (),
+		   type.as_string ().c_str ());
+  }
+
 protected:
   BaseRules (BaseType *base)
     : mappings (Analysis::Mappings::get ()),
@@ -1138,6 +1146,21 @@ private:
   StrType *base;
 };
 
+class NeverRules : public BaseRules
+{
+  using Rust::TyTy::BaseRules::visit;
+
+public:
+  NeverRules (NeverType *base) : BaseRules (base), base (base) {}
+
+  virtual void visit (NeverType &type) override { resolved = type.clone (); }
+
+private:
+  BaseType *get_base () override { return base; }
+
+  NeverType *base;
+};
+
 } // namespace TyTy
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-tyty-visitor.h b/gcc/rust/typecheck/rust-tyty-visitor.h
index 453a3b6..0ed7eef 100644
--- a/gcc/rust/typecheck/rust-tyty-visitor.h
+++ b/gcc/rust/typecheck/rust-tyty-visitor.h
@@ -44,6 +44,7 @@ public:
   virtual void visit (ReferenceType &type) = 0;
   virtual void visit (ParamType &type) = 0;
   virtual void visit (StrType &type) = 0;
+  virtual void visit (NeverType &type) = 0;
 };
 
 } // namespace TyTy
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index 8378cf2..86b1da0 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -1307,6 +1307,38 @@ StrType::is_equal (const BaseType &other) const
   return get_kind () == other.get_kind ();
 }
 
+void
+NeverType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+std::string
+NeverType::as_string () const
+{
+  return "!";
+}
+
+BaseType *
+NeverType::unify (BaseType *other)
+{
+  NeverRules r (this);
+  return r.unify (other);
+}
+
+bool
+NeverType::can_eq (BaseType *other)
+{
+  NeverCmp r (this);
+  return r.can_eq (other);
+}
+
+BaseType *
+NeverType::clone ()
+{
+  return new NeverType (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 2f343c1..2b9f304 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -45,6 +45,7 @@ enum TypeKind
   FLOAT,
   USIZE,
   ISIZE,
+  NEVER,
   // there are more to add...
   ERROR
 };
@@ -1226,6 +1227,41 @@ public:
   BaseType *clone () final override;
 };
 
+// https://doc.rust-lang.org/std/primitive.never.html
+//
+// Since the `!` type is really complicated and it is even still unstable
+// in rustc, only fairly limited support for this type is introduced here.
+// Unification between `!` and ANY other type (including `<T?>`) is simply
+// not allowed. If it is needed, it should be handled manually. For example,
+// unifying `!` with other types is very necessary when resolving types of
+// `if/else` expressions.
+//
+// See related discussion at https://github.com/Rust-GCC/gccrs/pull/364
+class NeverType : public BaseType
+{
+public:
+  NeverType (HirId ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ref, TypeKind::NEVER, refs)
+  {}
+
+  NeverType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
+    : BaseType (ref, ty_ref, TypeKind::NEVER, 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; }
+};
+
 class TypeKindFormat
 {
 public:
@@ -1281,6 +1317,9 @@ public:
       case TypeKind::ISIZE:
 	return "Isize";
 
+      case TypeKind::NEVER:
+	return "Never";
+
       case TypeKind::ERROR:
 	return "ERROR";
       }