MethodResolution should respect the autoderef cycle

Autoderef includes calling into the deref operator overloads so for
example.

```rust
pub trait Deref {
    type Target;

    fn deref(&self) -> &Self::Target;
}

impl<T> Deref for &T {
    type Target = T;

    fn deref(&self) -> &T {
        *self
    }
}

struct Bar(i32);
impl Bar {
    fn foobar(self) -> i32 {
        self.0
    }
}

struct Foo<T>(T);
impl<T> Deref for Foo<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

fn main() {
    let bar = Bar(123);
    let foo: Foo<&Bar> = Foo(&bar);
    let foobar: i32 = foo.foobar();
}

```

So you can see here we have a nested structure of Foo<&Bar> and Foo is a
generic structure, and we have a method call of foo.foobar(). This is an
interesting case of method resolution showing how rust allows for multiple
dereference to find the apropriate method of foobar.

So in this method call expression foo is of type Foo<&Bar> the generic
structure is a covariant Reference Type (&) of the structure Bar. The
method foobar has a receiver type of a simple Bar being passed by value.

So in order for this function to be called the method resolution system
has an algorithm of:

- reciever = Foo<&Bar>
- Find all methods named foobar
- try and match the receiver (self) with this reciever
- so that means we have Foo<&Bar> vs Bar which does not match
- Go back to the start and try by taking an immutable refernece
- &Foo<&Bar> does not match Bar
- Go back to the start and try by taking a mutable reference
- &mut Foo<&Bar> does not match Bar
- Try and dereference the original receiver Foo<&Bar>
- Do we have the deref lang item defined
- if yes resolve the method by the same mechanism for Foo<&Bar> for deref
- Get the result type of this function which is &&Bar do the dereference
- Now we have &Bar and a new adjustment for the original receiver
- Try and match &Bar to the foobar method reciever of Bar
- Try taking an immutable reference &&Bar
- Try taking a mutable reference &mut &Bar
- Try and deref &Bar we have the generic implementation of deref for &T
- Call this derefernece like before to get down to Bar
- Now try Bar on the foobar reciever Bar and it matches

We have now resolved the method with two dereference adjustments so the
function call becomes:

```
void main ()
{
  i32 D.110;
  const struct  bar;
  const struct  foo;
  const i32 foobar;
  try
    {
      bar.0 = 123;
      foo.0 = &bar;
      RUSTTMP.3 = <Foo as Deref>::deref<&Bar> (&foo);
      RUSTTMP.5 = <&T as Deref>::deref<Bar> (RUSTTMP.3);
      foobar = Bar::foobar (*RUSTTMP.5);
    }
  finally
    {
      bar = {CLOBBER};
      foo = {CLOBBER};
    }
}
```

Obviously GCC will optimize this with -O2 so that it does not require
function calls but the gimple will show us what is actually going on. As
far as I am aware rustc pre-optimizes this regardless of optimizations
being turned on or not, these lang item functions are easily inlineable
so it makes more sense to me to let GCC's middle-end take care of this for
us.

This is a big patch and very difficult to split up as it reimplements our
method resolution system.

Fixes #884

8 files changed, 122 insertions, 190 deletions

diff --git a/gcc/rust/backend/rust-compile-base.h b/gcc/rust/backend/rust-compile-base.h
index e963176..902bedc 100644
--- a/gcc/rust/backend/rust-compile-base.h
+++ b/gcc/rust/backend/rust-compile-base.h
@@ -60,6 +60,17 @@ protected:
 
   bool verify_array_capacities (tree ltype, tree rtype, Location ltype_locus,
 				Location rtype_locus);
+
+  tree query_compile (HirId ref, TyTy::BaseType *lookup,
+		      const HIR::PathIdentSegment &final_segment,
+		      const Analysis::NodeMapping &mappings,
+		      Location expr_locus, bool is_qualified_path);
+
+  tree resolve_adjustements (std::vector<Resolver::Adjustment> &adjustments,
+			     tree expression, Location locus);
+
+  tree resolve_deref_adjustment (Resolver::Adjustment &adjustment,
+				 tree expression, Location locus);
 };
 
 } // namespace Compile
