Add ReferenceType with BorrowExpr and DereferenceExpr

This also adds in the mising InferenceType _ which was mostly implemented
before as part of Data Structures 1.

We create GENERIC REFERENCE_TYPES for these this is the building block
to finish work on mutability rules and pointers.

Fixes: #196
Addresses: #169 #170

25 files changed, 370 insertions, 18 deletions

diff --git a/gcc/rust/ast/rust-expr.h b/gcc/rust/ast/rust-expr.h
index a7e7f1d..0afa46b 100644
--- a/gcc/rust/ast/rust-expr.h
+++ b/gcc/rust/ast/rust-expr.h
@@ -288,6 +288,10 @@ public:
     return main_or_left_expr;
   }
 
+  bool get_is_mut () const { return is_mut; }
+
+  bool get_is_double_borrow () const { return double_borrow; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
diff --git a/gcc/rust/ast/rust-type.h b/gcc/rust/ast/rust-type.h
index a9e0f0f..a9c1966 100644
--- a/gcc/rust/ast/rust-type.h
+++ b/gcc/rust/ast/rust-type.h
@@ -576,6 +576,12 @@ public:
     return type;
   }
 
+  bool get_has_mut () const { return has_mut; }
+
+  Lifetime &get_lifetime () { return lifetime; }
+
+  std::unique_ptr<TypeNoBounds> &get_base_type () { return type; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
diff --git a/gcc/rust/backend/rust-compile-context.h b/gcc/rust/backend/rust-compile-context.h
index 3955a5b..b50e103 100644
--- a/gcc/rust/backend/rust-compile-context.h
+++ b/gcc/rust/backend/rust-compile-context.h
@@ -445,6 +445,13 @@ public:
     translated = compiled_type;
   }
 
+  void visit (TyTy::ReferenceType &type) override
+  {
+    Btype *base_compiled_type
+      = TyTyResolveCompile::compile (ctx, type.get_base ());
+    translated = ctx->get_backend ()->reference_type (base_compiled_type);
+  }
+
 private:
   TyTyResolveCompile (Context *ctx) : ctx (ctx) {}
 
diff --git a/gcc/rust/backend/rust-compile-expr.h b/gcc/rust/backend/rust-compile-expr.h
index c63479c..842804d 100644
--- a/gcc/rust/backend/rust-compile-expr.h
+++ b/gcc/rust/backend/rust-compile-expr.h
@@ -816,6 +816,37 @@ public:
     ctx->add_statement (goto_label);
   }
 
+  void visit (HIR::BorrowExpr &expr)
+  {
+    Bexpression *main_expr
+      = CompileExpr::Compile (expr.get_expr ().get (), ctx);
+
+    translated
+      = ctx->get_backend ()->address_expression (main_expr, expr.get_locus ());
+  }
+
+  void visit (HIR::DereferenceExpr &expr)
+  {
+    Bexpression *main_expr
+      = CompileExpr::Compile (expr.get_expr ().get (), ctx);
+
+    TyTy::TyBase *tyty = nullptr;
+    if (!ctx->get_tyctx ()->lookup_type (expr.get_mappings ().get_hirid (),
+					 &tyty))
+      {
+	rust_fatal_error (expr.get_locus (),
+			  "did not resolve type for this TupleExpr");
+	return;
+      }
+
+    Btype *expected_type = TyTyResolveCompile::compile (ctx, tyty);
+    bool known_valid = true;
+    translated
+      = ctx->get_backend ()->indirect_expression (expected_type, main_expr,
+						  known_valid,
+						  expr.get_locus ());
+  }
+
 private:
   CompileExpr (Context *ctx) : HIRCompileBase (ctx), translated (nullptr) {}
 
diff --git a/gcc/rust/backend/rust-compile-tyty.h b/gcc/rust/backend/rust-compile-tyty.h
index f591696..eb8a961 100644
--- a/gcc/rust/backend/rust-compile-tyty.h
+++ b/gcc/rust/backend/rust-compile-tyty.h
@@ -56,6 +56,8 @@ public:
 
   void visit (TyTy::ArrayType &) override { gcc_unreachable (); }
 
+  void visit (TyTy::ReferenceType &) override { gcc_unreachable (); }
+
   void visit (TyTy::UnitType &) override { translated = backend->void_type (); }
 
   void visit (TyTy::FnType &type) override
