C# generic method type argument not inferred from usage

Question

Recently I've experimented with an implementation of the visitor pattern, where I've tried to enforce Accept & Visit methods with generic interfaces:

public interface IVisitable<out TVisitable> where TVisitable : IVisitable<TVisitable>
{
    TResult Accept<TResult>(IVisitor<TResult, TVisitable> visitor);
}

-whose purpose is to 1) mark certain type "Foo" as visitable by such a visitor, which in turn is a "visitor of such type Foo" and 2) enforce Accept method of the correct signature on the implementing visitable type, like so:

public class Foo : IVisitable<Foo>
{
    public TResult Accept<TResult>(IVisitor<TResult, Foo> visitor) => visitor.Visit(this);
}

So far so good, the visitor interface:

public interface IVisitor<out TResult, in TVisitable> where TVisitable : IVisitable<TVisitable>
{
    TResult Visit(TVisitable visitable);
}

-should 1) mark the visitor as "able to visit" the TVisitable 2) what the result type (TResult) for this TVisitable should be 3) enforce Visit method of a correct signature per each TVisitable the visitor implementation is "able to visit", like so:

public class CountVisitor : IVisitor<int, Foo>
{
    public int Visit(Foo visitable) => 42;
}

public class NameVisitor : IVisitor<string, Foo>
{
    public string Visit(Foo visitable) => "Chewie";
}

Quite pleasantly & beautifully, this lets me write:

var theFoo = new Foo();
int count = theFoo.Accept(new CountVisitor());
string name = theFoo.Accept(new NameVisitor());

Very good.

Now the sad times begin, when I add another visitable type, like:

public class Bar : IVisitable<Bar>
{
    public TResult Accept<TResult>(IVisitor<TResult, Bar> visitor) => visitor.Visit(this);
}

which is visitable by let's say just the CountVisitor:

public class CountVisitor : IVisitor<int, Foo>, IVisitor<int, Bar>
{
    public int Visit(Foo visitable) => 42;
    public int Visit(Bar visitable) => 7;
}

which suddenly breaks the type inference in the Accept method! (this destroys the whole design)

var theFoo = new Foo();
int count = theFoo.Accept(new CountVisitor());

giving me:

"The type arguments for method 'Foo.Accept<TResult>(IVisitor<TResult, Foo>)' cannot be inferred from the usage."

Could anyone please elaborate on why is that? There is only one version of IVisitor<T, Foo> interface which the CountVisitor implements - or, if the IVisitor<T, Bar> can't be eliminated for some reason, both of them have the same T - int, = no other type would work there anyway. Does the type inference give up as soon as there are more than just one suitable candidate? (Fun fact: ReSharper thinks the int in theFoo.Accept<int>(...) is redundant :P, even though it wouldn't compile without it)

Answer 1

Does the type inference give up as soon as there are more than just one suitable candidate?

Yes, in this case it does. While attempting to infer the method's generic type parameter (TResult), the type inference algorithm appears to fail on CountVisitor having two inferences to the type IVisitor<TResult, TVisitable>.

---

From the C# 5 specification (the most recent I could find), §7.5.2:

Tr M<X1…Xn>(T1 x1 … Tm xm)

With a method call of the form M(E1 …Em) the task of type inference is to find unique type arguments S1…Sn for each of the type parameters X1…Xn so that the call M<S1…Sn>(E1…Em) becomes valid.

The very first step the compiler takes is as follows (§7.5.2.1):

For each of the method arguments Ei:

• If Ei is an anonymous function, an explicit parameter type inference (§7.5.2.7) is made from Ei to Ti

• Otherwise, if Ei has a type U and xi is a value parameter then a lower-bound inference is made from U to Ti.

You only have one argument, so we have that the only Ei is the expression new CountVisitor(). It's clearly not an anonymous function, so we're in the second bullet point. It's trivial to see that in our case, U is of type CountVisitor. The "xi is a value parameter" bit basically means it's not an out, in, ref etc. variable, which is the case here.

At this point, we now need to make a lower-bound inference from CountVisitor to IVisitor<TResult, TVisitable> The relevant part of §7.5.2.9 (where due to a variable switch, we have V = IVisitor<TResult, TVisitable> in our case):