diff --git a/gcc/rust/backend/rust-compile-expr.cc b/gcc/rust/backend/rust-compile-expr.cc
index 33237e5..c58d29d 100644
--- a/gcc/rust/backend/rust-compile-expr.cc
+++ b/gcc/rust/backend/rust-compile-expr.cc
@@ -23,7 +23,6 @@
 #include "rust-hir-trait-resolve.h"
 #include "rust-hir-path-probe.h"
 #include "rust-hir-type-bounds.h"
-#include "rust-hir-dot-operator.h"
 #include "rust-compile-pattern.h"
 #include "rust-constexpr.h"
 
@@ -574,25 +573,9 @@ CompileExpr::visit (HIR::MethodCallExpr &expr)
     expr.get_mappings ().get_hirid (), &adjustments);
   rust_assert (ok);
 
-  for (auto &adjustment : *adjustments)
-    {
-      switch (adjustment.get_type ())
-	{
-	case Resolver::Adjustment::AdjustmentType::IMM_REF:
-	case Resolver::Adjustment::AdjustmentType::MUT_REF:
-	  self = ctx->get_backend ()->address_expression (
-	    self, expr.get_receiver ()->get_locus ());
-	  break;
-
-	case Resolver::Adjustment::AdjustmentType::DEREF_REF:
-	  tree expected_type
-	    = TyTyResolveCompile::compile (ctx, adjustment.get_expected ());
-	  self = ctx->get_backend ()->indirect_expression (
-	    expected_type, self, true, /* known_valid*/
-	    expr.get_receiver ()->get_locus ());
-	  break;
-	}
-    }
+  // apply adjustments for the fn call
+  self = resolve_adjustements (*adjustments, self,
+			       expr.get_receiver ()->get_locus ());
 
   std::vector<tree> args;
   args.push_back (self); // adjusted self
@@ -737,11 +720,10 @@ CompileExpr::resolve_method_address (TyTy::FnType *fntype, HirId ref,
   if (resolved_item != nullptr)
     {
       if (!fntype->has_subsititions_defined ())
-	return CompileInherentImplItem::Compile (receiver, resolved_item, ctx,
-						 true);
+	return CompileInherentImplItem::Compile (resolved_item, ctx, true);
 
-      return CompileInherentImplItem::Compile (receiver, resolved_item, ctx,
-					       true, fntype);
+      return CompileInherentImplItem::Compile (resolved_item, ctx, true,
+					       fntype);
     }
 
   // it might be resolved to a trait item
@@ -785,24 +767,20 @@ CompileExpr::resolve_method_address (TyTy::FnType *fntype, HirId ref,
     }
   else
     {
-      std::vector<Resolver::Adjustment> adjustments;
-      Resolver::PathProbeCandidate *candidate
-	= Resolver::MethodResolution::Select (candidates, root, adjustments);
-
       // FIXME this will be a case to return error_mark_node, there is
       // an error scenario where a Trait Foo has a method Bar, but this
       // receiver does not implement this trait or has an incompatible
       // implementation and we should just return error_mark_node
-      rust_assert (candidate != nullptr);
-      rust_assert (candidate->is_impl_candidate ());
 
-      HIR::ImplItem *impl_item = candidate->item.impl.impl_item;
+      rust_assert (candidates.size () == 1);
+      auto &candidate = candidates.at (0);
+      rust_assert (candidate.is_impl_candidate ());
+
+      HIR::ImplItem *impl_item = candidate.item.impl.impl_item;
       if (!fntype->has_subsititions_defined ())
-	return CompileInherentImplItem::Compile (receiver, impl_item, ctx,
-						 true);
+	return CompileInherentImplItem::Compile (impl_item, ctx, true);
 
-      return CompileInherentImplItem::Compile (receiver, impl_item, ctx, true,
-					       fntype);
+      return CompileInherentImplItem::Compile (impl_item, ctx, true, fntype);
     }
 }
 