diff --git a/gcc/rust/hir/rust-ast-lower-expr.h b/gcc/rust/hir/rust-ast-lower-expr.h
index 6921e6d..ea07f73 100644
--- a/gcc/rust/hir/rust-ast-lower-expr.h
+++ b/gcc/rust/hir/rust-ast-lower-expr.h
@@ -740,6 +740,43 @@ public:
 					std::move (outer_attribs));
   }
 
+  void visit (AST::BorrowExpr &expr)
+  {
+    std::vector<HIR::Attribute> outer_attribs;
+
+    HIR::Expr *borrow_lvalue
+      = ASTLoweringExpr::translate (expr.get_borrowed_expr ().get ());
+
+    auto crate_num = mappings->get_current_crate ();
+    Analysis::NodeMapping mapping (crate_num, expr.get_node_id (),
+				   mappings->get_next_hir_id (crate_num),
+				   UNKNOWN_LOCAL_DEFID);
+
+    translated
+      = new HIR::BorrowExpr (mapping,
+			     std::unique_ptr<HIR::Expr> (borrow_lvalue),
+			     expr.get_is_mut (), expr.get_is_double_borrow (),
+			     std::move (outer_attribs), expr.get_locus ());
+  }
+
+  void visit (AST::DereferenceExpr &expr)
+  {
+    std::vector<HIR::Attribute> outer_attribs;
+
+    HIR::Expr *dref_lvalue
+      = ASTLoweringExpr::translate (expr.get_dereferenced_expr ().get ());
+
+    auto crate_num = mappings->get_current_crate ();
+    Analysis::NodeMapping mapping (crate_num, expr.get_node_id (),
+				   mappings->get_next_hir_id (crate_num),
+				   UNKNOWN_LOCAL_DEFID);
+
+    translated
+      = new HIR::DereferenceExpr (mapping,
+				  std::unique_ptr<HIR::Expr> (dref_lvalue),
+				  std::move (outer_attribs), expr.get_locus ());
+  }
+
 private:
   ASTLoweringExpr ()
     : ASTLoweringBase (), translated (nullptr),
diff --git a/gcc/rust/hir/rust-ast-lower-type.h b/gcc/rust/hir/rust-ast-lower-type.h
index e78ae5a..425d5c1 100644
--- a/gcc/rust/hir/rust-ast-lower-type.h
+++ b/gcc/rust/hir/rust-ast-lower-type.h
@@ -34,6 +34,7 @@ public:
     ASTLoweringType resolver;
     type->accept_vis (resolver);
 
+    rust_assert (resolver.translated != nullptr);
     resolver.mappings->insert_location (
       resolver.translated->get_mappings ().get_crate_num (),
       resolver.translated->get_mappings ().get_hirid (),
@@ -172,8 +173,43 @@ public:
 			       translated);
   }
 
+  void visit (AST::ReferenceType &type)
+  {
+    HIR::Lifetime lifetime = lower_lifetime (type.get_lifetime ());
+
+    HIR::Type *base_type
+      = ASTLoweringType::translate (type.get_base_type ().get ());
+
+    auto crate_num = mappings->get_current_crate ();
+    Analysis::NodeMapping mapping (crate_num, type.get_node_id (),
+				   mappings->get_next_hir_id (crate_num),
+				   mappings->get_next_localdef_id (crate_num));
+
+    translated = new HIR::ReferenceType (mapping, type.get_has_mut (),
+					 std::unique_ptr<HIR::Type> (base_type),
+					 type.get_locus (), lifetime);
+
+    mappings->insert_hir_type (mapping.get_crate_num (), mapping.get_hirid (),
+			       translated);
+  }
+
+  void visit (AST::InferredType &type)
+  {
+    auto crate_num = mappings->get_current_crate ();
+    Analysis::NodeMapping mapping (crate_num, type.get_node_id (),
+				   mappings->get_next_hir_id (crate_num),
+				   mappings->get_next_localdef_id (crate_num));
+
+    translated = new HIR::InferredType (mapping, type.get_locus ());
+
+    mappings->insert_hir_type (mapping.get_crate_num (), mapping.get_hirid (),
+			       translated);
+  }
+
 private:
-  ASTLoweringType () : translated (nullptr), translated_segment (nullptr) {}
+  ASTLoweringType ()
+    : ASTLoweringBase (), translated (nullptr), translated_segment (nullptr)
+  {}
 
   HIR::Type *translated;
   HIR::TypePathSegment *translated_segment;
diff --git a/gcc/rust/hir/tree/rust-hir-expr.h b/gcc/rust/hir/tree/rust-hir-expr.h
index 95ba7f8..c5c80ad 100644
--- a/gcc/rust/hir/tree/rust-hir-expr.h
+++ b/gcc/rust/hir/tree/rust-hir-expr.h
@@ -244,6 +244,8 @@ protected:
 public:
   Location get_locus () const { return locus; }
   Location get_locus_slow () const override { return get_locus (); }
+
+  std::unique_ptr<Expr> &get_expr () { return main_or_left_expr; }
 };
 
 /* Unary prefix & or &mut (or && and &&mut) borrow operator. Cannot be
@@ -267,6 +269,9 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
+  bool get_is_mut () const { return is_mut; }
+  bool get_is_double_borrow () const { return double_borrow; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
diff --git a/gcc/rust/hir/tree/rust-hir-type.h b/gcc/rust/hir/tree/rust-hir-type.h
index 746e3e2..47850ae 100644
--- a/gcc/rust/hir/tree/rust-hir-type.h
+++ b/gcc/rust/hir/tree/rust-hir-type.h
@@ -518,7 +518,7 @@ class ReferenceType : public TypeNoBounds
   Lifetime lifetime;
 
   bool has_mut;
-  std::unique_ptr<TypeNoBounds> type;
+  std::unique_ptr<Type> type;
   Location locus;
 
 public:
@@ -530,7 +530,7 @@ public:
 
   // Constructor
   ReferenceType (Analysis::NodeMapping mappings, bool is_mut,
-		 std::unique_ptr<TypeNoBounds> type_no_bounds, Location locus,
+		 std::unique_ptr<Type> type_no_bounds, Location locus,
 		 Lifetime lifetime)
     : TypeNoBounds (mappings), lifetime (std::move (lifetime)),
       has_mut (is_mut), type (std::move (type_no_bounds)), locus (locus)
@@ -539,7 +539,7 @@ public:
   // Copy constructor with custom clone method
   ReferenceType (ReferenceType const &other)
     : TypeNoBounds (other.mappings), lifetime (other.lifetime),
-      has_mut (other.has_mut), type (other.type->clone_type_no_bounds ()),
+      has_mut (other.has_mut), type (other.type->clone_type ()),
       locus (other.locus)
   {}
 
@@ -549,7 +549,7 @@ public:
     mappings = other.mappings;
     lifetime = other.lifetime;
     has_mut = other.has_mut;
-    type = other.type->clone_type_no_bounds ();
+    type = other.type->clone_type ();
     locus = other.locus;
 
     return *this;
@@ -565,6 +565,12 @@ public:
 
   void accept_vis (HIRVisitor &vis) override;
 
+  Lifetime &get_lifetime () { return lifetime; }
+
+  bool get_has_mut () const { return has_mut; }
+
+  std::unique_ptr<Type> &get_base_type () { return type; }
+
 protected:
   /* Use covariance to implement clone function as returning this object rather
    * than base */
diff --git a/gcc/rust/resolve/rust-ast-resolve-expr.h b/gcc/rust/resolve/rust-ast-resolve-expr.h
index d7bd6ab..b8cf4de 100644
--- a/gcc/rust/resolve/rust-ast-resolve-expr.h
+++ b/gcc/rust/resolve/rust-ast-resolve-expr.h
@@ -351,6 +351,16 @@ public:
       }
   }
 
+  void visit (AST::BorrowExpr &expr)
+  {
+    ResolveExpr::go (expr.get_borrowed_expr ().get (), expr.get_node_id ());
+  }
+
+  void visit (AST::DereferenceExpr &expr)
+  {
+    ResolveExpr::go (expr.get_dereferenced_expr ().get (), expr.get_node_id ());
+  }
+
 private:
   ResolveExpr (NodeId parent) : ResolverBase (parent) {}
 };