• Otherwise, sets U1…Uk and V1…Vk are determined by checking if any of the following cases apply:
  • V is an array type V1[…] and U is an array type U1[…] (or a type parameter whose effective base type is U1[…]) of the same rank
  • V is one of IEnumerable<V1>, ICollection<V1> or IList<V1> and U is a one-dimensional array type U1[] (or a type parameter whose effective base type is U1[])
  • V is a constructed class, struct, interface or delegate type C<V1…Vk> and there is a unique type C<U1…Uk> such that U (or, if U is a type parameter, its effective base class or any member of its effective interface set) is identical to, inherits from (directly or indirectly), or implements (directly or indirectly) C<U1…Uk>.

(The “uniqueness” restriction means that in the case interface C<T>{} class U: C<X>, C<Y>{}, then no inference is made when inferring from U to C<T> because U1 could be X or Y.)

We can skip past the first two cases as they're clearly not applicable, the third case is the one we fall into. The compiler attempts to find a unique type C<U1…Uk> that CountVisitor implements and finds two such types, IVisitor<int, Foo> and IVisitor<int, Bar>. Note that the example the spec gives is nearly identical your example.

Because of the uniqueness constraint, no inference is made for this method argument. With the compiler not able to infer any type information from the argument, it has nothing to go on to try to infer TResult and thus fails.

---

As to why there exists a uniqueness constraint, my guess is that it simplifies the algorithm and thus compiler implementation. If you're interested, here's a link to source code where Roslyn (modern C# compiler) implements generic method type inference.

Answer 2

It seems that the type inference works in a greedy way, first trying to match the method generic types, then the class generic types. So if you say

int count = theFoo.Accept<int>(new CountVisitor());

it works, which is strange, since Foo is the only candidate for the class generic type.

First, if you replace the method generic type with a second class generic type, it works:

public interface IVisitable<R, out T> where T: IVisitable<int, T>
{
    R Accept(IVisitor<R, T> visitor);
}

public class Foo : IVisitable<int, Foo>
{
    public int Accept(IVisitor<int, Foo> visitor) => visitor.Visit(this);
}

public class Bar : IVisitable<int, Bar>
{
    public int Accept(IVisitor<int, Bar> visitor) => visitor.Visit(this);
}

public interface IVisitor<out TResult, in T> where T: IVisitable<int, T>
{
    TResult Visit(T visitable);
}

public class CountVisitor : IVisitor<int, Foo>, IVisitor<int, Bar>
{
    public int Visit(Foo visitable) => 42;
    public int Visit(Bar visitable) => 7;
}

class Program {
    static void Main(string[] args) {
        var theFoo = new Foo();
        int count = theFoo.Accept(new CountVisitor());
    }
}

Second (and this is the strange part which highlights how the type inference works) look what happens if you replace int with string in the Bar visitor:

public class CountVisitor : IVisitor<int, Foo> , IVisitor<string, Bar>
{
    public int Visit(Foo visitable) => 42;
    public string Visit(Bar visitable) => "42";
}

First, you get the same error, but watch what happens if you force a string:

    int count = theFoo.Accept<string>(new CountVisitor());

error CS1503: Argument 1: cannot convert from 'CountVisitor' to 'IVisitor<string, Foo>'

Which suggests that the compiler first looks at the method generic types (TResult in your case) and fails immediately if it finds more candidates. It doesn't even look further, at the class generic types.

I tried to find a type inference specification from Microsoft, but couldn't find any.

Answer 3

In C#, you can simplify the Visitor pattern by removing the 'double dispatch' by making use of the dynamic keyword.

You can implement your Visitor like this:

public class CountVisitor : IVisitor<int, IVisitable>
{
   public int Visit( IVisitable v )
   {
       dynamic d = v;
       Visit(d);
   }

    private int Visit( Foo f ) 
    {
        return 42;
    }

    private int Visit( Bar b )
    {
        return 7;
    }
}

By doing this, you won't need to have the Accept method implemented on Foo and Bar although they still must implement a common interface for the Visitor to work offcourse.