@@ -868,29 +846,8 @@ CompileExpr::resolve_operator_overload (
     expr.get_mappings ().get_hirid (), &adjustments);
   rust_assert (ok);
 
-  // FIXME refactor this out
-  tree self = lhs;
-  for (auto &adjustment : *adjustments)
-    {
-      switch (adjustment.get_type ())
-	{
-	case Resolver::Adjustment::AdjustmentType::IMM_REF:
-	case Resolver::Adjustment::AdjustmentType::MUT_REF:
-	  self
-	    = ctx->get_backend ()->address_expression (self,
-						       lhs_expr->get_locus ());
-	  break;
-
-	case Resolver::Adjustment::AdjustmentType::DEREF_REF:
-	  tree expected_type
-	    = TyTyResolveCompile::compile (ctx, adjustment.get_expected ());
-	  self
-	    = ctx->get_backend ()->indirect_expression (expected_type, self,
-							true, /* known_valid*/
-							lhs_expr->get_locus ());
-	  break;
-	}
-    }
+  // apply adjustments for the fn call
+  tree self = resolve_adjustements (*adjustments, lhs, lhs_expr->get_locus ());
 
   std::vector<tree> args;
   args.push_back (self); // adjusted self
@@ -1221,106 +1178,82 @@ CompileExpr::array_copied_expr (Location expr_locus,
 							    expr_locus);
 }
 