diff --git a/gcc/rust/resolve/rust-ast-resolve-type.h b/gcc/rust/resolve/rust-ast-resolve-type.h
index ec8ee87..4b08c21 100644
--- a/gcc/rust/resolve/rust-ast-resolve-type.h
+++ b/gcc/rust/resolve/rust-ast-resolve-type.h
@@ -83,6 +83,14 @@ public:
     type.get_elem_type ()->accept_vis (*this);
   }
 
+  void visit (AST::ReferenceType &type)
+  {
+    type.get_type_referenced ()->accept_vis (*this);
+  }
+
+  // nothing to do for inferred types
+  void visit (AST::InferredType &type) { ok = true; }
+
 private:
   ResolveType (NodeId parent) : ResolverBase (parent), ok (false) {}
 
diff --git a/gcc/rust/rust-backend.h b/gcc/rust/rust-backend.h
index c673e52..0ffc1aa 100644
--- a/gcc/rust/rust-backend.h
+++ b/gcc/rust/rust-backend.h
@@ -121,6 +121,9 @@ public:
   // Get a pointer type.
   virtual Btype *pointer_type (Btype *to_type) = 0;
 
+  // Get a reference type.
+  virtual Btype *reference_type (Btype *to_type) = 0;
+
   // make type immutable
   virtual Btype *immutable_type (Btype *base) = 0;
 
diff --git a/gcc/rust/rust-gcc.cc b/gcc/rust/rust-gcc.cc
index b2538b4..7cec47f 100644
--- a/gcc/rust/rust-gcc.cc
+++ b/gcc/rust/rust-gcc.cc
@@ -43,6 +43,7 @@
 #include "output.h"
 #include "realmpfr.h"
 #include "builtins.h"
+#include "print-tree.h"
 
 #include "rust-location.h"
 #include "rust-linemap.h"
@@ -186,6 +187,8 @@ public:
 
   Btype *pointer_type (Btype *);
 
+  Btype *reference_type (Btype *);
+
   Btype *immutable_type (Btype *);
 
   Btype *function_type (const Btyped_identifier &,
@@ -875,6 +878,18 @@ Gcc_backend::pointer_type (Btype *to_type)
   return this->make_type (type);
 }
 
+// Get a reference type.
+
+Btype *
+Gcc_backend::reference_type (Btype *to_type)
+{
+  tree to_type_tree = to_type->get_tree ();
+  if (to_type_tree == error_mark_node)
+    return this->error_type ();
+  tree type = build_reference_type (to_type_tree);
+  return this->make_type (type);
+}
+
 // Get immutable type
 
 Btype *
@@ -2517,7 +2532,6 @@ Gcc_backend::convert_tree (tree type_tree, tree expr_tree, Location location)
       || TREE_TYPE (expr_tree) == error_mark_node)
     return error_mark_node;
 
-  gcc_assert (TREE_CODE (type_tree) == TREE_CODE (TREE_TYPE (expr_tree)));
   if (POINTER_TYPE_P (type_tree) || INTEGRAL_TYPE_P (type_tree)
       || SCALAR_FLOAT_TYPE_P (type_tree) || COMPLEX_FLOAT_TYPE_P (type_tree))
     return fold_convert_loc (location.gcc_location (), type_tree, expr_tree);
diff --git a/gcc/rust/typecheck/rust-hir-type-check-expr.h b/gcc/rust/typecheck/rust-hir-type-check-expr.h
index e8ae83e..5ff17cb 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-expr.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-expr.h
@@ -246,10 +246,10 @@ public:
     auto rhs = TypeCheckExpr::Resolve (expr.get_rhs (), false);
 
     auto result = lhs->combine (rhs);
-    if (result == nullptr)
+    if (result->get_kind () == TyTy::TypeKind::ERROR)
       {
 	rust_error_at (expr.get_locus (),
-		       "failure in TypeInference AssignmentExpr");
+		       "type resolution failure in AssignmentExpr");
 	return;
       }
 
@@ -841,6 +841,32 @@ public:
     infered = new TyTy::UnitType (expr.get_mappings ().get_hirid ());
   }
 
+  void visit (HIR::BorrowExpr &expr)
+  {
+    TyTy::TyBase *resolved_base
+      = TypeCheckExpr::Resolve (expr.get_expr ().get (), false);
+
+    // FIXME double_reference
+
+    infered = new TyTy::ReferenceType (expr.get_mappings ().get_hirid (),
+				       resolved_base->get_ref ());
+  }
+
+  void visit (HIR::DereferenceExpr &expr)
+  {
+    TyTy::TyBase *resolved_base
+      = TypeCheckExpr::Resolve (expr.get_expr ().get (), false);
+    if (resolved_base->get_kind () != TyTy::TypeKind::REF)
+      {
+	rust_error_at (expr.get_locus (), "expected reference type got %s",
+		       resolved_base->as_string ().c_str ());
+	return;
+      }
+
+    TyTy::ReferenceType *ref_base = (TyTy::ReferenceType *) resolved_base;
+    infered = ref_base->get_base ()->clone ();
+  }
+
 private:
   TypeCheckExpr (bool inside_loop)
     : TypeCheckBase (), infered (nullptr), infered_array_elems (nullptr),
diff --git a/gcc/rust/typecheck/rust-hir-type-check-stmt.h b/gcc/rust/typecheck/rust-hir-type-check-stmt.h
index 195e483..cf0e979 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-stmt.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-stmt.h
@@ -73,7 +73,7 @@ public:
     if (specified_ty != nullptr && init_expr_ty != nullptr)
       {
 	auto combined = specified_ty->combine (init_expr_ty);
-	if (combined == nullptr)
+	if (combined->get_kind () == TyTy::TypeKind::ERROR)
 	  {
 	    rust_fatal_error (stmt.get_locus (),
 			      "failure in setting up let stmt type");
diff --git a/gcc/rust/typecheck/rust-hir-type-check-type.h b/gcc/rust/typecheck/rust-hir-type-check-type.h
index 2894899..0c8e861 100644
--- a/gcc/rust/typecheck/rust-hir-type-check-type.h
+++ b/gcc/rust/typecheck/rust-hir-type-check-type.h
@@ -70,12 +70,14 @@ public:
     TypeCheckType resolver;
     type->accept_vis (resolver);
 
-    if (resolver.translated != nullptr)
+    if (resolver.translated == nullptr)
       {
-	resolver.context->insert_type (type->get_mappings (),
-				       resolver.translated);
+	rust_error_at (Location (), "failed to translate %s",
+		       type->as_string ().c_str ());
+	return new TyTy::ErrorType (type->get_mappings ().get_hirid ());
       }
 
+    resolver.context->insert_type (type->get_mappings (), resolver.translated);
     return resolver.translated;
   }
 
@@ -174,6 +176,19 @@ public:
       = new TyTy::ArrayType (type.get_mappings ().get_hirid (), capacity, base);
   }
 
+  void visit (HIR::ReferenceType &type)
+  {
+    TyTy::TyBase *base = TypeCheckType::Resolve (type.get_base_type ().get ());
+    translated = new TyTy::ReferenceType (type.get_mappings ().get_hirid (),
+					  base->get_ref ());
+  }
+
+  void visit (HIR::InferredType &type)
+  {
+    translated = new TyTy::InferType (type.get_mappings ().get_hirid (),
+				      TyTy::InferType::InferTypeKind::GENERAL);
+  }
+
 private:
   TypeCheckType () : TypeCheckBase (), translated (nullptr) {}
 
diff --git a/gcc/rust/typecheck/rust-hir-type-check.cc b/gcc/rust/typecheck/rust-hir-type-check.cc
index 7f9bc69..2083344 100644
--- a/gcc/rust/typecheck/rust-hir-type-check.cc
+++ b/gcc/rust/typecheck/rust-hir-type-check.cc
@@ -51,7 +51,7 @@ TypeResolution::Resolve (HIR::Crate &crate)
     if (ty->get_kind () == TyTy::TypeKind::ERROR)
       {
 	rust_error_at (mappings->lookup_location (id),
-		       "failure in type resolution");
+		       "failure in type resolution for %u", id);
 	return false;
       }
 