-// tree
-// CompileExpr::array_copied_expr (Location expr_locus, tree array_type,
-// 				HIR::ArrayElemsCopied &elems)
-// {
-//   // create tmp for the result
-//   fncontext fnctx = ctx->peek_fn ();
-//   Location start_location = expr_locus;
-//   Location end_location = expr_locus;
-//   tree fndecl = fnctx.fndecl;
-//   tree enclosing_scope = ctx->peek_enclosing_scope ();
-
-//   bool is_address_taken = false;
-//   tree result_var_stmt = nullptr;
-//   Bvariable *result
-//     = ctx->get_backend ()->temporary_variable (fnctx.fndecl,
-//     enclosing_scope,
-// 					       array_type, NULL,
-// 					       is_address_taken, expr_locus,
-// 					       &result_var_stmt);
-//   ctx->add_statement (result_var_stmt);
-
-//   // get the compiled value
-//   tree translated_expr = CompileExpr::Compile (elems.get_elem_to_copy (),
-//   ctx);
-
-//   // lets assign each index in the array
-//   TyTy::BaseType *capacity_tyty = nullptr;
-//   HirId capacity_ty_id
-//     = elems.get_num_copies_expr ()->get_mappings ().get_hirid ();
-//   bool ok = ctx->get_tyctx ()->lookup_type (capacity_ty_id,
-//   &capacity_tyty); rust_assert (ok); tree capacity_type =
-//   TyTyResolveCompile::compile (ctx, capacity_tyty); tree capacity_expr =
-//   CompileExpr::Compile (elems.get_num_copies_expr (), ctx);
-
-//   // create a loop for this with assignments to array_index exprs
-//   tree index_type = capacity_type;
-//   Bvariable *idx
-//     = ctx->get_backend ()->temporary_variable (fnctx.fndecl,
-//     enclosing_scope,
-// 					       index_type, NULL,
-// 					       is_address_taken, expr_locus,
-// 					       &result_var_stmt);
-//   ctx->add_statement (result_var_stmt);
-
-//   // set index to zero
-//   tree index_lvalue = error_mark_node;
-//   tree zero = build_int_cst (index_type, 0);
-//   tree index_assignment
-//     = ctx->get_backend ()->assignment_statement (fnctx.fndecl,
-//     index_lvalue,
-// 						 zero, expr_locus);
-//   ctx->add_statement (index_assignment);
-
-//   // BEGIN loop block
-//   tree loop_body = ctx->get_backend ()->block (fndecl, enclosing_scope, {},
-// 					       start_location, end_location);
-//   ctx->push_block (loop_body);
-
-//   // loop predicate
-//   tree loop_predicate
-//     = fold_build2_loc (expr_locus.gcc_location (), GE_EXPR,
-//     boolean_type_node,
-// 		       ctx->get_backend ()->var_expression (idx, expr_locus),
-// 		       capacity_expr);
-//   tree exit_expr = fold_build1_loc (expr_locus.gcc_location (), EXIT_EXPR,
-// 				    void_type_node, loop_predicate);
-//   tree break_stmt
-//     = ctx->get_backend ()->expression_statement (fnctx.fndecl, exit_expr);
-//   ctx->add_statement (break_stmt);
-
-//   // increment index
-//   tree increment
-//     = fold_build2_loc (expr_locus.gcc_location (), POSTINCREMENT_EXPR,
-// 		       index_type,
-// 		       ctx->get_backend ()->var_expression (idx, expr_locus),
-// 		       build_int_cst (index_type, 1));
-
-//   // create index_assess
-//   tree index_access = ctx->get_backend ()->array_index_expression (
-//     ctx->get_backend ()->var_expression (result, expr_locus), increment,
-//     expr_locus);
-
-//   // create assignment to index_access
-//   tree array_assignment
-//     = ctx->get_backend ()->assignment_statement (fnctx.fndecl,
-//     index_access,
-// 						 translated_expr, expr_locus);
-//   ctx->add_statement (array_assignment);
-
-//   // END loop block
-//   ctx->pop_block ();
-
-//   tree loop_expr = ctx->get_backend ()->loop_expression (loop_body,
-//   expr_locus); tree loop_stmt
-//     = ctx->get_backend ()->expression_statement (fnctx.fndecl, loop_expr);
-//   ctx->add_statement (loop_stmt);
-
-//   // result is the tmp
-//   return ctx->get_backend ()->var_expression (result, expr_locus);
-// }
+tree
+HIRCompileBase::resolve_adjustements (
+  std::vector<Resolver::Adjustment> &adjustments, tree expression,
+  Location locus)
+{
+  tree e = expression;
+  for (auto &adjustment : adjustments)
+    {
+      switch (adjustment.get_type ())
+	{
+	case Resolver::Adjustment::AdjustmentType::ERROR:
+	  return error_mark_node;
+
+	case Resolver::Adjustment::AdjustmentType::IMM_REF:
+	case Resolver::Adjustment::AdjustmentType::MUT_REF:
+	  e = ctx->get_backend ()->address_expression (e, locus);
+	  break;
+
+	case Resolver::Adjustment::AdjustmentType::DEREF_REF:
+	  e = resolve_deref_adjustment (adjustment, e, locus);
+	  break;
+	}
+    }
+
+  return e;
+}
+
+tree
+HIRCompileBase::resolve_deref_adjustment (Resolver::Adjustment &adjustment,
+					  tree expression, Location locus)
+{
+  rust_assert (adjustment.is_deref_adjustment ());
+
+  tree expected_type
+    = TyTyResolveCompile::compile (ctx, adjustment.get_expected ());
+  if (!adjustment.has_operator_overload ())
+    {
+      return ctx->get_backend ()->indirect_expression (expected_type,
+						       expression,
+						       true, /* known_valid*/
+						       locus);
+    }
+
+  TyTy::FnType *lookup = adjustment.get_deref_operator_fn ();
+  HIR::ImplItem *resolved_item = adjustment.get_deref_hir_item ();
+
+  tree fn_address = error_mark_node;
+  if (!lookup->has_subsititions_defined ())
+    fn_address = CompileInherentImplItem::Compile (resolved_item, ctx, true,
+						   nullptr, true, locus);
+  else
+    fn_address = CompileInherentImplItem::Compile (resolved_item, ctx, true,
+						   lookup, true, locus);
+
+  // does it need a reference to call
+  tree adjusted_argument = expression;
+  bool needs_borrow = adjustment.get_deref_adjustment_type ()
+		      != Resolver::Adjustment::AdjustmentType::ERROR;
+  if (needs_borrow)
+    {
+      adjusted_argument
+	= ctx->get_backend ()->address_expression (expression, locus);
+    }
+
+  // make the call
+  auto fncontext = ctx->peek_fn ();
+  tree deref_call
+    = ctx->get_backend ()->call_expression (fncontext.fndecl, fn_address,
+					    {adjusted_argument}, nullptr,
+					    locus);
+
+  // do the indirect expression
+  return ctx->get_backend ()->indirect_expression (expected_type, deref_call,
+						   true, /* known_valid*/
+						   locus);
+}
 
 } // namespace Compile
 } // namespace Rust