@@ -64,7 +64,8 @@ TypeResolution::Resolve (HIR::Crate &crate)
       {
       case TyTy::InferType::GENERAL:
 	rust_error_at (mappings->lookup_location (id),
-		       "unable to determine type: %u", id);
+		       "unable to determine type: please give this a type: %u",
+		       id);
 	break;
 
 	case TyTy::InferType::INTEGRAL: {
diff --git a/gcc/rust/typecheck/rust-tyctx.cc b/gcc/rust/typecheck/rust-tyctx.cc
index 65c5563..484fd48 100644
--- a/gcc/rust/typecheck/rust-tyctx.cc
+++ b/gcc/rust/typecheck/rust-tyctx.cc
@@ -88,10 +88,7 @@ TypeCheckContext::lookup_type (HirId id, TyTy::TyBase **type)
 {
   auto it = resolved.find (id);
   if (it == resolved.end ())
-    {
-      *type = new TyTy::ErrorType (id);
-      return false;
-    }
+    return false;
 
   *type = it->second;
   return true;
diff --git a/gcc/rust/typecheck/rust-tyty-call.h b/gcc/rust/typecheck/rust-tyty-call.h
index 08c3ed3..fb2a259 100644
--- a/gcc/rust/typecheck/rust-tyty-call.h
+++ b/gcc/rust/typecheck/rust-tyty-call.h
@@ -52,6 +52,7 @@ public:
   void visit (ISizeType &type) override { gcc_unreachable (); }
   void visit (ErrorType &type) override { gcc_unreachable (); }
   void visit (CharType &type) override { gcc_unreachable (); }
+  void visit (ReferenceType &type) override { gcc_unreachable (); }
 
   // tuple-structs
   void visit (ADTType &type) override;
@@ -96,6 +97,7 @@ public:
   void visit (ErrorType &type) override { gcc_unreachable (); }
   void visit (ADTType &type) override { gcc_unreachable (); };
   void visit (CharType &type) override { gcc_unreachable (); }
+  void visit (ReferenceType &type) override { gcc_unreachable (); }
 
   // call fns
   void visit (FnType &type) override;
diff --git a/gcc/rust/typecheck/rust-tyty-rules.h b/gcc/rust/typecheck/rust-tyty-rules.h
index 809a76c..5a3edd4 100644
--- a/gcc/rust/typecheck/rust-tyty-rules.h
+++ b/gcc/rust/typecheck/rust-tyty-rules.h
@@ -176,6 +176,14 @@ public:
 		   base->as_string ().c_str (), type.as_string ().c_str ());
   }
 
+  virtual void visit (ReferenceType &type) override
+
+  {
+    Location ref_locus = mappings->lookup_location (type.get_ref ());
+    rust_error_at (ref_locus, "expected [%s] got [%s]",
+		   base->as_string ().c_str (), type.as_string ().c_str ());
+  }
+
 protected:
   BaseRules (TyBase *base)
     : mappings (Analysis::Mappings::get ()),
@@ -376,6 +384,22 @@ public:
 
   void visit (CharType &type) override
   {
+    {
+      bool is_valid
+	= (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
+      if (is_valid)
+	{
+	  resolved = type.clone ();
+	  return;
+	}
+
+      BaseRules::visit (type);
+    }
+  }
+
+  void visit (ReferenceType &type) override
+
+  {
     bool is_valid
       = (base->get_infer_kind () == TyTy::InferType::InferTypeKind::GENERAL);
     if (is_valid)
@@ -772,6 +796,25 @@ private:
   CharType *base;
 };
 
+class ReferenceRules : public BaseRules
+{
+public:
+  ReferenceRules (ReferenceType *base) : BaseRules (base), base (base) {}
+
+  void visit (ReferenceType &type) override
+  {
+    auto base_type = base->get_base ();
+    auto other_base_type = type.get_base ();
+
+    TyTy::TyBase *base_resolved = base_type->combine (other_base_type);
+    resolved = new ReferenceType (base->get_ref (), base->get_ty_ref (),
+				  base_resolved->get_ref ());
+  }
+
+private:
+  ReferenceType *base;
+};
+
 } // namespace TyTy
 } // namespace Rust
 
diff --git a/gcc/rust/typecheck/rust-tyty-visitor.h b/gcc/rust/typecheck/rust-tyty-visitor.h
index 6b36ebd..6609605 100644
--- a/gcc/rust/typecheck/rust-tyty-visitor.h
+++ b/gcc/rust/typecheck/rust-tyty-visitor.h
@@ -42,6 +42,7 @@ public:
   virtual void visit (ISizeType &type) = 0;
   virtual void visit (ErrorType &type) = 0;
   virtual void visit (CharType &type) = 0;