diff --git a/gcc/rust/backend/rust-compile-implitem.h b/gcc/rust/backend/rust-compile-implitem.h
index 7bef6ae..82b7c6d 100644
--- a/gcc/rust/backend/rust-compile-implitem.h
+++ b/gcc/rust/backend/rust-compile-implitem.h
@@ -34,14 +34,12 @@ class CompileInherentImplItem : public HIRCompileBase
   using Rust::Compile::HIRCompileBase::visit;
 
 public:
-  static tree Compile (const TyTy::BaseType *self, HIR::ImplItem *item,
-		       Context *ctx, bool compile_fns,
+  static tree Compile (HIR::ImplItem *item, Context *ctx, bool compile_fns,
 		       TyTy::BaseType *concrete = nullptr,
 		       bool is_query_mode = false,
 		       Location ref_locus = Location ())
   {
-    CompileInherentImplItem compiler (self, ctx, compile_fns, concrete,
-				      ref_locus);
+    CompileInherentImplItem compiler (ctx, compile_fns, concrete, ref_locus);
     item->accept_vis (compiler);
 
     if (is_query_mode
@@ -307,15 +305,13 @@ public:
   }
 
 private:
-  CompileInherentImplItem (const TyTy::BaseType *self, Context *ctx,
-			   bool compile_fns, TyTy::BaseType *concrete,
-			   Location ref_locus)
-    : HIRCompileBase (ctx), self (self), compile_fns (compile_fns),
-      concrete (concrete), reference (ctx->get_backend ()->error_expression ()),
+  CompileInherentImplItem (Context *ctx, bool compile_fns,
+			   TyTy::BaseType *concrete, Location ref_locus)
+    : HIRCompileBase (ctx), compile_fns (compile_fns), concrete (concrete),
+      reference (ctx->get_backend ()->error_expression ()),
       ref_locus (ref_locus)
   {}
 
-  const TyTy::BaseType *self;
   bool compile_fns;
   TyTy::BaseType *concrete;
   tree reference;
diff --git a/gcc/rust/backend/rust-compile-item.h b/gcc/rust/backend/rust-compile-item.h
index c35efcc..b3c5ba8 100644
--- a/gcc/rust/backend/rust-compile-item.h
+++ b/gcc/rust/backend/rust-compile-item.h
@@ -395,8 +395,7 @@ public:
       }
 
     for (auto &impl_item : impl_block.get_impl_items ())
-      CompileInherentImplItem::Compile (self_lookup, impl_item.get (), ctx,
-					compile_fns);
+      CompileInherentImplItem::Compile (impl_item.get (), ctx, compile_fns);
   }
 
   void visit (HIR::ExternBlock &extern_block) override
diff --git a/gcc/rust/backend/rust-compile-resolve-path.cc b/gcc/rust/backend/rust-compile-resolve-path.cc
index c1d0778..5c727d6 100644
--- a/gcc/rust/backend/rust-compile-resolve-path.cc
+++ b/gcc/rust/backend/rust-compile-resolve-path.cc
@@ -152,10 +152,10 @@ ResolvePathRef::resolve (const HIR::PathIdentSegment &final_segment,
   // let the query system figure it out
   return query_compile (ref, lookup, final_segment, mappings, expr_locus,
 			is_qualified_path);
-} // namespace Compile
+}
 
 tree