+  virtual void visit (ReferenceType &type) = 0;
 };
 
 } // namespace TyTy
diff --git a/gcc/rust/typecheck/rust-tyty.cc b/gcc/rust/typecheck/rust-tyty.cc
index c2d4763..24be4b0 100644
--- a/gcc/rust/typecheck/rust-tyty.cc
+++ b/gcc/rust/typecheck/rust-tyty.cc
@@ -510,6 +510,52 @@ CharType::clone ()
   return new CharType (get_ref (), get_ty_ref (), get_combined_refs ());
 }
 
+void
+ReferenceType::accept_vis (TyVisitor &vis)
+{
+  vis.visit (*this);
+}
+
+std::string
+ReferenceType::as_string () const
+{
+  return "&" + get_base ()->as_string ();
+}
+
+TyBase *
+ReferenceType::combine (TyBase *other)
+{
+  ReferenceRules r (this);
+  return r.combine (other);
+}
+
+const TyBase *
+ReferenceType::get_base () const
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  TyBase *lookup = nullptr;
+  bool ok = context->lookup_type (base, &lookup);
+  rust_assert (ok);
+  return lookup;
+}
+
+TyBase *
+ReferenceType::get_base ()
+{
+  auto context = Resolver::TypeCheckContext::get ();
+  TyBase *lookup = nullptr;
+  bool ok = context->lookup_type (base, &lookup);
+  rust_assert (ok);
+  return lookup;
+}
+
+TyBase *
+ReferenceType::clone ()
+{
+  return new ReferenceType (get_ref (), get_ty_ref (), base,
+			    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 dd80062..c333dd3 100644
--- a/gcc/rust/typecheck/rust-tyty.h
+++ b/gcc/rust/typecheck/rust-tyty.h
@@ -561,8 +561,35 @@ public:
 
   CharType (HirId ref, HirId ty_ref, std::set<HirId> refs = std::set<HirId> ())
     : TyBase (ref, ty_ref, TypeKind::CHAR)
+
+  {}
+
+  void accept_vis (TyVisitor &vis) override;
+
+  std::string as_string () const override;
+
+  TyBase *combine (TyBase *other) override;
+
+  TyBase *clone () final override;
+};
+
+class ReferenceType : public TyBase
+{
+public:
+  ReferenceType (HirId ref, HirId base,
+		 std::set<HirId> refs = std::set<HirId> ())
+    : TyBase (ref, ref, TypeKind::REF), base (base)
+  {}
+
+  ReferenceType (HirId ref, HirId ty_ref, HirId base,
+		 std::set<HirId> refs = std::set<HirId> ())
+    : TyBase (ref, ty_ref, TypeKind::REF), base (base)
   {}
 
+  const TyTy::TyBase *get_base () const;
+
+  TyTy::TyBase *get_base ();
+
   void accept_vis (TyVisitor &vis) override;
 
   std::string as_string () const override;
@@ -570,6 +597,9 @@ public:
   TyBase *combine (TyBase *other) override;
 
   TyBase *clone () final override;
+
+private:
+  HirId base;
 };
 
 } // namespace TyTy
diff --git a/gcc/testsuite/rust.test/compilable/borrow1.rs b/gcc/testsuite/rust.test/compilable/borrow1.rs
new file mode 100644
index 0000000..8afa474
--- /dev/null
+++ b/gcc/testsuite/rust.test/compilable/borrow1.rs
@@ -0,0 +1,17 @@
+fn main() {
+    let a: i32;
+    a = 123;
+
+    let b: &i32;
+    b = &a;
+
+    let aa;
+    aa = 456;
+    let bb: &_;
+    bb = &a;
+
+    let aaa;
+    aaa = 123;
+    let bbb;
+    bbb = &aaa;
+}
diff --git a/gcc/testsuite/rust.test/compilable/deref1.rs b/gcc/testsuite/rust.test/compilable/deref1.rs
new file mode 100644
index 0000000..9bf3eb5
--- /dev/null
+++ b/gcc/testsuite/rust.test/compilable/deref1.rs
@@ -0,0 +1,5 @@
+fn main() {
+    let a = 123;
+    let b = &a;
+    let c = *b;
+}