-ResolvePathRef::query_compile (HirId ref, TyTy::BaseType *lookup,
+HIRCompileBase::query_compile (HirId ref, TyTy::BaseType *lookup,
 			       const HIR::PathIdentSegment &final_segment,
 			       const Analysis::NodeMapping &mappings,
 			       Location expr_locus, bool is_qualified_path)
@@ -194,13 +194,11 @@ ResolvePathRef::query_compile (HirId ref, TyTy::BaseType *lookup,
 	  rust_assert (ok);
 
 	  if (!lookup->has_subsititions_defined ())
-	    return CompileInherentImplItem::Compile (self, resolved_item, ctx,
-						     true, nullptr, true,
-						     expr_locus);
+	    return CompileInherentImplItem::Compile (resolved_item, ctx, true,
+						     nullptr, true, expr_locus);
 	  else
-	    return CompileInherentImplItem::Compile (self, resolved_item, ctx,
-						     true, lookup, true,
-						     expr_locus);
+	    return CompileInherentImplItem::Compile (resolved_item, ctx, true,
+						     lookup, true, expr_locus);
 	}
       else
 	{
@@ -278,12 +276,12 @@ ResolvePathRef::query_compile (HirId ref, TyTy::BaseType *lookup,
 	      rust_assert (ok);
 
 	      if (!lookup->has_subsititions_defined ())
-		return CompileInherentImplItem::Compile (self, impl_item, ctx,
-							 true, nullptr, true,
+		return CompileInherentImplItem::Compile (impl_item, ctx, true,
+							 nullptr, true,
 							 expr_locus);
 	      else
-		return CompileInherentImplItem::Compile (self, impl_item, ctx,
-							 true, lookup, true,
+		return CompileInherentImplItem::Compile (impl_item, ctx, true,
+							 lookup, true,
 							 expr_locus);
 
 	      lookup->set_ty_ref (impl_item->get_impl_mappings ().get_hirid ());
diff --git a/gcc/rust/backend/rust-compile-resolve-path.h b/gcc/rust/backend/rust-compile-resolve-path.h
index 56f82d1..97a79e2 100644
--- a/gcc/rust/backend/rust-compile-resolve-path.h
+++ b/gcc/rust/backend/rust-compile-resolve-path.h
@@ -57,11 +57,6 @@ private:
 		const Analysis::NodeMapping &mappings, Location locus,
 		bool is_qualified_path);
 
-  tree query_compile (HirId ref, TyTy::BaseType *lookup,
-		      const HIR::PathIdentSegment &final_segment,
-		      const Analysis::NodeMapping &mappings,
-		      Location expr_locus, bool is_qualified_path);
-
   tree resolved;
 };
 
diff --git a/gcc/rust/backend/rust-compile-var-decl.h b/gcc/rust/backend/rust-compile-var-decl.h
index 4b52dcd..51affe0 100644
--- a/gcc/rust/backend/rust-compile-var-decl.h
+++ b/gcc/rust/backend/rust-compile-var-decl.h
@@ -49,6 +49,7 @@ public:
 
     address_taken_context->lookup_addess_taken (
       stmt.get_mappings ().get_hirid (), &address_taken);
+
     translated_type = TyTyResolveCompile::compile (ctx, resolved_type);
     stmt.get_pattern ()->accept_vis (*this);
   }
diff --git a/gcc/rust/backend/rust-compile.cc b/gcc/rust/backend/rust-compile.cc
index a97ad4d..b17c438 100644
--- a/gcc/rust/backend/rust-compile.cc
+++ b/gcc/rust/backend/rust-compile.cc
@@ -528,9 +528,8 @@ HIRCompileBase::compute_address_for_trait_item (
 	  lookup_fntype = lookup_fntype->handle_substitions (mappings);
 	}
 
-      return CompileInherentImplItem::Compile (root, associated_function, ctx,
-					       true, lookup_fntype, true,
-					       locus);
+      return CompileInherentImplItem::Compile (associated_function, ctx, true,
+					       lookup_fntype, true, locus);
     }
 
   // we can only compile trait-items with a body